IMO Problem Shortlist

Solution 1. Suppose there is an edge from $v_i$ to $v_j$. Then $i(j-1)=ij-i=kn$ for some integer $k$, which implies $i=ij-kn$. If $\gcd (i,n)=d$ and $\gcd (j,n)=e$, then $e$ divides $ij-kn=i$ and thus $e$ also divides $d$. Hence, if there is an edge from $v_i$ to $v_j$, then $\gcd (j,n)\mid \gcd (i,n)$. If there is a cycle in $G$, say $v_{i_1}\to v_{i_2}\to \cdots \to v_{i_r}\to v_{i_1}$, then we have $$\gcd \left(i_1,n\right)\left|\gcd \left(i_r,n\right)\right|\gcd \left(i_{r-1},n\right)|\dots |\gcd \left(i_2,n\right)\mid \gcd \left(i_1,n\right)$$ which implies that all these greatest common divisors must be equal, say be equal to $t$. Now we pick any of the $i_k$, without loss of generality let it be $i_1$. Then $i_r(i_1-1)$ is a multiple of $n$ and hence also (by dividing by $t$), $i_1-1$ is a multiple of $\frac{n}{t}$. Since $i_1$ and $i_1-1$ are relatively prime, also $t$ and $\frac{n}{t}$ are relatively prime. So, by the Chinese remainder theorem, the value of $i_1$ is uniquely determined modulo $n=t\cdot \frac{n}{t}$ by the value of $t$. But, as $i_1$ was chosen arbitrarily among the $i_k$, this implies that all the $i_k$ have to be equal, a contradiction.

Solution 2. If $a,b,c$ are integers such that $ab-a$ and $bc-b$ are multiples of $n$, then also $ac-a=a(bc-b)+(ab-a)-(ab-a)c$ is a multiple of $n$. This implies that if there is an edge from $v_a$ to $v_b$ and an edge from $v_b$ to $v_c$, then there also must be an edge from $v_a$ to $v_c$. Therefore, if there are any cycles at all, the smallest cycle must have length 2. But suppose the vertices $v_a$ and $v_b$ form such a cycle, i.e., $ab-a$ and $ab-b$ are both multiples of $n$. Then $a-b$ is also a multiple of $n$, which can only happen if $a=b$, which is impossible.

Solution 3. Suppose there was a cycle $v_{i_1}\to v_{i_2}\to \cdots \to v_{i_r}\to v_{i_1}$. Then $i_1(i_2-1)$ is a multiple of $n$, i.e., $i_1\equiv i_1{i}_2\mathrm{mod}n$. Continuing in this manner, we get $i_1\equiv i_1{i}_2\equiv i_1{i}_2{i}_3\equiv i_1{i}_2{i}_3\dots i_r\mathrm{mod}n$. But the same holds for all $i_k$, i.e., $i_k\equiv i_1{i}_2{i}_3\dots i_r\mathrm{mod}n$. Hence $i_1\equiv i_2\equiv \cdots \equiv i_r\mathrm{mod}n$, which means $i_1=i_2=\cdots =i_r$, a contradiction.

Solution 4. Let $n=k$ be the smallest value of $n$ for which the corresponding graph has a cycle. We show that $k$ is a prime power. If $k$ is not a prime power, it can be written as a product $k=de$ of relatively prime integers greater than 1. Reducing all the numbers modulo $d$ yields a single vertex or a cycle in the corresponding graph on $d$ vertices, because if $a(b-1)\equiv 0\mathrm{mod}k$ then this equation also holds modulo $d$. But since the graph on $d$ vertices has no cycles, by the minimality of $k$, we must have that all the indices of the cycle are congruent modulo $d$. The same holds modulo $e$ and hence also modulo $k=de$. But then all the indices are equal, which is a contradiction. Thus $k$ must be a prime power $k=p^m$. There are no edges ending at $v_k$, so $v_k$ is not contained in any cycle. All edges not starting at $v_k$ end at a vertex belonging to a non-multiple of $p$, and all edges starting at a non-multiple of $p$ must end at $v_1$. But there is no edge starting at $v_1$. Hence there is no cycle.

Solution 5. Suppose there was a cycle $v_{i_1}\to v_{i_2}\to \cdots \to v_{i_r}\to v_{i_1}$. Let $q=p^m$ be a prime power dividing $n$. We claim that either $i_1\equiv i_2\equiv \cdots \equiv i_r\equiv 0\mathrm{mod}q$ or $i_1\equiv i_2\equiv \cdots \equiv i_r\equiv 1\mathrm{mod}q$. Suppose that there is an $i_s$ not divisible by $q$. Then, as $i_s(i_{s+1}-1)$ is a multiple of $q$, $i_{s+1}\equiv 1\mathrm{mod}p$. Similarly, we conclude $i_{s+2}\equiv 1\mathrm{mod}p$ and so on. So none of the labels is divisible by $p$, but since $i_s(i_{s+1}-1)$ is a multiple of $q=p^m$ for all $s$, all $i_{s+1}$ are congruent to 1 modulo $q$. This proves the claim. Now, as all the labels are congruent modulo all the prime powers dividing $n$, they must all be equal by the Chinese remainder theorem. This is a contradiction.