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+6​an+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