Q1 Matemática  (Romanian Masters of Mathematics Collection 2012)

Dado um número finito de meninos e meninas, um conjunto sociável de meninos é um conjunto de meninos tal que cada menina conhece pelo menos um menino nesse conjunto; e um conjunto sociável de meninas é um conjunto de meninas tal que cada menino conhece pelo menos uma menina nesse conjunto. Prove que o número de conjuntos sociáveis de meninos e o número de conjuntos sociáveis de meninas têm a mesma paridade. (Assume-se que o conhecimento é mútuo.) (Polônia) Marek Cygan