Una prueba estándar y rigurosa utilizando el principio de casillero.

Question

Ahora hay una pregunta:

Durante veinte números de dos dígitos, añadimos dos dígitos. (como 12 y obtener el resultado 3) Demostrar en estos veinte números, debe haber al menos 2 mismos resultados.

Ahora sé que puedo asumir el ejemplo más extremo que es la adición de 0,0 0,1 hasta 9,9, así que tengo en la mayoría de los 19 resultados. Por lo tanto, el siglo xx debe ser igual a una de las anteriores 19.

Pero, en realidad, no sé el estándar y rigurosas pruebas de este problema. Alguien me puede ayudar con este estándar de prueba?

Answer 1

El Principio del Palomar es realmente la afirmación de que para finito de conjuntos de $S,T$ con $|S|>|T|$, no es inyectiva asignación de $S$ a $T$. Proceder por inducción en $|T|$. Para $|T|=1$, $|S|\ge 2$ por hipótesis; no hay un mapa de $S$ a $T$ y no es uno-a-uno. Ahora supongamos cierto para conjuntos con $n$ elementos y que $|T|=n+1$ (e $|S|>n+1$), y deje $\phi:S\to T$. Deje $t\in T$. Entonces, como no hay inyectiva asignaciones de $S$ a $T-\{t\}$ por la hipótesis de inducción, $\phi$ no ser inyectiva menos que algunas de las $s\in S$ mapas a $t$, así que supongo que esto es así. Si otro elemento que también se asigna a $T$, entonces claramente $\phi$ no es uno-a-uno, así que supongo que $\phi^{-1}(t) = \{s\}$. A continuación, $\phi|_{S-\{s\}}$ mapas de $S-\{s\}$ a $T-\{t\}$, y por la inducción de la hipótesis de este mapa no puede ser uno-a-uno. Así, en todos los casos $\phi$ no ser uno-a-uno.

Answer 2

El principio del casillero dice que si los elementos $i$ se colocan en $c$ contenedores, donde $i>c$ , entonces al menos un contenedor debe tener al menos dos artículos. Las sumas de los 20 números representan 20 artículos y el número de resultados posibles, 19, representa los contenedores.

Answer 3

No me gusta citar el principio del palomar cuando no es nada más que sentido común. Como este:

Sólo hay $19$ posible de dos dígitos sumas de dinero, porque el pequeño es $0+0$ y el más grande es $9+9$ y sólo hay $19$ enteros de $0$ a $18$. Así que, obviamente, si usted tiene $20$ números de dos dígitos, no todas se han de dígitos diferentes sumas de dinero, debido a que $20 > 19$.

Más generalmente, si usted ha $c·k+1$ artículos y asignar a uno de $c$ etiquetas para cada elemento, no es una etiqueta que se le asigna al menos a $k+1$ artículos. Prueba: Si la afirmación es falsa, entonces cada etiqueta es asignada a la mayoría de las $k$ , por lo que no puede haber más de $c·k$ artículos, contradiciendo el número dado de elementos. Por lo tanto la afirmación es verdadera.