Demostrar que entre 111 números enteros cualesquiera elegidos al azar hay uno que es múltiplo de 111 o dos cuya differencia es múltiplo de 111.

Question

Demostrar que entre 111 números enteros positivos elegidos al azar hay uno que es múltiplo de 111 o dos cuya differencia es múltiplo de 111.

Esta pregunta me la hicieron en un examen. ¡Lo dejé en blanco porque no estoy seguro de cómo resolverlo, si quieres enseñarme me encantaría saber!

Answer 1

Pista:
Supongamos que no es cierto. Entonces no hay ningún número que sea múltiplo de 111, ni ninguna diferencia entre dos números es múltiplo de 111. Sea $S$ el conjunto de todos los números módulo 111. Entonces no hay dos elementos en $S$ que son iguales, porque de lo contrario hay dos números cuya diferencia es múltiplo de 111.

Demuestre ahora que hay 111 elementos en el conjunto $S$ y por qué eso llevará a una contradicción.

Answer 2

Supongamos que $n_0, n_1, ..., n_{110}$ son $111$ enteros, de los cuales no hay dos que tengan una diferencia que sea múltiplo de $111$ . Entonces, el mapa de $\{0,1,...,110\}$ a sí mismo que envía $i$ a $n_i \bmod 111$ es inyectiva y, por tanto, también suryectiva, lo que significa que $0$ en particular, debe estar en la imagen, es decir, que al menos uno de los $n_i$ s es múltiplo de $111$ .

Answer 3

Sean los números enteros que forman el conjunto $\mathbb X = \{x_1, x_2, \dots, x_{111}\}$ y luego considerar el conjunto $\bar{\mathbb X} = \{\bar{x}_1, \bar{x}_2, \dots, \bar{x}_{111}\}$ donde

1. $\bar{x}_i \equiv x_i \pmod{111} \text{ for all } 1 \le i \le 111$ .
2. $\bar{x}_i \ne \bar 0 \text{ for all } 1 \le i \le 111$ .

Debido al artículo $(2.)$ sólo hay $110$ valores posibles para el $111$ módulos en el conjunto $\bar{\mathbb X}$ . Por el principio del agujero de Pidgeon, deben existir índices $i \ne j$ para lo cual $\bar x_i = \bar x_j \pmod{111}$ . Con un poco más de trabajo, se llega a la conclusión.

Answer 4

Dicho de otro modo: si $S$ es un conjunto de $111$ números enteros de los que dos no son congruentes $\!\bmod 111$ entonces $S$ tiene un elemento $\equiv 0\pmod{\!111},\,$ es decir sistema completo de residuos $\!\bmod 111$ contiene algunos $s\equiv 0$ .

Se trata de una consecuencia inmediata del Principio de encasillamiento, es decir, el mapa $\,s\to s\bmod 111$ es $1\!-\!1$ (inyectiva), por tanto onto (suryectiva).