Problema 3 OMM 2003

Sean $m_1,m_2,...,m_n$ las muchachas y $h_1,h_2,...,h_n$ los muchachos. Las parejas posibles son$(m_1,h_1),(m_1,h_2),...,(m_n,h_1),(m_n,h_2),...(m_n,h_n)$, y son $n^2$ parejas. Queremos asegurar que una de esas parejas, digamos la $(m_i,h_j)$ es tal que $m_i$ y $h_j$ se gustan mutuamente. Por otro lado, para cada $m_i$ hay $a$ parejas y para cada $h_j$ hay $b$ parejas, de tal manera que las preferencias de las muchachas forman $an$ parejas y las preferencias de los muchachos forman $bn$ parejas. Para que haya una pareja en la cual sus miembros se gusten mutuamente, debe haber por lo menos una pareja perteneciente a las preferencias de las muchachas ($an$ en total) que también pertenezca a las parejas de las preferencias de los muchachos ($bn$ en total) Si ninguna pareja se repitiera, ello significaría que $an+bn$ es menor que $n^2$ (porque se cuentan todas las parejas de preferencia femenina y todas las parejas de preferencia masculina y no se repiten). En otras palabras, si no hay una pareja cuyos miembros se gusten mutuamente entonces $an+bn \leq n^2$ Pero esta es precisamente la contrapositiva de la proposición "si $an+bn$ > $n^2$ entonces existe una pareja cuyos miembros se gustan mutuamente". En conclusión, para que forzosamente haya un muchacho y una muchacha que se gusten mutuamente la condición suficiente es que $an+bn$>$n^2$, es decir $a+b$ >$n$.