Difference between revisions of "2011 AIME II Problems/Problem 14"
(→Solution 1) |
(→Solution 1) |
||
Line 19: | Line 19: | ||
All numbers from 6 to 30 are also fixed in this manner. All values of i, j, and k have been used, so every one of these numbers will have a unique triple for placement, as above with the number five. Thus, after 1, 2, 3, and 4 have been placed, the rest of the permutation is fixed. | All numbers from 6 to 30 are also fixed in this manner. All values of i, j, and k have been used, so every one of these numbers will have a unique triple for placement, as above with the number five. Thus, after 1, 2, 3, and 4 have been placed, the rest of the permutation is fixed. | ||
− | Thus, N = 30*8*3*2=30*24=1440. Thus, the remainder when N is divided by 1000 <math>\framebox[1. | + | Thus, N = 30*8*3*2=30*24=1440. Thus, the remainder when N is divided by 1000 <math>\framebox[1.5\width]{440.}</math> |
==Solution 2== | ==Solution 2== |
Revision as of 17:19, 1 April 2011
Problem 14
There are N permutations of 1, 2, ... , 30 such that for
, m divides
for all integers n with
. Find the remainder when N is divided by 1000.
Solution 1
Each position in the 30-position permutation is uniquely defined by an ordered triple . The nth position is defined by this ordered triple where i is n mod 2, j is n mod 3, and k is n mod 5. There are 2 choices for i, 3 for j, and 5 for k, yielding 2*3*5=30 possible triples. Because the least common multiple of 2, 3, and 5 is 30, none of these triples are repeated and all are used. By the conditions of the problem, if i is the same in two different triples, then the two numbers in these positions must be equivalent mod 2. If j is the same, then the two numbers must be equivalent mod 3, and if k is the same, the two numbers must be equivalent mod 5.
The ordered triple (or position) in which the number one can be placed has 2 options for i, 3 for j, and 5 for k, resulting in 30 different positions it can be placed.
The ordered triple where 2 can be placed in somewhat constrained by the placement of the number 1. Because 1 is not equivalent to 2 mod 2, 3, or 5, the i, j, and k in their ordered triples must be different. Thus, for the number 2, there are (2-1) choices for i, (3-1) choices for j, and (5-1) choices for k. Thus, there are 1*2*4=8 possible placements for the number two once the number one is placed.
Because 3 is equivalent to 1 mod 2, it must have the same i as the ordered triple of 1. Because 3 is not equivalent to 1 or 2 mod 3 or 5, it must have different j and k values. Thus, there is 1 choice for i, (2-1) choices for j, and (4-1) choices for k, for a total of 1*1*3=3 choices for the placement of 3.
As above, 4 is even, so it must have the same value of i as 2. It is also 1 mod 3, so it must have the same j value of 2. 4 is not equivalent to 1, 2, or 3 mod 5, so it must have a different k value than that of 1, 2, and 3. Thus, there is 1 choice for i, 1 choice for j, and (3-1) choices for k, yielding a total of 1*1*2=2 possible placements for 4.
5 is odd and is equivalent to 2 mod 3, so it must have the same i value as 1 and the same j value of 2. 5 is not equivalent to 1, 2, 3, or 4 mod 5, so it must have a different k value from 1, 2, 3, and 4. However, 4 different values of k are held by these four numbers, so 5 must hold the one remaining value. Thus, only one possible triple is found for the placement of 5.
All numbers from 6 to 30 are also fixed in this manner. All values of i, j, and k have been used, so every one of these numbers will have a unique triple for placement, as above with the number five. Thus, after 1, 2, 3, and 4 have been placed, the rest of the permutation is fixed.
Thus, N = 30*8*3*2=30*24=1440. Thus, the remainder when N is divided by 1000
Solution 2
We observe that the condition on the permutations means that two numbers with indices congruent are themselves congruent
for
Furthermore, suppose that
Then, there are
indices congruent to
and
numbers congruent to
because 2, 3, and 5 are all factors of 30. Therefore, since every index congruent to
must contain a number congruent to
and no number can appear twice in the permutation, only the indices congruent to
contain numbers congruent to
In other words,
This tells us that in a valid permutation, the congruence classes are simply swapped around, and if the set
is a congruence class
for
2, 3, or 5, the set
is still a congruence class
Clearly, each valid permutation of the numbers 1 through 30 corresponds to exactly one permutation of the congruence classes modulo 2, 3, and 5. Also, if we choose some permutations of the congruence classes modulo 2, 3, and 5, they correspond to exactly one valid permutation of the numbers 1 through 30. This can be shown as follows: First of all, the choice of permutations of the congruence classes gives us every number in the permutation modulo 2, 3, and 5, so by the Chinese Remainder Theorem, it gives us every number
Because the numbers must be between 1 and 30 inclusive, it thus uniquely determines what number goes in each index. Furthermore, two different indices cannot contain the same number. We will prove this by contradiction, calling the indices
and
for
If
then they must have the same residues modulo 2, 3, and 5, and so
modulo 2, 3, and 5. Again using the Chinese Remainder Theorem, we conclude that
so because
and
are both between 1 and 30 inclusive,
giving us a contradiction. Therefore, every choice of permutations of the congruence classes modulo 2, 3, and 5 corresponds to exactly one valid permutation of the numbers 1 through 30.
We have now established a bijection between valid permutations of the numbers 1 through 30 and permutations of the congruence classes modulo 2, 3, and 5, so is equal to the number of permutations of congruence classes. There are always
congruence classes
so