Problema 1(IMO 2011)

Ya que nadie ha comentado una solución completa de este problema, lo voy a poner:

SPDG $a_1<a_2<a_3<a_4$

Ahora supongamos que $a_3+a_4|s_A=a_1+a_2+a_3+a_4$ entonces tenemos que $a_3+a_4|a_1+a_2$, y entonces tenemos que $a_3+a_4\leq a_1+a_2$ pero por otro lado tenemos que $a_1+a_2<a_3+a_4$ lo cual es una contradicción.

Ahora supongamos que $a_2+a_4|s_A$ y entonces $a_2+a_4|a_3+a_1$, y entonces $a_2+a_4 \leq a_3+a_1$, pero como $a_1<a_2$ y $a_3<a_4$ de nuevo llegamos a una contradicción.

Por lo que tenemos que $n_A \leq 4$, ahora tratemos de encontrar todos los subconjuntos con $n_A=4$, si no hay pues sabemos que no se puede con $4$ pero si hay podemos acabar el problema.

Para $n_A=4$ se tiene que cumplir

$$a_2+a_3|s_A$$

$$a_1+a_4|s_A$$

$$a_1+a_2|s_A$$

$$a_1+a_3|s_A$$

Y como $s_A=a_1+a_2+a_3+a_4$ entonces para las primeras dos se cumple que:

$$a_2+a_3|a_1+a_4$$

$$a_1+a_4|a_2+a_3$$

De lo que concluimos que $a_1+a_4=a_2+a_3$ por lo tanto $s_A=a_1+a_2+a_3+a_4=2(a_2+a_3)$

De las otras dos se tiene que:

$$a_1+a_3|2(a_2+a_3)$$

$$a_1+a_2|2(a_2+a_3)$$

Por lo tanto existen enteros positivos $k_1,k_2$ tales que

$$(a_1+a_3)k_1=2(a_2+a_3)$$

$$(a_1+a_2)k_2=2(a_2+a_3)$$

Si $k_1=1$ entonces tendriamos que $s_A>a_1+a_3=2(a_2+a_3)=s_A$ lo cual es una contradiccion.

Si $k_1=2$ entonces $2a_1+2a_3=2a_2+2a_3$, por lo que $a_1=a_2$ y es una contradicción al hecho de que son distintos.

El mismo argumento es análogo para $k_2$ por lo que $k_1,k_2 \geq 3$

Ahora nos fijamos que como $a_2<a_3$

$$(a_1+a_3)k_1=2(a_2+a_3)<4a_3$$

Por lo que tenemos que

$$k_1<\frac{4a_3}{a_3+a_1}=4-\frac{4a_1}{a_3+a_1}<4$$

Como $3 \leq k_1<4$ entonces $k_1=3$, por lo tanto

$$3(a_1+a_3)=2(a_2+a_3)$$

$$a_3=2a_2-3a_1$$

Sustuimos eso último en la segunda ecuación y tenemos

$$(a_1+a_2)k_2=6a_2-6a_1$$

Reacomodando un poco tenemos que

$$k_2=\frac{6a_2-6a_1}{a_2+a_1}=6-\frac{12a_1}{a_2+a_1}<6$$

Y como $k_2 \geq 3$ entonces $k_2=3,4,5$

Si $k_2=3$ entonces tendriamos $k_2=k_1$ por lo que $a_1+a_3=a_1+a_2$ y tendriamos que $a_2=a_3$ lo cual es una contradicción.

Si $k_2=4$ tendriamos que $4a_1+4a_2=6a_2-6a_1$, entonces $a_2=5a_1$. Recordando que $a_3=2a_2-3a_1$ tenemos que $a_3=7a_1$ y como $a_1+a_4=a_2+a_3$ entonces $a_4=11a_1$ y es fácil verificar que el conjunto $\{a_1,5a_1,7a_1,11a_1\}$ cumple con $n_A=4$, por lo que además demostramos que éste si era el máximo.

Si $k_2=5$ tenemos que $5a_1+5a_2=6a_2-6a_1$, y análogo al caso anterior llegamos al conjunto $\{a_1,11a_1,19a_1,29a_1\}$, que es fácil de verificar.

Como hemos agotado todos los casos, los conjuntos:

$$\{a_1,5a_1,7a_1,11a_1\}$$

$$\{a_1,11a_1,19a_1,29a_1\}$$

son los todos los conjuntos con $n_A$ máxima.

PD

Si encuentran un error de dedo o algun paso que no sea claro me avisan :)

Y por cierto el problema lo veo más clasificado como Álgebra-Números, que como combi, de hecho hay rumores de que en la shorlist viene como Álgebra. De hecho al principio duré como 2 o 3 horas sin éxito por tratar de llegar a algun argumento de Números, pero apenas se me ocurrió usar más argumentos de Álgebra 20 minutos más de trabajo y me salió.

Yo veo muy bien tu solución iwakura_isa. Gracias por compartírnosla.

Creo que tienes razón tal vez su clasificación sea más cercano al álgebra-números que a la combinatoria-números. Voy a meditarlo un poco más, ojalá otras personas nos compartieran su opinión.

Por otro lado, te comparto rápidamente mi solución. Inicio exactamente como tu, probando de la misma manera que $n_A \leq 4$ y que $n_A=4$ sólo se satisface cuando a_1+a_2&|s_A\\ a_1+a_3&|s_A\\ a_1+a_4&=a_2+a_3\\

Y luego hago las cosas poquito diferente, defino $k$ y $h$ como sigue: $k= a_4-a_3=a_2-a_1>0$ y $h=a_3-a_2>0$. Entonces, tendremos que $a_2=a_1+k$, $a_3=a_1+k+h$ y $a_4=2k+h$. Luego substituyendo en las primeras dos condiciones en ($\ref{condiciones}$) y reduciéndolas podemos concluir:

a_1+a_2 | s_A &\Longrightarrow 2a_1+k| 2k+h\\ a_1+a_3| s_A & \Longrightarrow 2a_1+k+h| 2k

Como $2a_1+k+h$ divide a $2k$ y es mayor que $k$ se llega a que $2a_1+k+h=2k$, por lo tanto  $k=2a_1+h$.

Substituyendo esta última identidad en la primera implicación de ($\ref{reduccion}$) llegamos a que $4a_1+ h| 3h$. Y luego $(4a_1+h)\ell =3h$ con $\ell =1,2$, pues con $\ell \geq 3$ es imposible ya que $(4a_1+h)\ell$ sería mayor que $3h$.

Con esto terminaría la prueba de forma idéntica. Cada caso $\ell=1$ y $\ell=2$ me da las dos familias de soluciones.

Muchas gracias nuevamente por compartir tu solución y espero que te agrade la mía. Al igual que tu también necesité pasar por el uso de desigualdades ($\ell <3$) para limitar los casos, y eso es muy típico del álgebra.  Ciertamente es más álgebra que combinatoria.