Difference between revisions of "2023 AIME II Problems/Problem 7"

Revision as of 01:16, 27 June 2023

Problem

Each vertex of a regular dodecagon ( $12$ -gon) is to be colored either red or blue, and thus there are $2^{12}$ 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 $2$ options for each vertices 1-6, and the remaining vertices 7-12 are set, yielding $2^6=64$ 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: $2^6*6=384$

case 3: There are two pairs, but oppositely colored. Start with $2^6$ 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. $2^6*15/2=480$

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: $64+384+480=\boxed{928}$

~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, $A$ , $B$ , $C$ , $D$ . Denote by $O$ the center of the dodecagon. Because $OA = OB = OC$ , $\angle OAB = \angle OBA$ and $\angle OBC = \angle OCB$ .

Thus, $\begin{align*} \angle ABC & = \angle OBA + \angle OBC \\ & = \frac{\angle OBA + \angle OAB}{2} + \frac{\angle OBC + \angle OCB}{2} \\ & = \frac{180^\circ - \angle AOB}{2} + \frac{180^\circ - \angle COB}{2} \\ & = 180^\circ - \frac{\angle AOB + \angle COB}{2} \\ & = 180^\circ - \frac{\angle AOC}{2} . \end{align*}$

Hence, $\angle ABC = 90^\circ$ if and only if $\angle AOC = 180^\circ$ . Similarly, $\angle ADC = 90^\circ$ if and only if $\angle AOC = 180^\circ$ , and $\angle BCD = 90^\circ$ (or $\angle DAB = 90^\circ$ ) if and only if $\angle BOD = 180^\circ$ .

Therefore, $ABCD$ is a rectangle if and only if two diagonals both pass through $O$ .

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 $2^6$ .

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 $2^5$ .

Following from the rule of product, the total number of configurations in this case is $6 \cdot 2 \cdot 2^5 = 6 \cdot 2^6$ .

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 $2^4$ .

Following from the rule of product, the total number of configurations in this case is $6 \cdot 5 \cdot 2^4 = 30 \cdot 2^4$ .

Putting all cases together, the total number of feasible configurations is $2^6 + 6 \cdot 2^6 + 30 \cdot 2^4 = \boxed{\textbf{(928) }}.$

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

Video Solution by The Power of Logic

https://youtu.be/sTOqj9OAc4o

@@ Line 93: / Line 93: @@
 ~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
+==Video Solution by The Power of Logic==
+https://youtu.be/sTOqj9OAc4o
 == 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

Page

Toolbox

Search