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.