La combinatoria de prueba (cualquier conjunto de 16 números del 1 al 100 contiene reiteradas sumas)

Question

Supongamos que $A$ es un conjunto de 16 de distintos números naturales y que $1\leq p\leq100$ por cada $p$$A $.

Demostrar que $A$ contiene 4 números diferentes $a$, $b$, $c$, y $d$, de tal manera que $a+b=c+d$.

Answer 1

Este es el número 17 de la introducción de los problemas de la sección en el libro 102 Problemas de Combinatoria de la la formación de los Estados Unidos de la OMI equipo por Titu Andreescu y Zuming Feng.

Aquí es una paráfrasis de su solución.

Hay ${16\choose 2}=120$ pares de números de $A$. Desde las diferencias absolutas en el rango de 1 a 99, debe haber dos pares diferentes $\{a,c\}$ $\{d,b\}$ $a-c=d-b$ y, por tanto,$a+b=c+d$.

El problema es que $\{a,b,c,d\}$ no puede ser distinto. Bien, ¿qué podría salir mal? Podemos acabar con pares como $\{7,6\}$$\{6,5\}$. En este caso, nos puede llamar el número 6 de "malo". En general, llamamos a $a\in A$ un mal número si existen $a_1<a<a_2\in A$ $a_2-a=a-a_1$ .

Tenga en cuenta que si $a$ es malo para los dos tipos de pares de pares, entonces tenemos una solución. Es decir, si $a_1<a<a_2\in A$, de modo que $a_2-a=a-a_1$ y $a_3<a<a_4\in A$ , de modo que $a_4-a=a-a_3$, luego tenemos a $a_1+a_2=a_3+a_4$. Se puede comprobar que $a_1,a_2,a_3,a_4$ realmente son diferentes en este caso.

Así que el único verdadero problema son pares de números en $A$ cuyo punto medio $a$ también pertenece a $A$, de tal manera que ningún otro par tiene el mismo punto medio. Hay en la mayoría de los 16 de estos molestos pares, por lo que hay $120-16=104$ pares a la izquierda. Aplicando el principio del palomar a este conjunto reducido da la solución.

Answer 2

Nota: Esta solución es que el problema originalmente planteado, sin el requisito de que $a,b,c$, e $d$ ser distintos. Ese requisito lo hace mucho más difícil, y voy a tener que pensar un poco más si tengo tiempo.

(Estoy asumiendo que te refieres a que si $p\in A$,$1\le p\le 100$.) Aquí está una extensa pista.

Deje $D=\{|a-b|:a,b\in A\text{ and }a\ne b\}$, el conjunto de par de diferencias.

1. Cuántos pares de $\{a,b\}\subseteq A$ hay con $a\ne b$?

2. Si $1\le a\le 100$ por cada $a\in A$, con lo que el número podría ser en $D$? ¿Cuántos de esos números hay?

3. Utilizar el principio del palomar para encontrar $a,b,c,d\in A$ tal que $a-c=d-b$.