Elige 8 enteros distintos de {1,2,…,16,17}{1,2,…,16,17}\{1, 2,\dots,16,17\}. Muestre que los ocho contienen al menos tres pares con una diferencia común para _cualquier_ opción.

Este problema es de la Olimpiada Nacional de Canadá de 1999. Estoy atascado tratando de probar la primera parte usando el principio del casillero. ¿Hay algún refinamiento que permita que se use de manera más aguda, o hay algún uso inteligente de la paridad que probaría la parte 1? u otro enfoque?

En lo que respecta a la parte 2, imagino que una solución surgirá naturalmente de la solución a la parte 1.

Suponer$a_1,a_2,\dots,a_8$son ocho enteros distintos de$\{1,2,\dots,16,17\}$. Demuestra que hay un entero$k>0$tal que la ecuación

$a_i−a_j=k \tag{1}$

tiene al menos tres soluciones diferentes.

---

Además, encuentre un conjunto específico de 7 enteros distintos de$\{1,2,\dots,16,17\}$tal que la ecuación$a_i−a_j=k$no tiene tres soluciones distintas para ninguna$k>0$.

Supongamos que el seleccionado$a_n$se ordenan para que$a_1<a_2<\dots<a_8$. Defina las brechas 1 entre términos sucesivos como

$\alpha_n = a_{n+1}-a_n,\: 1 \le n \le 7 \tag{2}$

Claramente estos siete$\alpha_k$puede sumar como máximo 16. Si tres de estos 1-huecos tienen el mismo valor,$k$, entonces la ecuación (1) tendrá tres soluciones para ese mismo$k$, por lo que esto debe evitarse. Para cumplir con estas dos condiciones

$(\alpha_1,\alpha_2,\dots,\alpha_7)\text{ must be a permutation of }(1,1,2,2,3,3,4) \tag{3}$

En un esfuerzo por aplicar el principio del casillero, defina ahora los 2 huecos

$\beta_n = a_{n+2}-a_n,\:\text{ for }1 \le n \le 6 \tag{4}$

Estos se relacionan con los espacios 1 como$\beta_n = \alpha_n + \alpha_{n+1},\:\text{ for }1 \le n \le 6 \tag{5}$

Hay seis espacios de 2, y pueden tener valores tales que para todos$n$

$4 \le \beta_n \le 7 \tag{6}$

Sólo podemos tener uno de los$\beta_n=4$, como hay un$\alpha_n=4$. Desde dos diferentes$\beta_n$pueden compartir el mismo valor (por$5,6,7$), por lo tanto, hay siete ranuras y solo seis objetos para colocar, por lo que el principio del casillero no obliga a tres soluciones a la ecuación (1).