Inicio · Parte 04 — Matemática discreta para computación
n objetos en m cajas con n > m ⟹ alguna caja tiene ≥ ⌈n/m⌉
colisión de hash garantizada si entradas > tamaño del espacioEl principio del palomar es de una simplicidad desarmante: si se reparten n objetos en m cajas y n > m, alguna caja recibe al menos dos. Su potencia está en que demuestra una existencia sin ofrecer un método para encontrarla, y ese tipo de argumento —no constructivo— es habitual en matemáticas y muy útil en informática.
La aplicación directa es a las funciones hash. Una función que mapea un dominio infinito —o simplemente mayor— en un espacio de 2ⁿ valores tiene colisiones necesariamente. No es un defecto de la función: es una consecuencia lógica. Por eso la pregunta correcta sobre una función hash criptográfica no es «¿tiene colisiones?» sino «¿es computacionalmente factible encontrarlas?».
La forma generalizada da una cota más fina: alguna caja tiene al menos ⌈n/m⌉ objetos. Con 400 personas y 365 días del año, alguna fecha tiene al menos dos cumpleaños; con 800, al menos tres.
Conviene no confundirlo con la paradoja del cumpleaños, que es un resultado probabilístico distinto: con solo 23 personas la probabilidad de coincidencia supera el 50 %. El palomar da certeza con 366; la paradoja da probabilidad alta con 23. La segunda es la que determina la seguridad real de un hash frente a ataques de colisión, y aparece en la clase 090 como contraste.
Cumpleaños y colisiones de hash.
400 personas, 365 días:
400 > 365 → coincidencia GARANTIZADA
mínimo de repeticiones: ⌈400/365⌉ = 2
Hash de 16 bits (65 536 valores), 100 000 entradas:
100 000 > 65 536 → colisión GARANTIZADA
Contraste con la paradoja del cumpleaños:
con 23 personas, P(coincidencia) > 0.5
el palomar da certeza; la paradoja da probabilidad
Lección: no hace falta encontrar la colisión
para demostrar que existe.Principio del palomar: colisiones garantizadas sin construirlas.
python classes/part-04-matematica-discreta-para-computacion/090-principio-del-palomar/lab.py
compmath run 090personasdias_del_añocoincidencia_de_cumpleaños_garantizadaminimo_repeticionesespacio_hashentradascolision_garantizadaleccion{
"personas": 400,
"dias_del_año": 365,
"coincidencia_de_cumpleaños_garantizada": true,
"minimo_repeticiones": 2,
"espacio_hash": 65536,
"entradas": 100000
}Análisis de funciones hash, límites de compresión sin pérdida, diseño de tablas hash y argumentos de existencia en teoría de la complejidad.
Los grafos de cómputo, la búsqueda en árbol y las GNN son estructuras discretas; el conteo sostiene la probabilidad que después usa todo modelo generativo.
9781138197015 verificado en International ISBN Agency (2026-08-19).