Members can be distributed to several rooms
Source: Tuymaada 2008, Senior League, First Day, Problem 4.
July 18, 2008
combinatorics
Problem Statement
A group of persons is called good if its members can be distributed to several rooms so that nobody is acquainted with any person in the same room
but it is possible to choose a person from each room so that all the chosen persons are acquainted with each other.
A group is called perfect if it is good and every set of its members is also good.
A perfect group planned a party. However one of its members, Alice, brought here acquaintance Bob, who was not originally expected, and introduced him to all her other acquaintances. Prove that the new group is also perfect.
Author: C. Berge