Inclusión-exclusión y principio del palomar

A∪B significa pertenecer a A o a B, permitiendo pertenecer a los dos. A∩B significa pertenecer a ambos. Al sumar |A|+|B|, un elemento de la intersección aparece dos veces; restar |A∩B| deja una sola copia.

“Al menos uno” pide la unión. “Exactamente uno” excluye a quienes pertenecen a ambos: su cantidad es |A|+|B|−2|A∩B|. El dibujo permite seguir a una persona de cada región y comprobar cuántas veces la cuenta cada fórmula.

Las cuatro regiones son solo A, ambos, solo B y ninguno.

Deben ser enteros no negativos y sumar |U|. No hace falta suponer un reparto aleatorio.

La cota superior impide que “ambos” supere un grupo entero; la inferior impide que la unión desborde el universo. Un dibujo ayuda, pero las áreas dibujadas no sustituyen estas cantidades.

Para A, B, C sumamos sus tamaños, restamos |A∩B|, |A∩C| y |B∩C| y añadimos |A∩B∩C|. Un elemento que está en los tres se sumó tres veces y se restó tres: quedó cero y necesita volver a contarse una vez.

Las intersecciones dobles incluyen a quienes están también en el tercero. No significan “exactamente esos dos”. Si la triple tiene tamaño t, exactamente A y B sin C tiene tamaño |A∩B|−t. Dibujar regiones o comprobar pertenencias evita confundir esos dos datos.

Para r conjuntos finitos se suman las intersecciones simples, se restan las dobles, se añaden las triples y se continúa. Cada selección de índices se cuenta una vez, sin distinguir órdenes. Para un elemento que pertenece a s≥1 conjuntos, la contribución es C(s,1)−C(s,2)+⋯+(−1)ˢ⁺¹C(s, s).

El binomio 0=(1−1)ˢ=1−C(s,1)+C(s,2)−⋯ demuestra que esa contribución es uno. Un elemento fuera de la unión contribuye cero. Esta cuenta elemento a elemento prueba la regla general. Omitir intersecciones de orden alto sin saber que son vacías puede cambiar el resultado.

Si U es el universo y Aᵢ describe una propiedad prohibida, los objetos válidos son U menos la unión de los Aᵢ. Las intersecciones cuentan varias infracciones simultáneas. El universo y las propiedades deben fijarse antes de aplicar la regla.

Entre 1 y M, los múltiplos de d son ⌊M/d⌋. Ser múltiplo de a y de b equivale a ser múltiplo del mínimo común múltiplo, no siempre de ab.

Los extremos forman parte del problema.

El principio del palomar dice: N objetos asignados a m cajas, con m≥1 y N>m, fuerzan una caja con al menos dos. Si todas tuviesen como máximo uno, cabrían a lo sumo m objetos, contradiciendo N>m. No requiere azar ni tamaños de cajas iguales.

Una caja es una categoría definida para cada objeto: un mes, un resto, una zona o un valor de una función. Debe haber una regla que asigne cada objeto a exactamente una caja. Una conclusión de coincidencia no identifica de antemano qué objetos ni qué caja compartirán.

Si las cargas enteras son n₁,…, nₘ y suman N, alguna es al menos ⌈N/m⌉. Si todas fuesen como máximo ⌈N/m⌉−1, el total sería menor que N. El techo es el entero más pequeño mayor o igual al cociente; no se redondea al entero más cercano.

Para forzar una carga de al menos k, la condición equivalente es N>m(k−1). Con m(k−1) objetos aún podrían colocarse k−1 en cada caja. La garantía no impide que alguna reciba mucho más: “al menos” debe mantenerse al interpretar el resultado.

El argumento del techo prueba que una carga es inevitable. Para saber si puede forzarse una carga mayor con la misma información, buscamos un reparto que no la alcance.

El máximo es ⌈N/m⌉.

Así la cota es óptima sin restricciones adicionales. “Alguna caja” tampoco significa “una sola caja”: puede haber varias con la misma carga alta. El método produce una existencia y una cota, no una distribución exacta ni una probabilidad sobre repartos.

Las cajas se diseñan para que dos objetos dentro de una impliquen lo que queremos demostrar. Para congruencias usamos restos; para cercanía usamos intervalos cortos; para sumas consecutivas usamos restos de sumas parciales. Después hay que traducir la coincidencia de vuelta a la pregunta.

Al partir un intervalo, fijamos qué ocurre con los extremos para que cada punto tenga una caja única. En [0,1] podemos usar intervalos semiabiertos y cerrar el último en 1. Si una caja mide 1/m, dos puntos en ella distan a lo sumo 1/m; no afirmamos una desigualdad estricta sin revisar la caja de los extremos.