HMMT 二月 2021 · 冲刺赛 · 第 12 题

HMMT February 2021 — Guts Round — Problem 12

[10] Compute the number of labelings f : { 0 , 1 } → { 0 , 1 , . . . , 7 } of the vertices of the unit cube such that 2 | f ( v ) − f ( v ) | ≥ d ( v , v ) i j i j for all vertices v , v of the unit cube, where d ( v , v ) denotes the Euclidean distance between v and v . i j i j i j . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT Spring 2021, March 06, 2021 — GUTS ROUND Organization Team Team ID#

解析

[10] Compute the number of labelings f : { 0 , 1 } → { 0 , 1 , . . . , 7 } of the vertices of the unit cube such that 2 | f ( v ) − f ( v ) | ≥ d ( v , v ) i j i j for all vertices v , v of the unit cube, where d ( v , v ) denotes the Euclidean distance between v and i j i j i v . j Proposed by: Krit Boonsiriseth Answer: 144 3 Solution: Let B = { 0 , 1 } , let E = { ( x, y, z ) ∈ B : x + y + z is even } , and let O = { ( x, y, z ) ∈ B : √ x + y + z is odd } . As all pairs of vertices within E (and within O ) are 2 apart, is easy to see that { f ( E ) , f ( O ) } = {{ 0 , 2 , 4 , 6 } , { 1 , 3 , 5 , 7 }} . • There are two ways to choose f ( E ) and f ( O ); from now on WLOG assume f ( E ) = { 0 , 2 , 4 , 6 } . • There are 4! ways to assign the four labels to the four vertices in E . • The vertex opposite the vertex labeled 0 is in O , and it must be labeled 3 , 5 , or 7. It is easy to check that for each possible label of this vertex, there is exactly one way to label the three remaining vertices. Therefore the total number of labelings is 2 · 4! · 3 = 144 .