El Principio del Palomar

Suponga que usted está en una plaza observando las palomas que pululan en ella, la bandada que vive en la zona cuenta con once palomas y usted observa que en su totalidad, hay diez nidos en una hilera, cuando las palomas retornan una a una a sus hogares la primera va al primer nido, la segunda al segundo nido, la tercera al tercer nido, y así sucesivamente, la décima al décimo nido pero… ¿A dónde va la última paloma? Pues inevitablemente, esta tiene que compartir el nido con alguna de las otras palomas.

El Principio de Dirichlet, popularmente conocido como El Principio del Palomar, establece que considerando $n$ cajas, si en ellas se meten $n+1$ o más objetos, entonces habrá al menos una caja que contiene al menos dos de estos objetos.

Este principio tiene su interpretación al considerar funciones, y es que si $A$ y $B$ son dos conjuntos con cardinales $n+1$ y $n$ , respectivamente (esto es la cantidad de elementos que ellos contienen). Entonces, cualquier función definida de $A$ en $B$ no es inyectiva.

Consideremos algunos ejemplos prácticos de este principio para entender cómo se aplica.

También pudiera interesarte

Anuncios

Ejemplos

Ejemplo 1

Suponga que usted es un médico que trata casos complejos, si atiende sólo de lunes a viernes, y debe practicar una consulta a 6 pacientes en una semana. Entonces, necesariamente debe atender a dos pacientes en un mismo día de la semana.

Ejemplo 2

Si en una clase de 16 estudiantes, se efectúa una evaluación cuya calificación tiene un rango entre 0 y 10 puntos. Entonces, se puede garantizar que habrán al menos dos estudiantes con la misma calificación.

Ejemplo 3

Si se efectúa una evaluación cuya calificación tiene un rango entre 0 y 20 puntos. ¿Cuál es la cantidad mínima de estudiantes que debe haber para garantizar que al menos dos tengan la misma calificación?

Podemos abordar este problema usando el principio del palomar, pues si consideramos el rango de las calificaciones hay 21 opciones $\{0,1,2, \ldots 20 \}$ . Entonces, básicamente, si contamos con 21 cajas, deberían haber al menos $21+1=22$ estudiantes para garantizar que al menos dos tengan la misma calificación.

Anuncios

Estos ejemplos pudieran resultar sencillos, pero el Principio del Palomar tiene mayor utilidad para asentar afirmaciones sobre números enteros. Un ejemplo de esto es la siguiente afirmación:

Para todo número entero, existe un múltiplo de este número cuyos dígitos son ceros o unos. Es decir, para todo número entero $p$ , existe un número entero $q$ tal que

$p \cdot q = x \cdot 10^{k} + x \cdot 10^{k-1} + \ldots + x \cdot 10^2 + x \cdot 10 + x$

Donde $x$ es cero o uno.

Demostración:

Para demostrar esta afirmación, definamos el siguiente conjunto:

Debemos notar que $|A| = p+1$ y que cada elemento $a_i$ del conjunto $A$ está definido de la forma

$1 \cdot 10^{i} + 1 \cdot 10^{i-1} + \ldots + 1 \cdot 10^2 + 1 \cdot 10 + 1$ .

Considerando el algoritmo de la división, debemos notar que cualquier número entero se puede expresar de la forma $p \cdot q + r$ y al ser $0 \leq r < p$ , podemos asegurar que existen $p$ posibles restos. Entonces, al dividir $a_{1}$ obtendremos un resto $r_1$ , al dividir $a_{2}$ obtendremos un resto $r_2$ , y así sucesivamente, al dividir $a_{p+1}$ obtendremos un resto $r_{p+1}$ .

De esta forma, obtenemos $p+1$ restos al efectuar cada una de estas divisiones pero ya hemos visto que hay $p$ posibles restos al dividir por $p$ , así, recurriendo al Principio del Palomar, concluimos que al menos dos de estos restos deben ser iguales. Es decir, existen dos elementos de $A$ , digamos $a_i < a_j$ , tal que $a_i = p \cdot q_i + r$ y $a_j = p \cdot q_j + r$ . Entonces, si consideramos la resta del mayor menos el menor, obtenemos que

$a_j - a_i = (p \cdot q_j + r) - (p \cdot q_i + r) = p \cdot (q_j - q_i)$

De donde concluimos que el número $a_j - a_i$ es un múltiplo de $p$ y además, notamos que esta resta es igual a

$1 \cdot 10^{j} + 1 \cdot 10^{j-1} + \ldots + 1 \cdot 10^{i+1} + 0 \cdot 10^{i} + 0 \cdot 10^{i-1} + 0 \cdot 10^2 + 0 \cdot 10 + 0$

Por lo tanto, $a_j - a_i$ es un múltiplo de $p$ que cuyos dígitos son ceros o unos.

Hemos visto que el Principio del Palomar nos ayuda a garantizar cuando hay al menos dos elementos en una caja, por ejemplo, si contamos con 5 sacos e introducimos naranjas en ellos, ¿al menos cuántas naranjas debemos tener para garantizar que habrán al menos dos en un saco? La respuesta es 6.

Pero, ¿al menos cuántas naranjas deben haber para garantizar que habrán al menos tres en un saco? ¿O al menos cuatro? ¿Cinco? Para responder a estas preguntas, veamos que este principio se puede generalizar pero primero debemos definir algunas funciones especiales.

Anuncios

Funciones de parte entera

La función piso redondea todo número decimal hacia abajo, formalmente, para todo número entero $a$ , definimos la función piso como una función $\lfloor \ \ \rfloor : [a,a+1] \to \mathbb{Z}$ de la forma $\lfloor x \rfloor = a$ y de forma general, $\lfloor \ \ \rfloor : \mathbb{R} \to \mathbb{Z}$ está definida como $\lfloor x \rfloor = a$ si $a \leq x < a+1$ .

La función techo redondea todo número decimal hacia arriba, formalmente, para todo número entero $b$ , definimos la función techo como una función $\lceil \ \ \rceil : (b-1,b] \to \mathbb{Z}$ de la forma $\lceil x \rceil = a$ y de forma general, $\lceil \ \ \rceil : \mathbb{R} \to \mathbb{Z}$ está definida como $\lceil x \rceil = b$ si $b -1 < x \leq b$ .

Funciones de Parte Entera, Función Piso y Función Techo | totumat.com

El Principio del Palomar Generalizado

El Principio del Palomar Generalizado, establece que considerando $k$ cajas, si en ellas se meten $n$ objetos, entonces habrá al menos una caja que contiene al menos $\lceil \frac{n}{k} \rceil$ de estos objetos.

Cuando no sabemos con certeza la cantidad de elementos en un conjunto, este principio nos ayuda principalmente a fijar cotas inferiores. Consideremos algunos ejemplos prácticos de este principio para entender cómo se aplica.

Anuncios

Ejemplos

Ejemplo 4

Si contamos con 5 sacos e introducimos naranjas en ellos, ¿al menos cuántas naranjas debemos tener para garantizar que habrán al menos tres en un saco? En términos del principio del palomar, si tenemos $n$ objetos y 5 cajas, ¿cuál es el mínimo valor de $n$ para que $\lceil \frac{n}{5} \rceil = 3$ ?

Si $\lceil \frac{n}{5} \rceil = 3$ , esto implica que $\frac{n}{5}$ es un elemento del intervalo $(2,3]$ . Entonces, considerando el extremo inferior de este intervalo, el menor número entero $n$ que estamos buscando es tal que $n = 2 \cdot 5 + 1 = 11$ , y en efecto, veamos el peor de los casos que es cuando distribuimos los objetos uno a uno:

Si consideramos cinco sacos vacíos:

E introducimos cinco naranjas, cada una en cada saco

Luego, introducimos cinco naranjas más, cada una en cada saco

Contamos diez naranjas, pero si consideramos una naranja adicional (la onceava), sea cual sea el saco en donde la metamos, tendremos un saco con tres naranjas en él.

Ejemplo 5

Considerando un mazo de barajas de 52 cartas, es decir, 13 corazones, 13 picas, 13 diamantes y 13 tréboles. ¿Cuántas cartas debe tomar una persona, para garantizar que al menos 3 son de la misma pinta? En términos del principio del palomar, si tenemos $n$ objetos y 4 cajas, ¿cuál es el mínimo valor de $n$ para que $\lceil \frac{n}{4} \rceil = 3$ ?

Si $\lceil \frac{n}{4} \rceil = 3$ , esto implica que $\frac{n}{4}$ es un elemento del intervalo $(2,3]$ . Entonces, considerando el extremo inferior de este intervalo, el menor número entero $n$ que estamos buscando es tal que $n = 2 \cdot 4 + 1 = 9$ , y en efecto, veamos el peor de los casos que es cuando:

Tomando las primeras cuatro cuartas, todas son de diferente pinta,

Tomamos cuatro cartas más, y todas son nuevamente, de diferente pinta,

Contamos ocho cartas, pero si tomamos una carta adicional (la novena), sea cual sea la carta que tomemos, esta será de alguna de las cuatro pintas.

Nota: Cuando se menciona el peor de los casos, es para evitar considerar aquellos casos en los que se cumple la condición que estamos buscando, pero no necesariamente siendo esta la regla general.

¿Tienes alguna duda? Compártela en los comentarios. Cancelar la respuesta

Introduce aquí tu comentario...

Introduce tus datos o haz clic en un icono para iniciar sesión:

Correo electrónico (obligatorio) (La dirección no se hará pública)

Nombre (obligatorio)

Web

Estás comentando usando tu cuenta de WordPress.com. ( Salir / Cambiar )

Estás comentando usando tu cuenta de Facebook. ( Salir / Cambiar )

Cancelar

Conectando a %s

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.

Ejemplos

Ejemplo 1

Ejemplo 2

Ejemplo 3

Funciones de parte entera

El Principio del Palomar Generalizado

Ejemplos

Ejemplo 4

Ejemplo 5

Comparte

Related

¿Tienes alguna duda? Compártela en los comentarios. Cancelar la respuesta