Difference between revisions of "2011 AIME II Problems/Problem 14"
(Created page with 'Problem: There are N permutations <math>(a_{1}, a_{2}, ... , a_{30})</math> of 1, 2, ... , 30 such that for <math>m \in \left\{{2, 3, 5}\right\}</math>, m divides <math>a_{n+m} …') |
|||
| Line 2: | Line 2: | ||
There are N permutations <math>(a_{1}, a_{2}, ... , a_{30})</math> of 1, 2, ... , 30 such that for <math>m \in \left\{{2, 3, 5}\right\}</math>, m divides <math>a_{n+m} - a_{n}</math> for all integers n with <math>1 \leq n < n+m \leq 30</math>. Find the remainder when N is divided by 1000. | There are N permutations <math>(a_{1}, a_{2}, ... , a_{30})</math> of 1, 2, ... , 30 such that for <math>m \in \left\{{2, 3, 5}\right\}</math>, m divides <math>a_{n+m} - a_{n}</math> for all integers n with <math>1 \leq n < n+m \leq 30</math>. Find the remainder when N is divided by 1000. | ||
| + | |||
| + | |||
| + | ---- | ||
| + | Solution: | ||
| + | |||
| + | Each position in the 30-position permutation is uniquely defined by an ordered triple <math>(i, j, k)</math>. 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 is <math>\framebox[1.1\width]{144.}</math> | ||
Revision as of 15:11, 31 March 2011
Problem:
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:
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 is ![$\framebox[1.1\width]{144.}$](http://latex.artofproblemsolving.com/6/7/f/67fccc645d89dc131e5f6ba754244c948b5f3ff7.png)
