Given a finite group of boys and girls, a covering set of boys is a set of boys such that every girl knows at least one boy in that set; and a covering set of girls is a set of girls such that every boy knows at least one girl in that set. Prove that the number of covering sets of boys and the number of covering sets of girls have the same parity. (Acquaintance is assumed to be mutual.)
Solution
. A set of boys is separated from a set of girls if no boy in is an acquaintance of a girl in . Similarly, a set of girls is separated from a set of boys if no girl in is an acquaintance of a boy in . Since acquaintance is assumed mutual, separation is symmetric: is separated from if and only if is separated from .
This enables doubly counting the number of ordered pairs of separated sets , of boys, and , of girls, and thereby showing that it is congruent modulo 2 to both numbers in question.
Given a set of boys, let be the largest set of girls separated from , to deduce that is separated from exactly sets of girls. Consequently, which is clearly congruent modulo 2 to the number of covering sets of boys.
Mutatis mutandis, the argument applies to show congruent modulo 2 to the number of covering sets of girls.
Remark. The argument in this solution translates verbatim in terms of the adjacency matrix of the associated acquaintance graph.