IMO 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 a circle such that the product of any two neighbours is of the form \(x^2+x+k\) for some positive integer \(x\).

Official text of the problem. Official problem paper (PDF)

Solution

Write \(F(x)=x^2+x+k\). We prove the stronger statement in which \(x\) is allowed to be a nonnegative integer. Call two distinct primes \(a,b\) compatible if \(ab=F(x)\) for some integer \(x\geq0\).

We first establish two facts: a prime \(p\) has at most two compatible primes smaller than itself, and if there are two, they are compatible with each other.

Suppose distinct primes \(a,b<p\) satisfy \[ pa=F(u),\qquad pb=F(v),\qquad u,v\geq0. \] Since \(k>0\) and \(pa,pb<p^2\), we have \(u,v<p\). Also \(u\neq v\), because \(a\neq b\). Subtracting gives \[ p(a-b)=F(u)-F(v)=(u-v)(u+v+1). \] As \(p\) is prime and \(0<|u-v|<p\), it follows that \(p\mid u+v+1\). But \[ 1\leq u+v+1\leq 2p-1, \] so \[ u+v+1=p. \tag{1} \]

If a third prime \(c<p\), distinct from \(a,b\), were compatible with \(p\), write \(pc=F(w)\), where \(0\leq w<p\). Applying the same argument to \(a,c\) gives \(u+w+1=p\). Together with (1), this yields \(w=v\), hence \(c=b\), a contradiction. Thus there are at most two smaller compatible primes.

Furthermore, dividing the subtraction identity by \(p\) and using (1), we obtain \[ a-b=u-v, \] and consequently \[ 2u+1=p+a-b. \] Therefore \[ \begin{aligned} F(u-a) &=F(u)-a(2u+1)+a^2\\ &=pa-a(p+a-b)+a^2\\ &=ab. \end{aligned} \] The integer \(u-a\) might be negative, but \[ F(t)=F(-t-1) \] for every integer \(t\). One of \(t\) and \(-t-1\) is nonnegative, so \(ab=F(x)\) for some integer \(x\geq0\). This proves that \(a,b\) are compatible.

We now prove the stronger statement by induction on \(n=|S|\). For \(n\leq3\), all circular orderings are equivalent up to rotation and reflection, so the assertion holds.

Let \(n\geq4\), and assume the assertion holds for sets of \(n-1\) odd primes. If no admissible arrangement exists, there is nothing to prove. Otherwise, let \(p\) be the largest element of \(S\), and let \(a,b\) be its neighbours in an admissible arrangement.

Both \(a,b\) are smaller than \(p\) and compatible with it. By the first fact proved above, they are the only possible neighbours of \(p\); thus every admissible arrangement has \(a,b\) as the neighbours of \(p\).

Delete \(p\) from any such arrangement and join its former neighbours \(a,b\). By the second fact, \(a,b\) are compatible, so this produces an admissible arrangement of \(S\setminus\{p\}\). By induction, that smaller arrangement is unique up to rotation and reflection.

The original arrangement is recovered uniquely by inserting \(p\) between the adjacent elements \(a,b\). Hence the arrangement of \(S\) is also unique up to rotation and reflection.

This proves uniqueness even when nonnegative values of \(x\) are allowed, and therefore proves the required statement for positive values of \(x\). \(\square\)

The solution was checked against the official IMO shortlist solutions.