Selection tests for the International Mathematical Olympiad 2013

Assume that it is possible to place the integers $1,2,\dots ,2012$ in a circle in such a way that the 2012 products of adjacent pairs of numbers leave pairwise distinct remainders when divided by 2013. Let $a_1,a_2,\dots ,a_{2012}$ be such a reordering of the integers $1,2,\dots ,2012$ on the circle.

Because $2013=3\times 11\times 61$, a number is a multiple of $3$ or $11$ or $61$ if and only if its remainder when divided by $2013$ is a multiple of $3$ or $11$ or $61$.

By the pigeonhole principle, there are at least two adjacent numbers in the list $a_1,a_2,\dots ,a_{2012}$ which are not multiples of $3$. Make this list starting from these two adjacent numbers and consider the list $b_1,b_2,\dots ,b_{2012}$ of their products, where $b_i=a_i\cdot a_{i+1}$, for $i=1,\dots ,2012$ with $a_{2013}=a_1$.

Consider $a_{i_1},a_{i_2},\dots ,a_{i_{670}}$, all the multiples of $3$ with $2<i_1<i_2<\cdots <i_{670}$. It is clear that $b_{i_1},b_{i_2},\dots ,b_{i_{670}}$ are all multiples of $3$ and that $b_{i_1-1},b_{i_2-1},\dots ,b_{i_{670}-1}$ are also all multiples of $3$. So their remainders when divided by $2013$ are all multiples of $3$. But there are only $671$ different multiples of $3$ between $0$ and $2012$ included. Therefore $i_{j+1}=i_j+1$ for all $j=1,\dots ,669$. This means that the multiples of $3$ in the list $a_1,a_2,\dots ,a_{2012}$ form a block and are not separated by any non-multiple of $3$.

In a similar way we prove that multiples of $11$ form a block in this list and that multiples of $61$ form also a block in this list. But since there are common multiples of $3$ and $11$, their blocks must be connected to each other. For the same reason the $3$ blocks must be connected by pairs to each other.

But, in each block, there are numbers which are in none of the two other blocks, for example there are multiples of $3$ which are neither multiples of $11$ nor multiples of $61$ like $3,6,9$, and the same thing happens for $11$ and $61$. So, these numbers are in the middle of each of the blocks and make the blocks intersecting only in their sides. There are also numbers which are not multiples of any of these $3$ numbers, like $1,2,4$. So, these numbers will prevent two of the three blocks to intersect, and here is the contradiction.

Hence, it is not possible to place the integers $1,2,\dots ,2012$ in a circle under the given condition.