Maths Olympiad Prep

Library / /61 of 71

Combinatorics Difficulty 5.5 AIME, harder Prove it United States

Problem:

Consider the cube whose vertices are the eight points (x,y,z)(x, y, z) for which each of xx, yy, and zz is either 00 or 11. 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

Solution:

Answer: 118118

Divide the 88 vertices of the cube into two sets AA and BB such that each set contains 44 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 AA.

- Case 1: 44 black. Then all the vertices in BB must be black, for 11 possible coloring.

- Case 2: 33 black, 11 white. Then there are 44 ways to assign the white vertex. The vertex in BB surrounded by the black vertices must also be black. Meanwhile, the three remaining vertices in BB may be any configuration except all black, for a total of 4(231)=284\left(2^{3}-1\right)=28 possible colorings.

- Case 3: 22 black, 22 white. Then, there are 66 ways to assign the 22 white vertices. The 44 vertices of BB cannot all be the same color. Additionally, we cannot have 33 black vertices of BB surround a white vertex of AA with the other vertex of BB white, and vice-versa, so we have a total of 6(2424)=606\left(2^{4}-2-4\right)=60 possible colorings.

- Case 4: 11 black, 33 white. As in case 22, there are 2828 possible colorings.

- Case 5: 44 white. As in case 11, there is 11 possible coloring.

So there is a total of 1+28+60+28+1=1181+28+60+28+1=118 possible colorings.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.