HMMT 十一月 2022 · 冲刺赛 · 第 17 题

HMMT November 2022 — Guts Round — Problem 17

[10] How many ways are there to color every integer either red or blue such that n and n + 7 are the same color for all integers n , and there does not exist an integer k such that k , k + 1, and 2 k are all the same color?

解析

[10] How many ways are there to color every integer either red or blue such that n and n + 7 are the same color for all integers n , and there does not exist an integer k such that k , k + 1, and 2 k are all the same color? Proposed by: Luke Robitaille Answer: 6 Solution: It suffices to color the integers from 0 through 6 and do all arithmetic mod 7. WLOG, say that 0 is red (we’ll multiply by 2 in the end). Then 1 must be blue because (0 , 0 , 1) can’t be monochromatic. 2 must be red because (1 , 2 , 2) can’t be monochromatic. Then we have two cases for what 3 is: Case 1: 3 is red. Then 4 is blue because (2 , 3 , 4) can’t be monochromatic. This makes 5 red because (4 , 5 , 1) can’t be monochromatic. Finally, 6 must be blue because (6 , 0 , 5) can’t be monochromatic. This gives a single consistent coloring for this case. Case 2: 3 is blue. 4 can’t also be blue because this would imply that 5 is red (because of (4 , 5 , 1)) and 6 is red (because of (3 , 4 , 6)), which would make (6 , 0 , 5) all red. So 4 must be red. Then we have two possibilities: either 5 is red and 6 is blue, or 5 is blue and 6 is red (5 and 6 can’t both be red because of (6 , 0 , 5), and they can’t both be blue because of (5 , 6 , 3)). These give two consistent colorings for this case. Overall, we have three consistent colorings: RBRRBRB , RBRBRRB , and RBRBRBR . Multiply this by 2 be- cause 0 could have been blue, and our answer is 6.