HMMT 十一月 2025 · 冲刺赛 · 第 28 题
HMMT November 2025 — Guts Round — Problem 28
题目详情
- [15] Let S be the set of integers between 0 and 100 (inclusive). Compute the number of ways to color each element of S either red, green, or blue such that for all elements x and y of S with | x − y | − 1 divisible by 3, the colors of x and y are different.
解析
- [15] Let S be the set of integers between 0 and 100 (inclusive). Compute the number of ways to color each element of S either red, green, or blue such that for all elements x and y of S with | x − y | − 1 divisible by 3, the colors of x and y are different. Proposed by: Derek Liu Answer: 606 R B G G R R G B B G R R G B Example of blocking when there are only 14 integers. Solution 1: We work modulo 101, arranging the numbers in a circle. Since 101 ≡ 2 mod 3, if the clockwise distance between two numbers is 1 mod 3, so is the counterclockwise distance between them. Some color must appear at least ⌈ 101 / 3 ⌉ = 34 times, dividing the circle into at least 34 intervals, which we will call blocks for clarity. No block can have length 1 mod 3 by definition. Furthermore, at most one block can have length 2 mod 3; otherwise, any interval spanning exactly two blocks of length 2 mod 3 (so the rest are length 0 mod 3) would have total length 1 mod 3, which is disallowed. It is also clear that not every block can have length 0 mod 3, as they have total length 101, so there must be exactly 1 block of length 2 mod 3. Since there are at least 34 blocks, their total length is at least 2+33 · 3 = 101. Thus, equality holds, and this color appears exactly 34 times. It follows that of the remaining 101 − 34 = 67 numbers, another color appears 34 times. Without loss of generality, we assume red and green appear 34 times each, with the red numbers being every multiple of 3. (Any possible arrangement of 34 red numbers can be reached from this one by rotation.) © 2025 HMMT By the argument above, there exists x for which both x − 1 and x + 1 are both green. If x is not red, then one of x ± 1 is red, so x must be red. If x is neither 0 nor 99, then both x − 2 and x + 2 are blue, but they differ by 4 (or 97), which is disallowed. Thus x = 0 or x = 99. Both lead to valid colorings (with the green numbers being 1, 4, 7, . . . , 100 and 2, 5, . . . , 95, 98, 100, respectively); one is a rotation of the other with red and green swapped. Thus, there is one coloring up to rotation and permutation of colors, or 3! · 101 = 606 colorings total. Solution 2: Without loss of generality, assume 0 is red and 1 is green; we will multiply by 6 at the end. Then, 2 is either red or blue. • If 2 is red, then 3 is either green or blue. – If 3 is green, then 4 must be blue and 5 must be red. Then, 6 cannot be blue, because that would make 0, 3, and 6 all different colors, leaving no choices for 7. Thus, 6 must be green. Then, 7 must be blue and 8 must be red. Again, 9 cannot be blue, because that would make 0, 3, and 9 all different colors, leaving no choices for 10. By repeating this argument, we get that the entire coloring is fixed with the following repeating pattern: RG ( RGB )( RGB )( RGB ) . . . . – If 3 is blue, then 4 must be green. Then, 5 cannot be blue, because that would force 6 to be green, making 0, 3, and 6 all different colors, leaving no choices for 7. Thus, 5 must be red. Then, 6 cannot be green, because that would make 0, 3, and 6 all different colors, leaving no choices for 7. Thus, 6 must be blue. By repeating these arguments, we get that the entire coloring is fixed with the following repeating pattern: RG ( RBG )( RBG )( RBG ) . . . . Therefore, there are 2 colorings in this case. • If 2 is blue, then consider splitting the coloring into an initial pair followed by several triples: ( RG )( B )( ) . . . ( ) . One valid coloring is setting all triples to be BRG . Otherwise, consider the first triple that deviates from BRG . – If it starts with a color other than B , then it must start with R because the previous pair/triple ends with G . From here, it is easy to check every remaining triple is RGB . – If it starts with B and its second color is not R , then its second color must be G . From here, it is easy to check that the triple must be BGB , and all remaining triples must be RGB . – If it starts with BR and its third color is not G , then its third color must be B . From here, it is easy to check that the triple must be BRB , and all remaining triples must be RGB . Therefore, the number of colorings equals the number of positions where the coloring could first deviate from RG ( RBG )( RBG ) . . . , plus 1 for the case where no deviation occurs. Hence, there are 98 + 1 = 99 colorings for this case. Our final answer is 6 · (99 + 2) = 606 .