64. LA FIESTA
|
64. LA FIESTA |
|
|
En una fiesta de 20 personas hay exactamente 49 pares de personas que se conocían entre sí. Probar que alguna persona conocía a lo sumo a 4 de los asistentes. Hay varias maneras de resolver el problema, una de ellas es la siguientee: Designando a las personas por P1, P2, ..., P20, construimos una matriz de 20x20 según las siguientes reglas: si ij, en la posición (i , j) escribimos un uno si Pi conoce a Pj, y un cero en caso contrario. En las posiciones (i , i), colocamos un asterico. La hipótesis del problema asegura que en la matriz hay exactamente 49x2=98 unos, ya que si en la posición (i , j) hay un uno también lo habrá en la posición (j , i). Ahora bien, si en cada fila hubiera al menos 5 unos, el número total de unos sería al menos 100, ya que hay 20 filas. En consecuencia, en alguna fila hay a lo sumo 4 unos, esto es, alguna persona conocía a lo sumo 4 de los asistentes, como queríamos demostrar. |