A beautiful problem from a Hungarian Olympiad
Source: 2018 Kürshák Mathematical Competition 3rd problem
October 7, 2018
combinatoricsgraph theory
Problem Statement
In a village (where only dwarfs live) there are streets, and there are clubs each containing dwarfs. A dwarf can be in more than one clubs, and two dwarfs know each other if they live in the same street or they are in the same club (there is a club they are both in). Prove that is it possible to choose different dwarfs from different clubs (one dwarf from each club), such that the dwarfs know each other!