Consider the cube whose vertices are the eight points for which each of , and 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.
Solution
Divide the 8 vertices of the cube into two sets and 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 . - Case 1: 4 black. Then all the vertices in 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 surrounded by the black vertices must also be black. Meanwhile, the three remaining vertices in may be any configuration except all black, for a total of possible colorings. - Case 3: 2 black, 2 white. Then, there are 6 ways to assign the 2 white vertices. The 4 vertices of cannot all be the same color. Additionally, we cannot have 3 black vertices of surround a white vertex of with the other vertex of white, and vice-versa, so we have a total of 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 possible colorings.