Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2011 AIME II Problems/Problem 14

Revision as of 16:54, 31 March 2011 by Pkustar (talk | contribs)

Problem:

There are N permutations $(a_{1}, a_{2}, ... , a_{30})$ of 1, 2, ... , 30 such that for $m \in \left\{{2, 3, 5}\right\}$, m divides $a_{n+m} - a_{n}$ for all integers n with $1 \leq n < n+m \leq 30$. Find the remainder when N is divided by 1000.


Solution:

Each position in the 30-position permutation is uniquely defined by an ordered triple $(i, j, k)$. 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.}$

Umm...just asking, but istn the remainder when 1440 is divided by 1000 $\framebox[1.1\width]{440.}$?

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2011_AIME_II_Problems/Problem_14&oldid=37946"