Reto 2
Demostrar que en una reunión de 100 personas hay al menos dos que tienen el mismo número de conocidos en el grupo.
Solución
Para este reto se puede usar el conocido como Principio del Palomar que pese a su simplicidad tiene un gran número de sorprendentes aplicaciones.
También conocido como Principio de Dirichlet, por haber sido el primero en usarlo, en su forma más sencilla establece que:
Si (n+1) palomas se meten en n palomares, al menos uno de los palomares contiene 2 palomas.
Aplicado a nuestro reto:
Metemos en el palomar 0 a las personas que tienen 0 conocidos, en el palomar 1 a las que tienen 1 y así sucesivamente hasta meter en el palomar 99 a las que tienen 99 conocidos.
Uno de los dos palomares, 0 y 99, tiene que estar vacío ya que si una persona no conoce a nadie, no puede haber otra que conozca a 99, de la misma manera que si una conoce a las 99 restantes, no puede haber otra que no conozca a ninguna.
De lo anterior se deduce que en alguno de los palomares restantes tiene que haber al menos 2 personas.
Para saber más
Engel, Artur. 1998. Problem-Solving Strategies. Springer
[El capítulo 4: The Box Principle está dedicado a la resolución de problemas con el Principio del Palomar]