Alumnos y paseos.

Este problema apareció el 12/5/14 en el envío semanal 10 de Olimpíada Matemática Argentina:

En una clase de 20 alumnos se organizan varios paseos. En cada paseo hay al menos un alumno que participa de ese paseo. Demostrar que hay un paseo tal que cada uno de los alumnos que fue a ese paseo también fue a por lo menos 1/20 del total de todos los paseos. 

Por suerte, los problemas de OMA no dejan de sorprenderme. Este en particular, porque apenas terminé de leerlo quedé tan perplejo como sencillo es el enunciado. Obviamente, como se imaginarán, releí el texto no menos de una docena de veces, y no tenía ni la menor idea por dónde empezar. Los envíos seguían llegando y este quedó relegado para cuando con tiempo y mucho coraje pudiera garabatear algo. Un día me lo propuse. Sólo transcribí la escasa información, pero no atiné a nada. Pasaron un par de semanas y volví a sentarme, y se me ocurrió algo.

Llamamos a a la cantidad de alumnos que asisten a por lo menos un paseo y p a la cantidad de paseos. Podemos escribir un conjunto fila de alumnos y un conjunto fila de paseos con el objeto de establecer que tipo de correspondencia y/o relaciones hay entre ellos. Por ejemplo, supongamos  a = 1 y p = 2:

 Ahora supongamos  a = 2 y p = 2:

Pasemos al caso  a = 3 y p = 2. Como a > p, hay algún P (no importa cual) que recibe a 2 alumnos:

Pero puede ser que algunos alumnos o todos vayan a más de un paseo:

El caso extremo es que todos los alumnos vayan a todos los paseos:

Mirando estos ejemplos descubrí estas relaciones:

Las salidas de las flechas de cualquier A me indican a cuantos paseos fue ese alumno.
Las llegadas de las flechas a cualquier P me indican cuántos alumnos fueron a ese paseo.
Como cada flecha tiene una "salida" y una "llegada", la suma de todas las salidas es igual a la suma de todas las llegadas e igual al total de flechas. Esto es, la suma de todos los paseos a los que fueron los a alumnos es igual a la suma de los alumnos que fueron a los p paseos.

Veamos que se cumplen en los tres últimos ejemplos:

Además, el mínimo de flechas es a (si a > p) y el máximo es a.p :

A partir de aquí, pude escudriñar un camino para resolver el problema. Como siempre, una parte queda para vos. Que disfrutes del paseo. Al fin y al cabo, de eso se trata un buen problema, de un buen viaje más allá de un buen destino.