63rd International Mathematical Olympiad - IMO 2022 | Problem 3 - Solution - 13 July 2022

Problem 3

Let k be a positive integer and let S be a finite set of odd prime numbers. Prove that there is at most one way (up to rotation and reflection) to place the elements of S around the circle such that the product of any two neighbours is of the form x²+x+k for some positive integer k.

Solution

We'll prove this by induction on $|S|$ on the relaxed problem: we'll prove the statement such that product of any two neighbors is of the form $x^2 + x + k$ for some integer $x$ , which proves the original problem. The result is clearly true for $|S| \le 3$ . Now, assume that the result is true for any $|S| < n$ , where $n \ge 4$ . We'll prove that this is true for $|S| = n$ . Indeed, suppose that there exists a configuration for $S$ with $|S| = n$ , otherwise we are done. Call a number $m$ of the form $m = x^2 + x + k$ for some $x \in \mathbb{Z}$ as nice. Now, take the largest prime $P$ on this set $S$ . By assumption, there exists distinct primes $Q, R < P$ such that
$PQ = x^2 + x + k \ \text{and} \ PR = y^2 + y + k$

Claim 01. $QR$ is nice.
Proof. By maximality of $P$ , we have $x, y < P$ and furthermore

$P \mid x^2 - y^2 + x - y = (x - y)(x + y + 1) \implies x \equiv y \pmod{P} \ \text{or} \ x + y + 1 \equiv 0 \pmod{P}$ As $x \not= y$ , we conclude that $x + y = P - 1$ . Now, we have
$2(k - xy) \equiv (x + y)^2 - 2xy + (x + y) + 2k \equiv (x^2 + x + k) + (y^2 + y + k) \equiv 0 \pmod{P}$ and since $P$ is odd, then $xy \equiv k \pmod{P}$ . Write $xy = k + Pz$ for some $z \in \mathbb{Z}$ .
Therefore, we have
$\begin{align*} QR &= \frac{(PQ)(PR)}{P^2} \\ &= \frac{(x^2 + x + k)(y^2 + y + k)}{P^2} = \frac{(x^2 + x + xy - Pz)(y^2 + y + xy - Pz)}{P^2} = \frac{(Px - Pz)(Py - Pz)}{P^2} \\ &= (x - z)(y - z) = xy - z(x + y) + z^2 = k + Pz - z(x + y) + z^2 = k + z + z^2 \end{align*}$ We thus conclude that $QR$ has to be nice as well.

The above claim implies that we can construct a valid configuration with $|S| = n - 1$ assuming that a valid configuration with $|S| = n$ exists; and by inductive hypothesis, there exists a unique valid configuration for $|S| = n - 1$ , by deleting the largest prime. Therefore, the valid configuration for $|S| = n$ can only be obtained by inserting $P$ between any two consecutive primes in the configuration for $|S| = n - 1$ . Now, suppose there are more than one ways to insert the prime, then there exists distinct $a,b,c \in S$ and $x,y,z \in \mathbb{N}$ such that
$\begin{align*} aP &= x^2 + x + k \\ bP &= y^2 + y + k \\ cP &= z^2 + z + k \end{align*}$ However, as $a,b,c < P$ , we have $x,y,z < P$ as well. Furthermore, as $a,b,c$ are distinct, then $x,y,z$ are distinct as well. Therefore, $P \mid x + y + 1, y + z + 1 \implies x + y = P - 1 = y + z \implies x = z$ , a contradiction. Therefore, the configuration for $|S| = n$ has to be unique as well, and hence our original result holds.