Los Números de Hilbert

ENUNCIADO Ana celebra una fiesta en su casa por su cumpleaños. Ha invitado a algunos de sus amigos y les ha animado a que estos traigan más gente a la fiesta. Al final llegan todos a la fiesta y Ana les sorprende con una tremenda afirmación: En esta fiesta hay al menos dos personas que conocen al mismo número de personas presentes en la fiesta. ¿Cómo ha llegado Ana a esta conclusión? SOLUCIÓN Supongamos que hay $n$ personas en la fiesta. Entonces cada una de esas personas puede conocer a $0,1, \ ..., n-1$ personas restantes que estén en la fiesta, por tanto hay $n$ posibles opciones para las $n$ personas totales. Sin embargo podemos considerar dos casos distintos. Caso 1: Si hubiera una persona que no conoce a nadie más en la fiesta, entonces nadie conocería a todo el mundo, pues a esa persona no la conocería nadie. Por tanto para las $n$ personas de la fiesta podría darse que conociesen a $0, 1, \ ..., n-2$ personas, es decir, $n-1$ posibles opciones. Ahora vam...

En los anteriores posts hemos estado viendo cómo contar determinados conjuntos y varias técnicas para hacerlo. Ahora lo que vamos a hacer es plantearnos el problema de cómo podemos contar los elementos de un subconjunto cualquiera de un conjunto finito. Es decir, si tenemos un conjunto finito de $n$ elementos, ¿cuántos subconjuntos suyos hay que tengan $k\leq n$ elementos? Un posible símil que podemos establecer es el siguiente: si tenemos $n$ personas, ¿de cuántas formas distintas podemos agrupar $k$ de ellas? En efecto, el conjunto de $n$ elementos es el conjunto de personas, y habrá tantos subconjuntos de $k$ elementos como formas de elegir $k$ personas distintas del grupo. Además este ejemplo nos viene muy bien para hacer algunas observaciones fácilmente. Por ejemplo: por cada grupo de $k$ personas que podemos formar, el resto de personas que no quedan en el grupo $(n-k)$ forman otro grupo (distinto), y de hecho esta es una correspondencia biunívoca, es decir, cada grupo de $k...