2 votos

Demostración del Principio del Casillero mediante prueba por contradicción

Dado que el Principio del Agujero de Paloma afirma que "Cuando n + 1 palomas se posan en n agujeros, debe haber algún agujero que contenga al menos dos palomas", demuéstrelo por contradicción.

¿cómo hacerlo sin utilizar un ejemplo concreto?

1voto

Broke Bytes Puntos 9

Supongamos que puede encajar $n + 1$ palomas en $n$ agujeros sin que ninguno contenga al menos dos palomas. Numere los $n$ agujeros para los que esto es posible a partir de $1$ a $n$ y que $a_i$ denota el número de palomas en el agujero $i$ . Por supuesto, cada $a_i$ es $0$ ou $1$ . Puesto que cada paloma está en un agujero, debe darse el caso de que $a_1 + \cdots + a_n$ es el número total de palomas. Es decir $$ a_1 + \cdots + a_n = n + 1 $$ Por otra parte, tenemos $a_i \leq 1$ para todos $i$ (hay como máximo $1$ paloma en cada agujero). Así $$ a_1 + \cdots + a_n \leq 1 + \cdots + 1 = n $$ (si sumamos $n$ cosas, cada una de las cuales es como máximo $1$ el mayor número que podemos obtener es $n$ ). Por lo tanto, hemos demostrado $$ n + 1 \leq n $$ Esto implica $1 \leq 0$ lo cual es absurdo.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X