HMMT 二月 2012 · 冲刺赛 · 第 29 题
HMMT February 2012 — Guts Round — Problem 29
题目详情
- [ 19 ] Consider the cube whose vertices are the eight points ( x, y, z ) for which each of x , y , and z is either 0 or 1. How many ways are there to color its vertices black or white such that, for any vertex, if all of its neighbors are the same color then it is also that color? Two vertices are neighbors if they are the two endpoints of some edge of the cube.
解析
- [ 19 ] Consider the cube whose vertices are the eight points ( x, y, z ) for which each of x , y , and z is either 0 or 1. How many ways are there to color its vertices black or white such that, for any vertex, if all of its neighbors are the same color then it is also that color? Two vertices are neighbors if they are the two endpoints of some edge of the cube. Answer: 118 Divide the 8 vertices of the cube into two sets A and B such that each set contains 4 vertices, any two of which are diagonally adjacent across a face of the cube. We do casework based on the number of vertices of each color in set A . • Case 1: 4 black. Then all the vertices in B must be black, for 1 possible coloring. • Case 2: 3 black, 1 white. Then there are 4 ways to assign the white vertex. The vertex in B surrounded by the black vertices must also be black. Meanwhile, the three remaining vertices in 3 B may be any configuration except all black, for a total of 4(2 − 1) = 28 possible colorings. • Case 3: 2 black, 2 white. Then, there are 6 ways to assign the 2 white vertices. The 4 vertices of B cannot all be the same color. Additionally, we cannot have 3 black vertices of B surround a white 4 vertex of A with the other vertex of B white, and vice-versa, so we have a total of 6(2 − 2 − 4) = 60 possible colorings. • Case 4: 1 black, 3 white. As in case 2, there are 28 possible colorings. • Case 5: 5 white. As in case 1, there is 1 possible coloring. So there is a total of 1 + 28 + 60 + 28 + 1 = 118 possible colorings.