Problem:
Members of a parliament participate in various committees. Each committee consists of at least 2 people, and it is known that every two committees have at least one member in common. Prove that it is possible to give each member a colored hat (hats are available in black, white or red) so that every committee contains at least two members with different hat colors.
Solution:
Pick a committee of smallest size and give one of its members a black hat and the rest of its members a white hat. Give everyone else who is not in this committee a red hat. Committee contains two colors of hats (black and white) by choice. Any other committee with the exact same members as also has black and white hats. Any committee whose membership is not identical to 's membership must contain a member that is not in , since it is not a subset of , which was chosen to be a smallest committee. Therefore, it must contain a red hat. But it also contains either a white or a black hat, since it shares a member with by assumption.