Difference between revisions of "2023 AIME II Problems/Problem 7"
R00tsofunity (talk | contribs) |
|||
Line 96: | Line 96: | ||
== See also == | == See also == | ||
{{AIME box|year=2023|num-b=6|num-a=8|n=II}} | {{AIME box|year=2023|num-b=6|num-a=8|n=II}} | ||
+ | |||
+ | [[Category:Intermediate Combinatorics Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 20:34, 17 February 2023
Contents
Problem
Each vertex of a regular dodecagon (-gon) is to be colored either red or blue, and thus there are possible colorings. Find the number of these colorings with the property that no four vertices colored the same color are the four vertices of a rectangle.
Solution 1
Note that the condition is equivalent to stating that there are no 2 pairs of oppositely spaced vertices with the same color.
Case 1: There are no pairs. This yields options for each vertices 1-6, and the remaining vertices 7-12 are set, yielding cases.
Case 2: There is one pair. Again start with 2 options for each vertex in 1-6, but now multiply by 6 since there are 6 possibilities for which pair can have the same color assigned instead of the opposite. Thus, the cases are:
case 3: There are two pairs, but oppositely colored. Start with for assigning 1-6, then multiply by 6C2=15 for assigning which have repeated colors. Divide by 2 due to half the cases having the same colored opposites.
It is apparent that no other cases exist, as more pairs would force there to be 2 pairs of same colored oppositely spaced vertices with the same color. Thus, the answer is:
~SAHANWIJETUNGA
Solution 2
First, we identify the geometric condition for the sentence ``four vertices colored the same color are the four vertices of a rectangle. Consider any four vertices on the dodecagon, , , , . Denote by the center of the dodecagon. Because , and .
Thus,
Hence, if and only if . Similarly, if and only if , and (or ) if and only if .
Therefore, is a rectangle if and only if two diagonals both pass through .
Now, we categorize 12 vertices into 6 groups. Each group contains 2 diagonal vertices. Next, we compute the number of coloring configurations such that the above same-color rectangles do not exist.
Case 1: Two vertices in each group has distinct colors.
For each group, we only need to determine which vertex is red. The other one must be blue. Therefore, the number of configurations in this case is .
Case 2: There is one group who vertices have the same color. All other groups are with vertices that have distinct colors.
We construct such an instance in the following steps.
Step 1: We determine which group has two vertices that have the same color.
The number of ways is 6.
Step 2: For the selected group, we choose a color for its two vertices.
The number of ways is 2.
Step 3: For each unselected group, we determine which vertex is red.
The number of ways is .
Following from the rule of product, the total number of configurations in this case is .
Case 3: One group has two red vertices, one group has two blue vertices, and each of the other four groups has vertices with distinct colors.
We construct such an instance in the following steps.
Step 1: We determine which group has two vertices that have both red color.
The number of ways is 6.
Step 2: We determine which group has two vertices that have both blue color.
The number of ways is 5.
Step 3: For each unselected group, we determine which vertex is red.
The number of ways is .
Following from the rule of product, the total number of configurations in this case is .
Putting all cases together, the total number of feasible configurations is
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
See also
2023 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 6 |
Followed by Problem 8 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.