Teo. Hay un Hombre para cada Mujer si y sólo si, para cada subconjunto de mujeres la cantidad de hombres que les gustan es mayor o igual al número de mujeres del subconjunto.
(Nota: utilizaremos el signo * como unión de conjuntos.)
D
EM. La ida se debe a que si existe un conjunto de chicas al que le gusta menos hombres que el numero de chicas del conjunto, pues una chica es lesbiana o asexual, por lo que no quiere a ningun hombre. Entonces partimos de que a cada mujer le gusta al menos un hombre.
El regreso se hará por inducción sobre el numero de mujeres. Si hubiera una sola mujer (además de que todos estariamos aperrados por ella), pues, le gustaría al menos alguien y tiene la libertad de escoger a quien se le de la gana.
Supongamos que el teorema es válido para
m mujeres.
Consideremos un conjunto ordenado de
m+1 mujeres. Supongamos que cada mujer
i, tiene una lista
Si de hombres que le gustan,
Si≠ø. Supongamos que el teorema es falso, entonces existe una mujer sin hombre, digamos que es la mujer
m+1, entonces el conjunto
Sm+1 esta contenido en la unión de los conjuntos
Si desde
i=1 hasta
m, de lo contrario existiria un hombre que no le gusta a ninguna de las anteriores
m mujeres y que le gusta a la mujer
m+1. Por hipótesis de inducción, si quitamos a la mujer
m+1, tenemos que existen un hombre para cada una de las
m mujeres. Como el conjunto
Sm+1 esta contenido en la unión de los conjuntos
Si desde
i=1 hasta
m, la mujer
m+1, comparte gustos con alguna mujer, sin perdida de generalidad podemos decir que es la mujer
m, y como |
Sm+1*
Sm|≥|{
m+1,m}|=2, pues podemos escoger un hombre para la mujer
m+1, si escogemos a un hombre
m+1 distinto al hombre que le tocaba a la mujer
m desde un principio, habriamos concluido la prueba. Entonces supongamos que escogimos el mismo, por lo que ahora es la mujer
m la que no tiene hombre. De nuevo, si existiera un hombre en la lista de la mujer
m que no estuviera en las listas de las otras, lo escogemos y acabamos la prueba. Por lo que comparte gustos con otra mujer, que además es distinta de la mujer
m+1, pues |
Sm+1*
Sm|≥|{
m+1,m}|=2. Digamos, reordenando el conjunto de mujeres que la mujer
m comparte gustos con la mujer
m-1. Por hipótesis, |
Sm*
Sm-1|≥|{
m,m-1}|=2, por lo que de nuevo podemos elegir a un hombre para la mujer
m. Si fuera distinto el hombre que elgimos para la mujer
m-1, acabariamos la prueba, si no, repetimos el procedimento para la mujer
m-1, que, como es finito llega a un final. Es más, a un final feliz.□
Hay muchas razones por las cuales el teorema no se aplica, empezando porque hay más mujeres que hombres, pero bueno, ya saben chicas, ustedes hagan grandes listas de hombres, alguno les debe de tocar. Y hombres, no nos hagamos, ellas nos escogen.