PUMaC 2022 · 组合（A 组） · 第 4 题
PUMaC 2022 — Combinatorics (Division A) — Problem 4
题目详情
- Let C denote the n -dimensional unit cube, consisting of the 2 points n { ( x , x , . . . , x ) | x ∈ { 0 , 1 } for all 1 ≤ i ≤ n } . 1 2 n i A tetrahedron is equilateral if all six side lengths are equal. Find the smallest positive integer n for which there are four distinct points in C that form a non-equilateral tetrahedron with n integer side lengths.
解析
- Let C denote the n -dimensional unit cube, consisting of the 2 points n { ( x , x , . . . , x ) | x ∈ { 0 , 1 } for all 1 ≤ i ≤ n } . 1 2 n i A tetrahedron is equilateral if all six side lengths are equal. Find the smallest positive integer n for which there are four distinct points in C that form a non-equilateral tetrahedron with n integer side lengths. Proposed by Ryan Alweiss Answer: 11 Note that the square of the Euclidean distance between any two points in C equals the n Hamming distance d between the points, which is defined as d ( x, y ) = |{ i | 1 ≤ i ≤ n, x ̸ = H H i y }| . Note that d ( x, y ) + d ( y, z ) ≥ d ( x, z ) for all x, y, z ∈ C . i H H H n I claim that if A and B are vertices of the tetrahedron, then d ( A, B ) > 1. If not, then given H a third vertex z of the tetrahedron, d ( z, x ) and d ( z, y ) are two squares that differ by 1. The H H only such squares are 0 and 1, which implies that either z = x or z = y , which is impossible. Therefore, we have d ( x, y ) ≥ 4. We cannot have n < 9, because otherwise the only possible H integer side length would be 2 and the tetrahedron would be equilateral. For a construction when n = 11, consider the vertices given by (0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0), (0 , 0 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 1 , 1), (1 , 1 , 1 , 1 , 0 , 0 , 1 , 1 , 1 , 1 , 1), (1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0). It suffices to rule out any possibilities for n = 9 and n = 10. Since one of the side lengths of the tetrahedron must be 3, we must have that d ( A, B ) = 9 for some points A, B ∈ C . Thus, for H n any other vertex C , we cannot have d ( A, C ) = d ( B, C ) = 4 because d ( A, C )+ d ( C, B ) ≥ H H H H d ( A, B ) = 9. Since the only other possible side length is 9, we can assume without of loss H of generality that d ( A, C ) = 9. If n = 9, then there is exactly one point with Hamming H distance 9 away from A , which implies that B = C , a contradiction. If n = 10, then B and C must have at least 9 + 9 − 10 = 8 coordinates in common, which means they have Hamming distance at most 2. But we know that d ( B, C ) ≥ 4, which is a contradiction. H It follows that n = 11 is minimal. 2