Tourists and t-shirts
Source: All-Russian Olympiad 2006 finals, problem 11.8
May 6, 2006
ceiling functionfunctioncombinatorics proposedcombinatoricsProbabilistic Method
Problem Statement
At a tourist camp, each person has at least and at most friends among the other persons at the camp. Show that one can hand out a t-shirt to every person such that the t-shirts have (at most) different colors, and any person has friends whose t-shirts all have pairwisely different colors.