HMMT 二月 2020 · COMB 赛 · 第 9 题
HMMT February 2020 — COMB Round — Problem 9
题目详情
- Farmer James wishes to cover a circle with circumference 10 π with six different types of colored arcs. Each type of arc has radius 5, has length either π or 2 π , and is colored either red, green, or blue. He has an unlimited number of each of the six arc types. He wishes to completely cover his circle without overlap, subject to the following conditions: • Any two adjacent arcs are of different colors. • Any three adjacent arcs where the middle arc has length π are of three different colors. Find the number of distinct ways Farmer James can cover his circle. Here, two coverings are equivalent if and only if they are rotations of one another. In particular, two colorings are considered distinct if they are reflections of one another, but not rotations of one another.
解析
- Farmer James wishes to cover a circle with circumference 10 π with six different types of colored arcs. Each type of arc has radius 5, has length either π or 2 π , and is colored either red, green, or blue. He has an unlimited number of each of the six arc types. He wishes to completely cover his circle without overlap, subject to the following conditions: • Any two adjacent arcs are of different colors. • Any three adjacent arcs where the middle arc has length π are of three different colors. Find the number of distinct ways Farmer James can cover his circle. Here, two coverings are equivalent if and only if they are rotations of one another. In particular, two colorings are considered distinct if they are reflections of one another, but not rotations of one another. Proposed by: James Lin Answer: 93 Solution: Fix an orientation of the circle, and observe that the the problem is equivalent to finding the number of ways to color ten equal arcs of the circle such that each arc is one of three different colors, and any two arcs which are separated by exactly one arc are of different colors. We can consider every other arc, so we are trying to color just five arcs so that no two adjacent arcs are of the same color. This is independent from the coloring of the other five arcs. Let a be the number of ways to color i arcs in three colors so that no two adjacent arcs are the same i i color. Note that a = 3 and a = 6. We claim that a + a = 3 · 2 for i ≥ 2. To prove this, observe 1 2 i i +1 that a counts the number of ways to color i + 1 points in a line so that no two adjacent points are the i same color, and the first and ( i + 1)th points are the same color. Meanwhile, a counts the number i +1 of ways to color i + 1 points in a line so that no two adjacent points are the same color, and the first and ( i + 1)th points are different colors. Then a + a is the number of ways to color i + 1 points in i i +1 i a line so that no two adjacent points are the same color. There are clearly 3 · 2 ways to do this, as we pick the colors from left to right, with 3 choices for the first color and 2 for the rest. We then compute a = 6, a = 18, a = 30. Then we can color the whole original circle by picking one of the 30 possible 3 4 5 2 colorings for each of the two sets of 5 alternating arcs, for 30 = 900 total. Now, we must consider the rotational symmetry. If a configuration has no rotational symmetry, then ◦ we have counted it 10 times. If a configuration has 180 rotational symmetry, then we have counted it 5 times. This occurs exactly when we have picked the same coloring from our 30 for both choices, ◦ ◦ and in exactly one particular orientation, so there are 30 such cases. Having 72 or 36 rotational symmetry is impossible, as arcs with exactly one arc between them must be different colors. Then after we correct for overcounting our answer is 900 − 30 30
- = 93 . 10 5