Partition of a Group of Nine Persons
Source: Bulgarian IMO TST 2005, Day 2, Problem 3
July 7, 2013
graph theorycombinatorics proposedcombinatoricsRamsey Theory
Problem Statement
In a group of nine persons it is not possible to choose four persons such that every one knows the three others. Prove that this group of nine persons can be partitioned into four groups such that nobody knows anyone from his or her group.