Each of 29 guests at the party wear a hat of one of three colours. A guest is a lucky if at least two of its friends in the party wear differently coloured hats. Show that it is always possible to choose a guest and to change its hat to hat of one of the remaining two colours such that the total number of lucky guests will not be decreased.
Solution
Assume the contrary. Each lucky guest has at least two friends. Note that a lucky guest having exactly 2 friends can be made unlucky in two different ways: the hat colours of her friends should be changed from to either or . A lucky guest having at least 3 friends can be made unlucky in just one way: the hat colour of her uniquely determined friend should be changed to uniquely determined colour. There are possibilities to change hat colour of one guest. If each of these changes produces some unlucky guest then each person should have exactly two friends. Consider a graph where vertices correspond guests and two vertices are adjacent if and only if guest corresponding to these vertices are friends. Let us colour vertices according to hat colours of corresponding guests. Then will be decomposed into cycles of the form . Since we get a contradiction. Done.