Teorema del matrimonio de Hall $2n$ Grajos en $2n \times 2n$ tablero

Question

He visto esta pregunta en https://brilliant.org/wiki/applications-of-hall-marriage-theorem/ . No consigo resolverlo, ¡agradecería cualquier ayuda!

En un $2n \times 2n$ tablero de ajedrez, hay $n$ torres en cada fila y cada columna del tablero. Demuestre que existen $2n$ torres que pertenecen a filas y columnas distintas.

Answer 1

Consideremos el grafo bipartito en el que el primer conjunto de vértices es el conjunto de filas, el segundo conjunto de vértices es el conjunto de columnas, y hay una arista entre una fila y una columna si y sólo si el cuadrado correspondiente a esa fila y columna tiene una torre en él.

Debemos comprobar que este gráfico cumple la condición de Hall.

Así que coge un conjunto de $k$ filas, debemos demostrar que las torres en estas filas cubren al menos $k$ columnas.

Supongamos que este no es el caso, entonces claramente $k$ es mayor que $n$ (porque cada fila tiene $n$ torres). Pero si $k>n$ ¡también es imposible, porque cada columna tiene que contener al menos una torre en una de las filas ! (porque de lo contrario cada columna tendría como máximo $n-k$ torres, que es menos que $n$ ).

Por lo tanto, este gráfico satisface la condición de Hall, y por lo tanto tiene una correspondencia perfecta, que se traduce precisamente en lo que queremos.