Tu amigo te ha dado su lista de los 115 mejores episodios de Doctor Who en orden de grandeza.

Question

Tu amigo te ha dado su lista de los 115 mejores episodios de Doctor Who (en orden de grandeza). Resulta que has visto 60 de ellos. Demuestre que hay al menos dos episodios que ha visto que son exactamente cuatro episodios aparte en la lista de su amigo

Answer 1

Dos aplicaciones de la encasillar principio.

En primer lugar, dividir los números de $1,\cdots, 115$ en cuatro grupos según el resto en la división por $4$. Es fácil ver que estos subconjuntos tienen o $29$ o $28$ cada uno de los miembros. Llegamos a la conclusión de que uno de ellos (al menos) debe contener, al menos, $15$ de los episodios que he visto.

Segundo: Si todos los cuatro de ellos contienen $15$ de las que hemos visto, entonces, en particular, el subgrupo con $28$ elementos hace. Fácil ver que, en ese caso, ese subconjunto debe tener dos episodios consecutivos que han visto. Si el conjunto de $28$ no contiene $15$ de las que hemos visto, uno de los conjuntos de $29$ debe contener, al menos, $16$ de los episodios que hemos visto, y de nuevo tenemos que hacer.

Answer 2

La partición del conjunto de $S=\{1,2,\ldots,115\}$ a $S_1\cup S_2 \cup S_3 \cup S_4$, donde:

$S_1=\{1,5,9,\ldots,113\}$
$S_2=\{2,6,10,\ldots,114\}$
$S_3=\{3,7,11,\ldots,115\}$
$S_4=\{4,8,12,\ldots,112\}$

Ahora supongamos que tenemos $T\subset S$ tal que no hay dos elementos de $T$ difieren por $4$. A continuación, $T$ no puede contener elementos consecutivos de $S_i$ cualquier $i$; por lo que puede contener en la mayoría de las $15$ elementos de $S_1,S_2$, e $S_3$, y en la mayoría de las $14$ elementos de $S_4$. Por lo tanto $|T|\le 59$.

Por el contrario, si $|T|=60$, a continuación, $T$ debe contener dos elementos diferentes por $4$.

Answer 3

Me gusta la $\bmod 4$respuestas, pero aquí es otra alternativa.

Partición de los episodios en $14$ bloques de ocho episodios consecutivos cada uno, además de tres episodios. Al menos $57$ de sus episodios están entre los bloques de ocho. Por el Principio del Palomar, uno de los bloques debe incluir al menos cinco de sus episodios. El uso de cualquiera de las $\bmod 4$ de la aritmética o de la fuerza bruta para mostrar que cinco episodios en un bloque de ocho debe incluir dos episodios exactamente cuatro lugares separados.

Answer 4

Por agotamiento (probablemente hay una forma más elegante de encontrar este), usted puede encontrar el más densamente puedes pack de episodios que se han visto, sin haber visto 2 episodios que son 4 episodios separados, es

SSSSNNNN, donde S = visto, N = no se ve.

Esto significa que, en el mejor de los que he visto 4 episodios por cada 8 en su lista. Sin embargo, si continúa este patrón de ver a los 4 que faltan 4, usted encontrará que la lista va a tener 14 lotes de SSSSNNNN (56 episodios visto, 112 episodios en la lista), luego de terminar con el SSS, completando la lista de 115 episodios, sin embargo viendo sólo el 59. Su lista tendría que ser de al menos 116 episodios largos para cumplir con los no-4-episodios-aparte de los criterios. Por lo tanto, debe haber al menos dos episodios que se han visto que son exactamente cuatro episodios aparte de tu lista de amigos.