HMMT 十一月 2014 · 冲刺赛 · 第 14 题

HMMT November 2014 — Guts Round — Problem 14

[ 9 ] How many ways can the eight vertices of a three-dimensional cube be colored red and blue such that no two points connected by an edge are both red? Rotations and reflections of a given coloring are considered distinct.

解析

[ 9 ] How many ways can the eight vertices of a three-dimensional cube be colored red and blue such that no two points connected by an edge are both red? Rotations and reflections of a given coloring are considered distinct. Answer: 35 We do casework on R , the number of red vertices. Let the cube be called ABCDEF GH , with opposite faces ABCD and EF GH , such that A is directly above E . • R = 0 : There is one such coloring, which has only blue vertices. Guts Round • R = 1 : There are 8 ways to choose the red vertex, and all other vertices must be blue. There are 8 colorings in this case. ( ) 8 • R = 2 : Any pair not an edge works, so the answer is − 12 = 16. 2 • R = 3 : Each face ABCD and EF GH has at most two red spots. Assume WLOG ABCD has exactly two and EF GH has exactly one (multiply by 2 at the end). There are two ways to pick those in ABCD (two opposite corners), and two ways after that to pick EF GH . Hence the grand total for this subcase is 2 · 2 · 2 = 8. • R = 4 : There are only two ways to do this. Hence, the sum is 35.