Problema de las olimpiadas matemáticas

Olimpiadas matemáticas

Un amigo mío, Roberto, es doctor ingeniero aeronáutico y profesor, así que lleva una vida matemática interesante. Para él, los aviones no son cosas que vuelan, como para el resto de los mortales, sino cilindros que de metal que se van deformando. Hace mucho tiempo, a raíz de los atentados del 11S, tuvimos una charla sobre si un edificio que se está hundiendo puede girar sobre sí mismo; esencialmente, un edificio es una cosa que está hecha para aguantar su peso en una dirección concreta (la vertical), pero no en otras direcciones, de forma que lo normal es que si lo pones en una postura rara se deshaga por su propio peso. Podría parecer que lo que le gusta a Roberto es retorcer cosas con gente dentro, pero su inclinación natural es más bien evitar este tipo de cosas, por eso es ingeniero en vez de banquero. Bueno, el caso es que hace poco recibí por correo una bonita serie de fotos de un edificio volcado pero no roto, y acordándome de esta charla, se la reenvié.

El comentario de Roberto al ver estas fotos vino a ser algo así como "esto es lo que ocurre cuando haces un edificio con estructura muy dura y cimientos muy blandos". En realidad, sus palabras no fueron éstas, los ingenieros se cuidan mucho de pronunciar la palabra "duro" en vano.

Bueno, el caso es que aprovechando el intercambio de correos, Roberto me contó que había estado haciendo los problemas de la Olimpiada Matemática de 2008, y se le había resistido el tercero:

Demostrar que existen infinitos números n tales que n²+1 tiene un factor primo mayor que 2n+raíz(2n).

Es un problema muy chulo, porque está claro que es verdad, pero todos los ataques directos fallan frustrantemente, así que hay que dar un rodeo. A continuación voy a contar mi solución, que empieza siendo bonita pero acaba de una forma muy fea, la verdad, pero lo mismo quieres dejar de leer en este punto e intentar resolver el problema tú mismo.

Solución

Sea p un primo congruente con 1 módulo 4 lo suficientemente grande (luego veremos que basta que sea mayor que 29). Entonces p=a²+b², donde a y b son primos entre sí (de lo contrario p no sería primo), y por tanto existen dos números u y v tales que a*u+b*v=1. Entonces

p*(u²+v²) = (a²+b²)*(u²+v²) = (a*u+b*v)²+(b*u-a*v)² = 1+(b*u-a*v)²

Así que tomamos n=b*u-a*v y ya tenemos un n tal que n²+1 es un múltiplo de un primo p bastante grande para n. Demostrar que la cota p>2n+raíz(2n) se cumple es un poco feo porque iremos por casos; seguro que hay una forma inteligente de hacer esto rápidamente, pero yo no la he encontrado. Dejémosla por un momento para después y "acabemos" el problema. Para cada p construimos un n como antes. Observemos que todos estos n son diferentes entre sí; precisamente porque cumplen la cota, sabemos que su mayor factor primo es p, de forma que a cada p le corresponde un n diferente. Pero claro, hay infinitos p, de forma que también hay infinitos n como pide el problema.

Bien, pues ya hemos acabado, salvo por el detalle de demostrar la cota, cosa que haremos por casos.

El primer caso que tenemos que considerar es a=1 o b=1 (en el siguiente párrafo veremos por qué). Esto es fácil; si a=1, lo que haré es tomar u=1 y v=0, y por tanto n=b*u-a*v=b, con lo cual la desigualdad es cierta porque p = 1²+b² > 2b+raíz(2b) = 2n+raíz(2n) si b≥3, es decir, si p≥11.

Bien, ya podemos suponer que a>1 y b>1. Empezamos tomando u≅a^-1 (mod b) y v≅b^-1 (mod a), cosa que no podríamos hacer si a=1 o b=1, y por tanto 0≤u<b, 0≤v<a, y a*u+b*v≅1 (mod a*b). Como 0≤a*u+b*v<a*b+b*a=2*a*b, entonces o bien a*u+b*v=1, o bien a*u+b*v=a*b+1. En este segundo caso tiene que ocurrir que o bien u≥b/2 o bien v≥a/2, pero no pueden cumplirse ambas desigualdades, porque a*u+b*v sería demasiado grande; si se cumple la primera, lo que hago es escoger u=mod(a^-1,b)-b, y entonces ya se cumple a*u+b*v=1.

Así pues, ya podemos suponer que |u|≤b/2 y |v|≤a/2, y que u²+v²≤(a²+b²)/4. Pero me hace falta ajustar más.

Para eliminar el caso u=b/2 (los casos u=-b/2, v=a/2, v=-a/2 se hacen igual), tenemos que a*u+b*v=1 implica b*(a+2v)=2, con lo cual b es un divisor de 2. El caso b=1 ya lo vimos antes, así que podemos suponer que b=2. Entonces u=1, v=(1-a)/2, n = b*u-a*v = 2*1-a*(1-a)/2 = (a*a-a+4)/2, p=a²+b²=a²+4, y entonces p>2n+raíz(2n) se reduce a

a²+4 > a²-a+4 + raíz(a²-a+4)

a > raíz(a²-a+4)

a² > a²-a+4

que es cierto para a>4, es decir, para p≥5²+4=29. Por cierto, la desigualdad es muy ajustada; para p=29 sale a=5, b=2, u=1, v=-2, n²+1=29*5=145 luego n=12, y por tanto

29 = p > 2n+raíz(2n) = 24+raíz(24) = 28,8989

Así que ahora podemos suponer que |u|<b/2 y |v|<a/2; como estos cuatro números son enteros, esto quiere decir que |u|≤(b-1)/2 y |v|≤(a-1)/2; pero claro, no puede ocurrir que a y b sean impares a la vez, porque entonces el primo p=a²+b² sería par; luego sabemos que el caso |u|=(b-1)/2 y |v|=(a-1)/2 a la vez no puede ocurrir. Por tanto:

u²+v² ≤ (b-1)²/4 + (a-1)²/4 -1/4

donde el último 1/4 lo quitamos porque acabamos de ver que el caso u²+v²=(b-1)²/4+(a-1)²/4 no puede ocurrir. Como a+b≥raíz(a²+b²),

u²+v² ≤ (b²-2b+1+a²-2a+1-1)/4 ≤

≤ (a²+b²+1-2raiz(a²+b²))/4 = (raíz(a²+b²)-1)²/4

Bien, ya falta poco; recordemos que a²+b²=p y que p*(u²+v²) = n²+1, así que

p*(raíz(p)-1)²/4 = p*(raíz(a²+b²)-1)²/4 > p*(u²+v²) = n²+1

(p-raíz(p))² > 4n²+4 > 4n²

p-raíz(p) > 2n

raíz(p-raíz(p)) > raíz(2n)

p-raíz(p) + raíz(p-raíz(p)) > 2n + raíz(2n)

Como p>p-raíz(p), -raíz(p) + raíz(p-raíz(p)) es un número negativo, y por tanto

p>2n+raíz(2n)

Y vaya chasco de solución; con lo bonitos que eran los dos primeros párrafos...