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

英文解析

14. [ 9 ] How many ways can the eight vertices of a three-dimensional cube be colored red and blue suchthat no two points connected by an edge are both red? Rotations and reflections of a given coloringare 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.
    ( )
    • R = 2 : Any pair not an edge works, so the answer is − 12 = 16.8
    • R = 3 : Each face ABCD and EF GH has at most two red spots. Assume WLOG ABCD has 2
    exactly two and EF GH has exactly one (multiply by 2 at the end). There are two ways to pickthose in ABCD (two opposite corners), and two ways after that to pick EF GH . Hence the grandtotal for this subcase is 2 · 2 · 2 = 8.
    • R = 4 : There are only two ways to do this.
    Hence, the sum is 35.