El principio del palomar

Mete más objetos que cajas en unas cajas y alguna recibirá dos. Ese es el principio entero, y la habilidad consiste en saber elegir las cajas. Aquí tienes tres problemas en los que las cajas están ocultas: elige los números o colorea las conexiones, y la página te mostrará qué caja se ha desbordado.

Ejemplo resuelto — El principio del palomar

Números frente a cajas	se fuerza una colisión
Caja con dos	5 \| 10
caja 9	9
caja 11	11
caja 13	13
caja 15	15

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

Lección

La teoría — El principio del palomar

El principio del palomar: si metes N cosas en k cajas y N > k, en alguna caja habrá al menos dos. Con más precisión, alguna caja contiene al menos ⌈N/k⌉, el menor número entero que es mayor o igual a N/k.

Qué significa cada símbolo

N: la cantidad de cosas colocadas
k: el número de cajas
⌈N/k⌉: N/k redondeado hacia arriba: el mínimo que debe contener la caja más llena

De dónde viene la fórmula

Por qué ⌈N/k⌉. Si cada caja contuviera menos de N/k cosas, las k cajas juntas tendrían menos de k × N/k = N, pero contienen las N enteras. Por tanto, alguna caja tiene al menos N/k, y como guarda un número entero de cosas, tiene al menos ⌈N/k⌉. Cinco conexiones en dos colores dan ⌈5/2⌉ = 3 de un color; dieciséis conexiones en tres colores dan ⌈16/3⌉ = 6.
Eligiendo las cajas para los divisores. Cada número entero es, de exactamente una manera, un número impar multiplicado por una potencia de 2, m × 2ᵃ; ponlo en la caja m. Dos números en una misma caja son m × 2ᵃ y m × 2ᵇ con a < b, y el primero divide al segundo. Los números impares del 1 al 2n son 1, 3, …, 2n − 1, lo cual supone n cajas, así que n + 1 elecciones obligan a meter dos en una caja. El límite es exacto: n + 1, …, 2n son n números, uno por caja, y ninguno divide a otro, porque el simple hecho de duplicar el más pequeño ya supera 2n.
De sumas iguales a grupos disjuntos. Dos grupos distintos A y B con la misma suma pueden compartir algunos números. Quita de ambos los números compartidos: cada suma baja en la misma cantidad, por lo que las sumas siguen siendo iguales. Ningún grupo se queda vacío, porque si A estuviera dentro de B, B tendría la suma más grande, al ser todos los números positivos. Lo que queda son dos grupos disjuntos y no vacíos con sumas iguales, y eso es lo que dibuja la página.

Nueve números del 1 al 16: uno siempre divide a otro 🖖

Escribe cada número como un número impar multiplicado por una potencia de 2: 12 = 3 × 4, 10 = 5 × 2. Los números con la misma parte impar van a la misma caja, y el menor divide al mayor, porque solo se diferencian en potencias de 2. Del 1 al 16 hay ocho números impares, es decir, ocho cajas, y nueve elecciones meten dos en una caja. Pulsa Del 9 al 16 para ver ocho números que escapan, uno por caja: solo 10 de las 12.870 elecciones de ocho números lo logran. Luego pulsa Del 9 al 16 y el 5. Las 11.440 elecciones de nueve números contienen un par que se divide, y las cajas lo demuestran sin comprobar ni uno solo.

Entre seis personas, tres son amigos mutuos o tres son desconocidos 🖖

Pulsa Seis personas y fíjate en la persona 1. Sus cinco conexiones son de dos colores, así que al menos tres comparten uno; pongamos que son amigos. Si cualesquiera dos de esos tres son amigos entre sí, ellos y la persona 1 forman tres amigos mutuos. Si ninguno lo es, esos tres son desconocidos mutuos. En cualquier caso aparece un triángulo, y el argumento no se ha fijado en el coloreado. Cinco personas pueden evitarlo, con amigos alrededor de un pentágono y desconocidos a través de él. De las 1.024 formas de colorear las conexiones de cinco personas, 12 evitan un triángulo de un solo color, y todas ellas son ese pentágono en alguna disposición. Ninguna de las 32.768 combinaciones para seis lo consigue. Greenwood y Gleason propusieron este argumento en 1955.

Diez números de dos cifras siempre ocultan dos sumas iguales, y nueve también 🖖

Pulsa Diez números. Diez números distintos de dos cifras forman 2¹⁰ − 1 = 1.023 grupos no vacíos, y un grupo de ellos solo puede sumar un valor del 10 al 90 + 91 + … + 99 = 945, lo cual da 936 valores posibles. Por tanto, dos grupos comparten una suma. Quítales los números que tengan en común y las sumas seguirán siendo iguales mientras que los grupos pasan a ser disjuntos. Este fue el primer problema de la Olimpiada Internacional de Matemáticas de 1972. Con nueve números distintos hay 511 grupos frente a un máximo de 846 sumas, y el recuento no demuestra nada. La verdad va más allá de la cuenta: nueve números donde cada suma de grupo es distinta necesitan que uno de ellos sea al menos 161 (cálculo de J. P. Grossman), así que nueve números de dos cifras también colisionan siempre. Ocho pueden escapar; pulsa Ocho que escapan.

Problema resuelto al detalle

¿Cuántas personas fuerzan un triángulo de un color con tres colores? 4 pasos
Ahora cada par de personas son amigos, desconocidos o rivales: tres colores en lugar de dos. ¿Cuántas personas garantizan que haya tres conectados completamente con un solo color?

Abre este problema en la herramienta
1. Con dos colores, el argumento de la página parte de las conexiones de una persona:
  
  $6 people : 5 links, 2 colours \Rightarrow ⌈ \frac{5}{2} ⌉ = 3 share a colour$
2. Con tres colores, toma a una persona de entre 17. Sus 16 conexiones se dividen en tres colores:
  
  $17 people : 16 links, 3 colours \Rightarrow ⌈ \frac{16}{3} ⌉ = 6 share a colour$
3. Si cualesquiera dos de esos seis están conectados con ese mismo color, ellos y la primera persona forman un triángulo de un color:
  
  $a link of that colour among the 6 \Rightarrow a triangle through person 1$
4. Si ninguno lo está, esos seis solo usan los otros dos colores, y la fiesta de seis personas de la página ya garantiza un triángulo entre ellos:
  
  $no such link \Rightarrow the 6 use 2 colours \Rightarrow a triangle, since R (3, 3) = 6$
Respuesta

Diecisiete personas siempre bastan, y Greenwood y Gleason demostraron en 1955 que dieciséis no: colorearon las conexiones de dieciséis personas con tres colores sin formar un triángulo de un color. Con cuatro colores nadie conoce la respuesta; está entre 51 y 62.

$R (3, 3, 3) = 17; 51 \leq R (3, 3, 3, 3) \leq 62$

Ruta de aprendizaje

Métodos de demostración

Referencias (5)

The party problem solved exactly as this page solves it, the pentagon with red sides and blue diagonals for five and one person's five links for six, and Theorem 4, three colours need exactly 17 people, which is the worked problem: R. E. Greenwood and A. M. Gleason, "Combinatorial Relations and Chromatic Graphs", Canadian Journal of Mathematics 7, 1–7 (1955).
The equal-sums problem as it was set, ten distinct two-digit numbers, with the count of 1,023 groups against sums of at most 945: 14th International Mathematical Olympiad, 1972, Problem 1; problem and solution in J. Scholes's IMO archive (Kalva).
Why nine two-digit numbers cannot escape either: nine numbers with all their subset sums different need one at least as large as 161: OEIS Foundation, "A276661: Least k such that there is a set S in {1, 2, ..., k} with n elements and the property that each of its subsets has a distinct sum", The On-Line Encyclopedia of Integer Sequences.
Three colours are settled at 17; four are not, and the answer lies between 51 and 62: OEIS Foundation, "A003323: Multicolor Ramsey numbers R(3,3,...,3), where there are n 3's", The On-Line Encyclopedia of Integer Sequences.
The principle stated and used, including its generalised form, ⌈N/k⌉ in some box: E. Lehman, F. T. Leighton and A. R. Meyer, Mathematics for Computer Science, MIT, revised 6 June 2018, §15.8, The Pigeonhole Principle.

Por el equipo de 42Math · Contrastado con fuentes publicadas. Se agradecen correcciones.