Problem 1 from the IMO 2009

Here is Problem 1 from the IMO 2009:

Let $n$ be a positive integer and let $a_{1}, ..., a_{k},$ $(k ≥ 2),$ be distinct integers in the set $\{1, ..., n\}$ such that $n$ divides $a_{i}(a_{i+1} - 1)$ for $i = 1, \cdots, k - 1.$ Prove that $n$ does not divide $a_{k}(a_{1} - 1).$

Solution

Set for simplicity $a = a_{1}$ and $b = a_{2},$ $a \ne b$ and both are less than $n.$

Thus $n|a(b - 1)$ meaning that there are $s$ and $t,$ $st = n,$ such that $s|a$ and $t|(b - 1).$ Since both $a$ and $b$ are less than $n,$ neither $s$ or $t$ may equal $1,$ meaning that both are non-trivial factors of $n.$

Let first $k = 2,$ and assume that $n|b(a - 1).$ No non-trivial factor of $t$ may divide $b,$ and no non-trivial factor of $s$ may divide $a - 1,$ implying that $s|b.$ We are therefore in a position to apply the Chinese Remainder Theorem:

$\begin{align} b\equiv 1\space(\mbox{mod}\space t), \\ b\equiv 0\space(\mbox{mod}\space s). \end{align}$

The theorem tells us that there is a unique solution modulo $\mbox{lcd}(s, t) = n.$ However, due to the symmetry in the conditions for $a$ and $b,$ we also have

$\begin{align} a\equiv 1\space(\mbox{mod}\space t), \\ a\equiv 0\space(\mbox{mod}\space s). \end{align}$

which contradicts the assumption that $a$ and $b$ are distinct.

For $k = 3,$ we are given that $n|b(c - 1)$ where $c = a_{3}.$ Assume, as before, $n|c(a - 1).$

There are $s$ and $t$ different from $1$ and $n$ such that $s|a$ and $t|(b - 1).$ No non-trivial factor of $t$ may divide $b.$ From $n|b(c - 1)$ it then follows that $t|(c - 1)$. If not $s$ itself, then one of its factors, say, $s_{0}$ divides $b:$ $s_{0}|b,$ $s_{1}t|(c - 1)$, where $s = s_{0}s_{1}$.

Similarly, $n|c(a - 1)$ implies that $\sigma_{0}|c$ and $\sigma_{1}s_{1}t|(a - 1)$, where $\sigma_{0}\sigma_{1} = s_{0}.$ It's now one of the two: either $\sigma_{1}s_{1} = 1$ or not. In the former case, the Chinese Remainder theorem leads to a contradiction. In the latter case, there appears a non-trivial factor common to both $a$ and and $a - 1.$ Again a contradiction.

For greater $k,$ we always have $t|a_{i+1} - 1.$ As we progress from $1$ to larger $i,$ additional factors may be borrowed from $s.$ If this happens, then $a$ and $a - 1$ will have shown to have common factors. Otherwise a contradiction is reached via the Chinese Remainder theorem.

A shorter and a more formal solution was posted at the artofproblemsolving.com forum by mathman145.

We know that $n$ divides $a_{i}(a_{i + 1} - 1), i = 1, \cdots, k - 1.$ The condition is equivalent to saying that

$\begin{align} a_{k}a_{k - 1} \equiv a_{k - 1}\space(\mbox{mod}\space n), \\ a_{k}a_{k - 1}a_{k - 2} \equiv a_{k - 1}a_{k - 2} \equiv a_{k - 2}\space(\mbox{mod}\space n) \\ a_{k}a_{k - 1}a_{k - 2}a_{k - 3} \equiv a_{k - 1}a_{k - 2}a_{k - 3} \equiv a_{k - 2}a_{k - 3} \equiv a_{k - 3}\space(\mbox{mod}\space n) \\ \cdots \end{align}$

so that

$a_{k}a_{k - 1}a_{k - 2}a_{k - 3} ... a_{1} = a_{1}\space(\mbox{mod}\space n).$

Now assume that $a_{k}(a_{1} - 1)$ is divisible by $n.$ Then, similarly to the above

$a_{1}a_{k}a_{k - 1}a_{k - 2}a_{k - 3} ... a_{2} \equiv a_{2}\space(\mbox{mod}\space n),$

implying that $a_{1} = a_{2}\space(\mbox{mod}\space n)$ which is impossible for two distinct positive integers both less than $n.$

Note

This page has been created in 2009 right after the problems of the 50th IMO became public. Since then I came into possession of three books (listed below) that deal with that and other problems of that IMO. The dedicated book offers five solutions, each with remarks on different ways to proceed at different of its stages. This book and the Compendium offer two alternative formulations markedly different from the official one. The original formulation proposed by the Australian team was highlighted by the online version of "Spiegel" under the headlines "Formula against embarrassing presents" and "Get rid of ugly items. See that online: https://www.spiegel.de/wissenschaft/mensch/0,1518,636670,00.html and https://www.spiegel.de/wissenschaft/mensch/0,1518,636682,00.html. Here it is:

A social club has n members. They have the membership numbers 1, 2, ..., n, respectively. From time to time members send presents to other members, including items they have already received as presents from other members. In order to avoid the embarrassing situation that a member might receive a present that he or she has sent to other members, the club adds the following rule to its statues at one of its annual meetings:

"A member with membership number a is permitted to send a present to a member with membership number b if and only if a(b-1) is a multiple of n."

Prove that, if each member follows this rule, none will receive a present from another member that he or she has already sent to other members.

References

Dusan Djukić et alThe IMO Compendium: A Collection of Problems Suggested for The International Mathematical Olympiads: 1959-2009, Springer; 2nd Edition. edition (May 16, 2011)
Hans-Dietrich Gronau et al, 50th IMO - 50 Years of International Mathematical Olympiad, Springer, 2011
Xiong Bin, Lee Peng Yee, Mathematical Olympiads in China (2009-2010). Problems and Solutions, World Scientific, 2013

71536488