PUMaC 2019 · 团队赛 · 第 10 题

PUMaC 2019 — Team Round — Problem 10

Define the unit N -hypercube to be the set of points [0 , 1] ⊂ R . For example, the unit 0-hypercube is a point, and the unit 3-hypercube is the unit cube. Define a k -face of the unit N -hypercube to be a copy of the k -hypercube in the exterior of the N -hypercube. More formally, a k -face of the unit N -hypercube is a set of the form N ∏ S i i =1 where S is either { 0 } , { 1 } , or [0 , 1] for each 1 ≤ i ≤ N , and there are exactly k indices i such i that S = [0 , 1]. i The expected value of the dimension of a random face of the unit 8-hypercube (where the p dimension of a face can be any value between 0 and N ) can be written in the form where p q and q are relatively prime positive integers. Find p + q .

解析

Define the unit N -hypercube to be the set of points [0 , 1] ⊂ R . For example, the unit 0-hypercube is a point, and the unit 3-hypercube is the unit cube. Define a k -face of the unit N -hypercube to be a copy of the k -hypercube in the exterior of the N -hypercube. More formally, a k -face of the unit N -hypercube is a set of the form N ∏ S i i =1 where S is either { 0 } , { 1 } , or [0 , 1] for each 1 ≤ i ≤ N , and there are exactly k indices i such i that S = [0 , 1]. i The expected value of the dimension of a random face of the unit 8-hypercube (where the p dimension of a face can be any value between 0 and N ) can be written in the form where p q and q are relatively prime positive integers. Find p + q . Proposed by: Matt Tyler Answer: 11 Solution by Michael Gintz 8 Note that there is a bijection between the faces of this hypercube and elements of { 0 , [1 , 0] , 1 } by definition. Then the dimension of a k -face is the number of [0 , 1]’s in the 8-element set corresponding to it. By linearity this is on average 8/3.