Determine with proof, the number of permutations $a_1,a_2,a_3,...,a_{2016}$ of $1,2,3,...,2016$ such that the value of $|a_i-i|$ is fixed for all $i=1,2,3,...,2016$, and its value is an integer multiple of $3$.
Problem
Source: Indonesian MO 2016 Problem #8
Tags: permutations, combinatorics, number theory
03.05.2017 16:12
Misread, sorry
03.05.2017 19:43
mbwoz, I think you may have misread the problem. It says that $|a_i-i|$ is fixed for all $i$, and it follows that for any given value of $i$ there is at most one possible permutation: $$i+1,i+2,i+3,\dots,2i,1,2,3,\dots ,i,3i+1,3i+2,3i+3,\dots ,4i,2i+1,2i+2,2i+3,\dots ,3i, \dots \dots$$ The problem is equivalent to finding the number of integers $n$ such that $$2016\equiv k\in \{3n+1,3n+2,\dots ,6n\} \mod 6n$$
03.05.2017 20:18
mbwoz wrote: To solve this problem we should start with $|a_{i} - i|$. This has to be a multiple of $3$ so it is enough to talk about remainders of $a_{i}$ and $i$. [.....] . So in total we get $(672!)^3$ combinations. $(672!)^3$ is the number of permutation where $|a_{i} - i|$ is multiple of $3$. but according to the problem we should have $|a_{i} - i|$ fixed. i understand that we should have $|a_{i} - i|=3k$ where $k$ is fixed. if this case we are looking for $|A_k|$ where $A_k=${$permutation$ $(a_i)$ $|$ $|a_{i} - i|=3k$}. $|A_k|=1$ if $6k$ divide $2016$, if not $|A_k|=0$ we have $a_i=3k+i$ or $i-3k$ for $i=1,2,...,3k$ we have $a_i=3k+i$ (one choice, $a_i=3k+1,3k+2,...,6k$) for $i=3k+1,3k+2,...,3k+3k$ we should have $a_i=i-3k$ (one choice, $a_i=1,2,...,3k$) because it's the only way to have $a_i\le 3k$ so the first $6k-elements$ of the permutation are $3k+1,3k+2,3k+3...,6k$ follows by $1,2,3,....,3k$ by induction, the $n-th$ $6k-elements$ of the permutation are $3k+1+6k(n-1),3k+2+6k(n-1),3k+3+6k(n-1)...,6k+6k(n-1)$ follows by $1+6k(n-1),2+6k(n-1),3+6k(n-1),....,3k+6k(n-1)$ then we should have $6k$ divide $2016$