返回题库

HMMT 二月 2020 · COMB 赛 · 第 9 题

HMMT February 2020 — COMB Round — Problem 9

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. 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. Hehas an unlimited number of each of the six arc types. He wishes to completely cover his circle withoutoverlap, 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 equivalentif and only if they are rotations of one another. In particular, two colorings are considered distinct ifthey are reflections of one another, but not rotations of one another.
解析

英文解析

  1. 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. Hehas an unlimited number of each of the six arc types. He wishes to completely cover his circle withoutoverlap, 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 equivalentif and only if they are rotations of one another. In particular, two colorings are considered distinct ifthey 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 findingthe number of ways to color ten equal arcs of the circle such that each arc is one of three differentcolors, and any two arcs which are separated by exactly one arc are of different colors. We can considerevery other arc, so we are trying to color just five arcs so that no two adjacent arcs are of the samecolor. 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 sameicolor. Note that a = 3 and a = 6. We claim that a + a = 3 · 2 for i ≥ 2. To prove this, observei
    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 theisame color, and the first and ( i + 1)th points are the same color. Meanwhile, a counts the numberi +1
    of ways to color i + 1 points in a line so that no two adjacent points are the same color, and the firstand ( i + 1)th points are different colors. Then a + a is the number of ways to color i + 1 points ini i +1
    a line so that no two adjacent points are the same color. There are clearly 3 · 2 ways to do this, as weipick the colors from left to right, with 3 choices for the first color and 2 for the rest. We then computea = 6, a = 18, a = 30. Then we can color the whole original circle by picking one of the 30 possible
    3 4 5
    colorings for each of the two sets of 5 alternating arcs, for 30 = 900 total.2
    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 countedit 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 rotationalsymmetry is impossible, as arcs with exactly one arc between them must be different colors. Thenafter we correct for overcounting our answer is
    900 − 30 30 + = 93 .
    10 5