Para cualquier conjunto de cuatro enteros positivos distintos se denota la suma con . Sea el número de parejas con para las cuales divide a . Encontrar todos los conjuntos de cuatro enteros positivos distintos para los cuales se alcanza el mayor valor posible de .
Enviado por iwakura_isa el 6 de Agosto de 2011 - 10:05.
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$
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:
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.
de cuatro enteros positivos distintos se denota la suma 
con 
. Sea 
el número de parejas 
con 
para las cuales 
divide a 
de cuatro enteros positivos distintos para los cuales se alcanza el mayor valor posible de
Ya que nadie ha comentado una
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
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:
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.