En cada conjunto de$14$ enteros hay dos que su diferencia es divisible por$13$

Question

Demostrar que en cada conjunto de $14$ enteros hay dos que su diferencia es divisible por $13$

La prueba va como este, hay $13$ resto al dividir por $13$, $14$ números, por lo que a partir de la encasillar principio, hay dos que tienen el mismo resto, por lo que su diferencia es divisible por $13$.

Pero, ¿y si vamos a tomar un conjunto de números que no tiene nada en común con $13$?

Como $\{10,10^2,10^3...,10^{14}\}$ o un primo que está más lejos de 13: $\{89,89^2,...,89^{14}\}$ ¿cómo es posible que los números y sus diferencias, tienen algo en común con una totalmente diferente prime?

Answer 1

Considerar los números seleccionados $\{a_1, a_2, \ldots a_{14}\} \bmod 13$. A continuación, cada uno de ellos debe estar en una clase de residuo, $\{r_1, r_2, \ldots r_{14}\} $ -, pero sólo hay $13$ residuo de clases, por lo que, al menos, $2$ debe estar en la misma clase. La diferencia de cualquier $2$ números en el mismo residuo de la clase es divisible por $13$.

Tenga en cuenta que con el primer poderes diferentes a $13$, está evitando la $0$ residuo de la clase, por lo que realmente habrá, al menos, $2$ diferencias divisible por $13$ en ese caso, como sólo hay $12$ clases de ser ocupada por la $14$ números.

Answer 2

Puede dividir el conjunto de enteros en$13$ conjuntos que no se intersecan. Existen los múltiplos de$13$, números cuyo resto cuando se divide por$13$ es$1$, números cuyo resto es$2$ y así sucesivamente. Si elige$14$ de números distintos, al menos dos de ellos deben pertenecer al conjunto establecido por el principio de casillero. La diferencia de estos dos será divisible por$13$.

Answer 3

Me alegro de que ahora sé lo que la Caja Principal es, después de haber escuchado tantas veces. :)

No ser $14$ distintos números de$\in N\gt 13$, basta con aplicar el Algoritmo de la División para obtener el resto a $0-12$ $13$ de esos números. Para producir set $\{13q_0 + r_0,13q_1 + r_1,...,13q_{12}+r_{12}\}$. Los restos de $r_1-r_{12}$ son los números de $0$ a través de $12$ y son distintos. si estaban en la misma la diferencia sería divisible por $13$ y listo. ahora el $14th$ número debe tener el mismo resto como uno de los otros $13$, por lo que la diferencia es divisible por $13$. De hecho, me encontré con este en una inducción de la prueba. La inducción en el rango de los números/mayor número $n$.

Caso Base $n=14$:debe tener todos los números de $1$ a través de $14$. $14-1=13$.

Asumir cierto para $n$. Para $n+1$ puede aplicar lo dicho anteriormente. Si todos los $14$ elegido de establecer a través de la gama de $n$ /verdadero, por hipótesis inductiva.

De lo contrario, si $n+1$ han elegido set/subconjunto $\{\{i_1,i_2,...,i_{13}\},n+1\}$ y pueden aplicar lo que se dijo anteriormente. Es decir, si ninguno de $\{i_1,i_2,...,i_{13}\}$ tienen el mismo resto mod $13$ cubren toda la gama de los restos de mod $13$ y, por tanto, $n+1$ mod $13$ debe ser igual a uno de $\{i_1,i_2,...,i_{13}\}$mod $13$. Esto completa la inducción. (si es el mismo mod $13$ de diferencia entre los dos es divisible por $13$)

La inducción no es necesario para este problema, sin embargo.

Answer 4

Intuitivamente, podría pensar en términos de aritmética modular: llame a 3 miembros de su conjunto$a,b$ y$c$. Supongamos que$a-b=k_1 \mod 13$ y$a-c= k_2 \mod 13$. Ahora, si$k_1=k_2$, entonces$b-c$ será divisible por 13, por lo que necesita$k_1 \neq k_2$ para tener problemas. Pero tienes 13 ecuaciones de este tipo, y solo 12 valores diferentes para$k$, así que aplica el principio del casillero aquí y listo.