Problem:
There are N permutations (a1,a2,…,a30) of 1,2,…,30 such that for m∈ {2,3,5},m divides an+m−an for all integers n with 1≤n<n+m≤30. Find the remainder when N is divided by 1000.
Solution:
Consider the sets
S1={1,7,13,19,25},T1={a1,a7,a13,a19,a25},S2={2,8,14,20,26},T2={a2,a8,a14,a20,a26},S3={3,9,15,21,27},T3={a3,a9,a15,a21,a27},S4={4,10,16,22,28},T4={a4,a10,a16,a22,a28},S5={5,11,17,23,29},T5={a5,a11,a17,a23,a29},S6={6,12,18,24,30},T6={a6,a12,a18,a24,a30}.
Because an+2−an is divisible by 2 and an+3−an is divisible by 3,n+6− an=(an+6−an+3)+(an+3−an)=(an+6an+4)+(an+4−an+2)+(an+2−…an) is divisible by both 2 and 3; that is, an+6−an is divisible by 6. Hence for every i with 1≤i≤6,Ti=Sj for some j. Furthermore, because an+2−an is divisible by 2, it follows that {T1,T3,T5}={S1,S3,S5} or {S2,S4,S6}. Hence there are 2⋅6=12 ordered triples (T1,T3,T5) of sets. Assume that (T1,T3,T5)=(Si,Sj,Sk). There are 5!=120 ways to permute the numbers in Si; that is, there are 120 permutations for (a1,a7,a13,a19,a25). Because an+5−an is ivisible by 5, it is true that, modulo 5,
(a1,a7,a13,a19,a25)≡(a21,a27,a3,a9,a15)≡(a11,a17,a23,a29,a5)
Because each of Sj and Sk consists of a complete set of remainders modulo 5, for each permutation (a1,a7,a13,a19,a25), there is exactly one way to arrange the numbers in T3 and T5. Hence there are 12⋅120=1440 ways to choose the subsequence a1,a3,…,a29. Furthermore, because {a1,a3,…,a29}=S1∪S3∪S5 or S2∪S4∪S6,{a1,a3,…,a29} form a complete set of remainders modulo 15. Hence {a2,a4,…,a30} also form a complete set of remainders modulo 15. Since an+15−an is divisible by 15, each (a1,a3,…,a29) determines a unique (a2,a4,…,a30). Thus N=1440 and the required remainder is 440.
The problems on this page are the property of the MAA's American Mathematics Competitions