Maths Olympiad Prep

Library / /335 of 520

Combinatorics Difficulty 6.7 National olympiad Prove it

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 XX of boys is separated from a set YY of girls if no boy in XX is an acquaintance of a girl in YY. Similarly, a set YY of girls is separated from a set XX of boys if no girl in YY is an acquaintance of a boy in XX. Since acquaintance is assumed mutual, separation is symmetric: XX is separated from YY if and only if YY is separated from XX.

This enables doubly counting the number nn of ordered pairs (X,Y)(X, Y) of separated sets XX, of boys, and YY, of girls, and thereby showing that it is congruent modulo 2 to both numbers in question.

Given a set XX of boys, let YXY_{X} be the largest set of girls separated from XX, to deduce that XX is separated from exactly 2YX2^{\left|Y_{X}\right|} sets of girls. Consequently, n=X2YXn=\sum_{X} 2^{\left|Y_{X}\right|} which is clearly congruent modulo 2 to the number of covering sets of boys.

Mutatis mutandis, the argument applies to show nn 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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.