Maths Olympiad Prep

Library / /511 of 860

Combinatorics Difficulty 5.2 AIME, harder Find the answer

Consider the cube whose vertices are the eight points (x,y,z)(x, y, z) for which each of x,yx, y, and zz 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.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Divide the 8 vertices of the cube into two sets AA and BB 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 AA. - Case 1: 4 black. Then all the vertices in BB 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 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: 2 black, 2 white. Then, there are 6 ways to assign the 2 white vertices. The 4 vertices of BB cannot all be the same color. Additionally, we cannot have 3 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: 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=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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.