Maths Olympiad Prep

Library / /17 of 23

Combinatorics Difficulty 6.8 National olympiad Prove it Ireland

There are some boys and some girls at a party. A set of boys is said to be sociable if every girl at the party knows at least one boy in that set, and similarly a set of girls is said to be sociable if every boy at the party knows at least one girl in that set.
Suppose that the number of sociable sets of boys is odd. Prove that the number of sociable sets of girls is also odd.

NOTE: Acquaintance is mutual.

Solution

We say that a set XX of boys is separated from a set YY of girls if no boy in XX knows any girl in YY. Similarly, a set YY of girls is separated from a set XX of boys if no girl in YY knows any boy in XX. Since acquaintance is mutual, separation is symmetric: XX is separated from YY if and only if YY is separated from XX.

Let nn denote the number of ordered pairs (X,Y)(X, Y) such that XX is a subset of boys, YY is a subset of girls, and XX is separated from YY.

For any set XX of boys, denote by Y(X)Y(X) the set of girls who are not acquainted with any boy in XX. Then XX is separated from exactly 2Y(X)2^{|Y(X)|} sets of girls, and so
n=XB2Y(X). n = \sum_{X \subset B} 2^{|Y(X)|}.
Exactly those terms in the sum are odd for which Y(X)Y(X) is empty, i.e., when XX is sociable. Therefore nn is congruent modulo 22 to the number of sociable sets of boys.

A similar argument shows that nn is congruent modulo 22 to the number of sociable sets of girls. Therefore, if the number of sociable sets of boys is odd, then the number of sociable sets of girls is also odd.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.