IMO 2022 - P3

[Matías V5]

Sea $k$ un entero positivo y sea $S$ un conjunto finito de números primos impares. Demostrar que existe a lo sumo una manera (sin contar rotaciones y reflexiones) de colocar los elementos de $S$ alrededor de una circunferencia de modo que cada producto de dos números que son vecinos sea de la forma $x^2 + x + k$ para algún entero positivo $x$.

[enigma1234]

Solución:

Spoiler: mostrar

Probaremos el problema permitiendo que $x$ sea entero no negativo. Claramente esto implica el problema.

Sea $S$
Lema 1: Sea $p$ un primo impar. Sea $A_p$ el conjunto de primos impares $q$ menores a $p$ tal que $pq=x^2+x+k$ para algún entero no negativo $x$.
Luego tenemos que $|A_p|\leq 2$.

Spoiler: mostrar

Supongamos que $p_1,p_2,p_3$ son 3 primos distintos que pertenecen a $A$, con:
$$p_ip=x_i^2+x_i+k \text{, $x_i\in \mathbb{Z}_0^+$ $\forall i=\{1,2,3\}$}$$

Entonces como: $$p^2\geq pp_i=x_i^2+x_i+k >x_i^2$$
Obtenemos $0\leq x_i<p$ $\forall i=\{1,2,3\}$, al ser enteros, esto es $0\leq x_i\leq p-1$ $\forall i=\{1,2,3\}$.

Restando obtenemos: $p\mid p(p_1-p_2)=x_1^2+x_1-x_2^2-x_2=(x_1-x_2)(x_1+x_2+1)\to p\mid x_1-x_2 \vee p\mid x_1+x_2+1$.

Como los $p_i$ son distintos, claramente los $x_i$ también lo son. Luego $x_1-x_2\neq 0$ y $-p<x_1-x_2<p$, con lo que $p\nmid x_1-x_2$.

Luego $p\mid x_1+x_2+1$ y tenemos que $1\leq x_1+x_2+1\leq p-1+p-1+1=2p-1$, con lo que claramente tenemos que $x_1+x_2+1=p$.

Haciendo un razonamiento similar con $p_1,p_3$ obtendremos $x_2=x_3\to p_2=p_3$ lo cual es una contradicción a lo supuesto.

Por lo tanto $|A_p|\leq 2$.

Lema 2: Sean $p,q,r$ primos impares distintos tales que $p>q,r$ y:

$ pq=x^2+x+k, pr=y^2+y+k \text{ para algunos enteros no negativos $x,y$}$

Luego $qr=z^2+z+k$ para algún entero no negativo $z$.

Spoiler: mostrar

Haciendo el mismo procedimiento que en el Lema 1, obtenemos que $x+y+1=p$. Y como $p(q-r)=(x-y)(x+y+1)$ entonces $x-y=q-r$.

Por lo tanto $x=\frac{p+q-r-1}{2}$ y $y=\frac{p+r-q-1}{2}$. Reemplazando $x$ en $x^2+x+k=pq$ tenemos que:
$$k=pq-x^2-x=pq-\frac{p+q-r-1}{2}\times \frac{p+q-r+1}{2}=pq-\frac{(p+q-r)^2-1}{4}=\frac{2pq+2pr+2qr-p^2-q^2-r^2}{4}$$
Al ser la expresión de $k$ simétrica, nos dice que cambiando el orden de $p,q,r$ se cumple lo mismo, es decir:
$$k=qr-\left(\frac{q+r-p-1}{2}\right)^2-\left(\frac{q+r-p-1}{2}\right)$$

Como $p,q,r$ son primos impares entonces $a=\frac{q+r-p-1}{2}\in\mathbb{Z}$ y cumple que $qr=a^2+a+k$.
Luego como $a^2+a=a(a+1)=(-1-a)^2+(-1-a)$ y $\min\{a,-1-a\}\geq 0$, luego $z=\min\{a,-1-a\}$ cumple lo pedido.

Ahora en el nuevo problema (permitiendo que $x$ sea entero no negativo) veamos por inducción en $|S|$.

Para $|S|\leq 3$ es claro que se cumple lo pedido.

Ahora supongamos que el enunciado es cierto para $|S|=n\geq 3$. Probaremos para $S$ tal que $|S|=n+1$.
Supongamos que para dicho $S$ existen dos posibles arreglos. Sea $p$ el mayor elemento de $S$, y los primos en los arreglos están en el siguiente orden:

$p,p_1,p_2,\dots,p_n,p$
$p,q_1,q_2,\dots, q_n,p$

donde $S\setminus\{p\}=\{p_1,p_2,\dots,p_n\}=\{q_1,q_2,\dots,q_n\}$.
Como $p$ es el máximo, y $p_1,p_n,q_1,q_n\in A_p$, $p_1\neq p_n,q_1\neq q_n$ entonces por el Lema 1 tenemos que $\{p_1,p_n\}=\{q_1,q_n\}$. Sin perdida de generalidad digamos que $p_1=q_1, p_n=q_n$.

Por el Lema 2 existe un entero no negativo $a$ tales que $p_1p_n=q_1q_n=a^2+a+k$. Por lo tanto podemos "eliminar" $p$ de ambas circunferencias y nos quedarían 2 arreglos validos para $S\setminus\{p\}$:

$p_1,p_2,\dots,p_n,p_1$
$q_1=p_1,q_2,\dots, q_n=p_n,q_1=p_1$

Pero por la hipótesis hay máximo un posible arreglo con lo que $q_j=p_j\forall$ $1\leq j\leq n$. Entonces los 2 arreglos para $S$ son necesariamente iguales, completando la inducción y el problema.