PUMaC 2014 · 组合（A 组） · 第 6 题
PUMaC 2014 — Combinatorics (Division A) — Problem 6
题目详情
- [ 6 ] Let f ( n ) be the number of points of intersections of diagonals of a n -dimensional hypercube that is not the vertice of the cube. For example, f (3) = 7 because the intersection points of a cube’s diagonals are at the centers of each face and the center of the cube. Find f (5)
解析
- [ 6 ] Let f ( n ) be the number of points of intersections of diagonals of a n -dimensional hypercube that is not the vertice of the cube. For example, f (3) = 7 because the intersection points of a cube’s diagonals are at the centers of each face and the center of the cube. Find f (5) Solutions: 1 Lemma 1: Each coordinate of a diagonal intersection is either a 0, a 1, or a . 2 Proof: Each diagonal has a paramentric representation; each coordinate is either 0, 1, t , or 1- t , where 0 ≤ t ≤ 1. At least two coordinates must be t or 1 − t . Diagonals D and D (with 1 2 parametric representations D ( t ) = ( x ( t ) , x ( t ) , ..., x ( t )) and D ( t ) = ( y ( t ) , y ( t ) , ..., y ( t ))) 1 1 2 n 2 1 2 n intersect when t can be set so that the coordinates of D and D are the same. Since D and 1 2 1 D are distinct, there must be at least one coordinate i for which their equations differ, and 2 for which these equations are without loss of generality x = 1 − t and y = t (otherwise the i 1 i 2 diagonals could only meet at a vertex of the hypercube). There must be another coordinate j for which x = t and y = t (otherwise we could set s = 1 − t , describe D in terms of s , j 1 j 2 2 2 and there would be no coordinate satisfying the conditions of i ). Thus, D and D must meet 1 2 1 at the point where t = t = , so the intersection point’s coordinates are each either 0, 1, or 1 2 2 1 1 , with at least two coordinates that are . 2 2 1 Lemma 2: Let x = ( x , x , ..., x ) be a point in n -space such that x ∈ { 0 , 1 , } for each i , and 1 2 n i 2 1 such that x = x = for some distinct i and j . Then there exist two diagonals of the n -cube i j 2 that intersect at x . 1 Proof: Without loss of generality, suppose x = x = ... = x = , and x , x , ..., x ∈ 1 2 k k +1 k +2 n 2 { 0 , 1 } . We define points A = (0 , 0 , ..., 0 , x , x , ..., x ), B = (1 , 1 , ..., 1 , x , x , ..., x ), k +1 k +2 n k +1 k +2 n C = (1 , 0 , 0 , ..., 0 , x , x , ..., x ), and D = (0 , 1 , ..., 1 , x , x , ..., x ). Diagonals AB k +1 k +2 n k +1 k +2 n and CD intersect at x . 4 Thus, there is a one-to-one correspondence between intersection points and n -tuples consist- 1 n n − 1 n n ing of 1s, 0s, and at least two s. There are 3 − n 2 − 2 of these tuples (3 total 2 1 n − 1 1 n tuples consisting of 0s, 1s, and s; n 2 tuples with one , and 2 with only 0s and 1s), so 2 2 n n − 1 n f ( n ) = 3 − n 2 − 2 . 5 4 5 Hence f (5) = 3 − 5 × 2 − 2 = 131 .