Maths Olympiad Prep

Library / /24 of 73

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it Turkey

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 (a,b)(a, b) to either (a,a)(a, a) or (b,b)(b, b). 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 2292 \cdot 29 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 GG 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 GG will be decomposed into cycles of the form a,b,c,...,a,b,ca, b, c, ..., a, b, c. Since 3293 \nmid 29 we get a contradiction. Done.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.