Problem

Source: 2022 Turkey JBMO TST P3

Tags: combinatorics



Each of the $29$ people attending a party wears one of three different types of hats. Call a person lucky if at least two of his friends wear different types of hats. Show that it is always possible to replace the hat of a person at this party with a hat of one of the other two types, in a way that the total number of lucky people is not reduced.