OFO 2018 Problema 1

[ésta]

Determinar el menor entero positivo $N$ que cumple la siguiente propiedad:
"Es imposible dividir los números $1,2,3,\ldots,2N$ en $N$ parejas de manera que las sumas de los números en cada pareja sean $N$ números primos distintos."
(Para el valor hallado, justificar por qué es imposible formar las parejas, y mostrar que si $N$ es menor que ese valor entonces sí es posible.)

[Matías V5]

Solución oficial:

[enigma1234]

Spoiler: mostrar

Veamos que para N menor que 7 si se puede dividir en dichas parejas
N=1:(1,2)
N=2:(1,2)(3,4)
N=3:(1,2)(3,4)(5,6)
N=4:(1,6)(2,3)(4,7)(5,8)
N=5:(1,6)(2,3)(4,7)(5,8)(9,10)
N=6:(1,6)(2,3)(4,7)(5,8)(9,10)(11,12)
Que claramente cumplen.
Ahora veamos que para N=7 no se puede dividir. Supongamos que si se puede dividir en ese tipo de parejas. Sean $p_1,p_2,...,p_7$ las sumas de cada pareja en orden creciente(que por lo supuesto son primos distintos).Dados que son primos y son sumas de dos números distintos entre 1 y 14 entonces $ p_1< p_2<....<p_7 \leq 23$. Entonces $p_1+p_2+...+p_7 \leq 23+19+17+13+11+7+5=95$ Pero como $p_1+p_2+...+p_7=1+2+3+...+14=105$ lo cual es una contradicción. Por lo tanto N=7 es el mínimo que cumple lo pedido.

[SantiClemente]

Spoiler: mostrar

El menor $N$ que cumple la propiedad es 7.
Con $N=7$, tenemos disponibles los números del $1$ al $14$, con los que podemos formar parejas que sumen los siguientes números primos: $3; 5; 7; 11; 13; 17; 19$ y $23$. Esos 8 números suman $98$, y no nos olvidemos que teniendo 7 parejas y 8 posibles primos, hay uno de ellos que no vamos a usar, por lo que obtendremos 7 números primos que suman como máximo $95$. Sin embargo, los números del $1$ al $14$ suman $105$, y no importa cómo los distribuyamos, no obtendremos un grupo de 7 primos que sumen $95$ o menos.

Para ver que con $N<7$ sí se puede realizar la distribución, simplemente buscamos los ejemplos:

$N=1$
$1+2=3$

$N=2$
$1+2=3$
$3+4=7$

$N=3$
$1+2=3$
$3+4=7$
$5+6=11$

$N=4$
$2+3=5$
$1+6=7$
$4+7=11$
$5+8=13$

$N=5$
$2+3=5$
$1+6=7$
$4+7=11$
$5+8=13$
$9+10=19$

$N=6$
$2+3=5$
$1+6=7$
$4+7=11$
$5+8=13$
$9+10=19$
$11+12=23$