Difference between revisions of "2011 AIME I Problems/Problem 5"
(→Solution) |
(→Solution: LaTeX and cleanup in general) |
||
Line 3: | Line 3: | ||
== Solution == | == Solution == | ||
− | First, we determine which possible combinations of digits 1 through 9 will yield sums that are multiples of 3. It is simplest to do this by looking at each of the digits | + | First, we determine which possible combinations of digits <math>1</math> through <math>9</math> will yield sums that are multiples of <math>3</math>. It is simplest to do this by looking at each of the digits <math>\bmod{3}</math>. |
+ | |||
+ | We see that the numbers <math>1, 4,</math> and <math>7</math> are congruent to <math>1 \pmod{3}</math>, that the numbers <math>2, 5,</math> and <math>8</math> are congruent to <math>2 \pmod{3}</math>, and that the numbers <math>3, 6,</math> and <math>9</math> are congruent to <math>0 \pmod{3}</math>. In order for a sum of three of these numbers to be a multiple of three, the mod <math>3</math> sum must be congruent to <math>0</math>. Quick inspection reveals that the only possible combinations are <math>0+0+0, 1+1+1, 2+2+2,</math> and <math>0+1+2</math>. However, every set of three consecutive vertices must sum to a multiple of three, so using any of <math>0+0+0, 1+1+1</math>, or <math>2+2+2</math> would cause an adjacent sum to include exactly 2 digits with the same mod 3 value, and this is an unacceptable arrangement. Thus the only possible groupings are composed of three digits congruent to three different mod 3 values. | ||
+ | |||
We see also that there are two possible arrangements for these trios on the nonagon: a digit congruent to 1 (mod 3) can be located counterclockwise of a digit congruent to 0 and clockwise of a digit congruent to 2, or the reverse can be true. | We see also that there are two possible arrangements for these trios on the nonagon: a digit congruent to 1 (mod 3) can be located counterclockwise of a digit congruent to 0 and clockwise of a digit congruent to 2, or the reverse can be true. | ||
+ | |||
The nonagon can be rotated, so if we find all possible strings beginning with one particular digit, we have found all indistinguishable arrangements. For each of the two trio arrangements, we find 72 possible strings: | The nonagon can be rotated, so if we find all possible strings beginning with one particular digit, we have found all indistinguishable arrangements. For each of the two trio arrangements, we find 72 possible strings: | ||
+ | |||
The first digit is predetermined as 3 because we want to avoid strings that rotate to become indistinguishable, so we have one option as a choice for the first digit. The other two 0 (mod 3) numbers can be arranged in 2!=2 ways. The three 1 (mod 3) and three 2 (mod 3) can both be arranged in 3!=6 ways. Therefore, the desired result is 2(2*6*6)=144. | The first digit is predetermined as 3 because we want to avoid strings that rotate to become indistinguishable, so we have one option as a choice for the first digit. The other two 0 (mod 3) numbers can be arranged in 2!=2 ways. The three 1 (mod 3) and three 2 (mod 3) can both be arranged in 3!=6 ways. Therefore, the desired result is 2(2*6*6)=144. | ||
== See also == | == See also == | ||
{{AIME box|year=2011|n=I|num-b=4|num-a=6}} | {{AIME box|year=2011|n=I|num-b=4|num-a=6}} |
Revision as of 12:09, 30 May 2011
Problem
The vertices of a regular nonagon (9-sided polygon) are to be labeled with the digits 1 through 9 in such a way that the sum of the numbers on every three consecutive vertices is a multiple of 3. Two acceptable arrangements are considered to be indistinguishable if one can be obtained from the other by rotating the nonagon in the plane. Find the number of distinguishable acceptable arrangements.
Solution
First, we determine which possible combinations of digits through
will yield sums that are multiples of
. It is simplest to do this by looking at each of the digits
.
We see that the numbers and
are congruent to
, that the numbers
and
are congruent to
, and that the numbers
and
are congruent to
. In order for a sum of three of these numbers to be a multiple of three, the mod
sum must be congruent to
. Quick inspection reveals that the only possible combinations are
and
. However, every set of three consecutive vertices must sum to a multiple of three, so using any of
, or
would cause an adjacent sum to include exactly 2 digits with the same mod 3 value, and this is an unacceptable arrangement. Thus the only possible groupings are composed of three digits congruent to three different mod 3 values.
We see also that there are two possible arrangements for these trios on the nonagon: a digit congruent to 1 (mod 3) can be located counterclockwise of a digit congruent to 0 and clockwise of a digit congruent to 2, or the reverse can be true.
The nonagon can be rotated, so if we find all possible strings beginning with one particular digit, we have found all indistinguishable arrangements. For each of the two trio arrangements, we find 72 possible strings:
The first digit is predetermined as 3 because we want to avoid strings that rotate to become indistinguishable, so we have one option as a choice for the first digit. The other two 0 (mod 3) numbers can be arranged in 2!=2 ways. The three 1 (mod 3) and three 2 (mod 3) can both be arranged in 3!=6 ways. Therefore, the desired result is 2(2*6*6)=144.
See also
2011 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 4 |
Followed by Problem 6 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |