Xa levamos varias entradas dándolle voltas ao seguinte resultado.
Teorema do matrimonio de Hall. Dado un grafo bipartito $G=(X,Y)$, unha condición necesaria e suficiente para que $X$ teña un emparellamento perfecto (condición de Hall) é que $\forall A\subset X$ se verifique que $ \left| A \right|\le \left| N\left( A \right) \right|$
Xa vimos como se podía aplicar ao establecemento de trucos de maxia ou á resolución do problema do matrimonio. Agora toca aplicalo a novos problemas.
Unha carta de cada valor. Colocamos as 40 cartas dunha baralla española en 10 columnas de 4 cartas. Poderemos sempre, escollendo unha carta de cada columna, obter todos os valores (do as ao rei)?
Na seguinte imaxe temos un exemplo. Podes comprobar que neste caso si que podemos escoller unha carta de cada columna.
No exemplo da imaxe podemos coller de dereita a esquerda 1, 2, 3, 4, 5, 6, 7, Sota, Rei e Cabalo. A cuestión, claro, é se sempre é posible.
Para iso establecemos un grafo bipartito. Por unha banda temos os 10 vértices que nos representan os 10 valores das cartas: 1, 2, 3, ,4 5, 6, 7, S, C, R. Por outra os 10 vértices que representan os 10 montóns $m_{1},m_{2},...,m_{10}$. Conectamos cada montón con todos os valores que conteña. Dado un subconxunto $A$ calquera de $k$ valores teremos a súa veciñanza $ N\left( A \right) $ isto é, o conxunto de vértices (montóns) que están conectados con algún dos vértices de $A$. Supoñamos que $\left| N\left( A \right) \right|\lt k$. Isto significa que hai como moito $k-1$ montóns que conteñen as $4k$ cartas representadas por $A$. Pero en $k-1$ montóns só hai $4k-4$ cartas! De aí que a suposición que fixemos debe ser falsa. A conclusión é que se verifica a condición de Hall para calquera colección de valores: $\left| A \right|\le \left| N\left( A \right) \right|$. De aí que sempre poidamos establecer un emparellamento perfecto entre valores e montóns. Ademais este razoamento é completamente xeral polo que tamén é valido no caso de que quixeramos escoller os 13 valores distintos dunha baralla francesa distribuídos nunha matriz $4 \times 13$. Quizais sobra dicilo, pero tamén é factible escoller sempre unha carta de cada pau collendo unha carta de cada fila. Claro que esta posibilidade preséntase como menos espectacular.
Sempre gañadores
O seguinte problema ten certo empaque. Apareceu na competición Putnam do ano 2012.
Sempre gañadores. $2n$ equipos xogan un torneo de todos contra todos. Durante $2n-1$ días cada equipo xoga exactamente contra un adversario distinto. Non hai empates.
Demostra que podemos escoller un equipo gañador diario sen que repitamos ningún equipo dúas veces.
O razoamento terá moitas concomitancias co anterior. Realizarémolo por redución ao absurdo. Comezamos establecendo un grafo bipartito con $2n-1$ vértices representando a cada un dos dos días do torneo e outros $2n$ vértices identificando cada un dos equipos participantes. As arestas unen cada equipo cos días nos que gaña.
Razoaremos por deución ao absurdo. Supoñamos que non hai un emparellamento perfecto. Daquela non se verificará a condición de Hall e existirá un subconxunto $A$ de $k$ días tal que $\left| N\left( A \right) \right|\lt k$: neses días hai menos de $k$ gañadores. Velaí que haberá un xogador que perdeu todos os partidos durante eses $k$ días. Pero isto asegura que debe haber $k$ equipos gañadores diferentes nese período. Xa obtivemos a contradición.
Agochado no enunciado hai outro problema, o de establecer un calendario para unha liga na que $2n$ equipos xoguen todos contra todos. Pódese facer? Como? A pouco que un o pense decatarase de que é posible realizala, e de moitas maneiras distintas. No libro de Oystein Ore, Graphs and their uses (MAA 1990) ofrécese unha solución para o caso xeral.
