Problema relacionado con el uso del principio de Pigeonhole (Caja)

Question

Pregunta:

Tome cualquier $37$ enteros del conjunto { ${1,2,…,112}$ }. Demostrar que siempre existirán dos enteros $x,y$ de esos $37$ enteros tales que $ \mid x-y \mid \in \{9,10,19\}$ .

Enfoque:

Qué he hecho hasta ahora:

Dejemos que $S=$ { ${1,2,…,112}$ }

Partimos el conjunto en subconjuntos $S_i$ de la forma $\{x, x+9, x+19\}$ . Entonces la diferencia de dos elementos cualesquiera está en $\{9, 10, 19 \}$ que es fácil de ver.

Se realizan las siguientes particiones (para $x=1, 2, \cdots , 9$ ): $$\{1, 10, 20 \}, \{2, 11, 21 \}, \cdots, \{9, 18, 28\}$$ A continuación, elegimos $x=29$ para mantener los conjuntos disjuntos esenciales para nuestra prueba. Esto da los conjuntos disjuntos $$ \{29, 38, 48\}, \cdots, \{37, 46, 56 \} $$ y de manera similar $$\{85, 94, 104 \}, \cdots, \{93, 102, 112 \}$$

Sin embargo, como el lector rápido puede ver que los números $\{19, 47, 75, 103\}$ no aparecen en ningún conjunto. Sin embargo, decido hacer un análisis caso por caso de las situaciones. Nombra este conjunto como $X$ .

Supongamos, inicialmente, que de los $37$ enteros en nuestra selección, ninguno pertenece a $X$ . Entonces se deduce del principio de caja de Dirichlet que al menos dos elementos son del mismo conjunto (es decir, de uno de los subconjuntos que hemos dividido $S$ en) entonces la reclamación es válida.

Supongamos ahora que un elemento de $X$ está en nuestra selección, digamos $19$ entonces si al menos uno de $9, 28, 29, 38$ está en nuestra selección, entonces la afirmación es válida.

Supongamos que no hay ninguno de ellos y que nos faltan cuatro enteros. Ahora podemos seleccionar cuatro enteros cualesquiera de los números restantes y el principio de caja garantiza que al menos dos son del mismo conjunto.

Porque, aunque todos los $3$ otros elementos de $X$ están ahora presentes, hay una ranura vacía que puede ser llenada usando los otros subconjuntos de donde ya tenemos al menos un elemento en nuestra elección de $37$ números.

Espero que esto sea comprensible porque mis habilidades para escribir pruebas de combinatoria son horribles. Me estoy preparando para las olimpiadas y también para ser un buen matemático en general. Gracias por la ayuda :)

Editar:

Parece que no he introducido mi pregunta principal, disculpas. ¿Es correcta mi solución?

Answer 1

Buen trabajo, creo que tu razonamiento está todo ahí, pero te ayudará desglosar un poco tu argumento, para que sea más fácil de leer.

Primero has dividido el intervalo $\{1,\cdots 112\}$ en $37$ conjuntos, todos de la forma $S_x = \{x, x+9, x+19\}$ salvo el conjunto excepcional $X = \{19, 47, 75, 103\}$ . A continuación, examinamos cómo $X$ interactúa con el $S_x$ . Para cualquier $z \in \{1,\cdots 112\}$ , defina $$B_z = \big\{y \in \{1,\cdots 112\} \text{ such that } |y-z| \in \{9,10,19\} \big\}$$

Hacemos la importante observación de que para cada $y \in X$ , $B_y \supset S_{y-10}$ . Es decir, por cada elemento que colocamos en $X$ invalidamos un $S_x$ .

Ahora tenemos que colocar $37$ elementos entre los $37$ conjuntos.

Supongamos que colocamos $0 \leq n \leq 4$ elementos en $X$ . Esto deja $37 - n$ elementos para colocar entre los $36$ $S_x$ . De la observación anterior, $n$ opciones de la $S_x$ dará lugar inmediatamente a elementos a una distancia "mala". Por lo tanto, sólo $36 - n$ opciones de la $S_x$ son viables. De este modo, estamos colocando $37 - n$ elementos en $36 - n$ de la $S_x$ y por pidgeonhole, uno de los $S_x$ debe contener dos elementos.

Answer 2

Sólo para mostrar otra forma posible de abordar el problema.

Tomando $S=\{1,\,2,\, \cdots,\,112\}$ o $S=\{0,\,1,\, \cdots,\,111\}$ o cualquier conjunto de $112$ consecutivos enteros claramente no cambia el problema. Arreglemos $S=\{0,\,1,\, \cdots,\,111\}$ .

Entonces, tomando el conjunto $T$ de $37$ enteros, también está claro que si desplazamos como para tener el mínimo en $0$ no cambia el problema.

Por lo tanto, podemos empezar $T$ como $\{0,\, 1,\, 2,\, \cdots,\, 8\}$ (total de $9$ enteros)
después de lo cual saltaremos el conjunto $\{9,\, \cdots,\,18\} $ y $\{19,\, \cdots,\,27\} $ es decir $19$ enteros.

La forma más compacta con la que podemos proceder es repetir lo anterior empezando por $28$ .

Para llegar a $|T|=37$ tenemos que arreglar $4$ conjuntos prohibidos, es decir $76$ enteros.
Pero $112-76=36 < 37$ por lo que no podemos evitar que al menos un entero esté en el conjunto prohibido.