Each of n guests at a party wears a hat of one of three distinct colors.
A guest is said to be lucky if at least two of his/her friends in the party wear differently colored hats.
Determine all possible values of n for which it is always possible to choose a guest and to change his/her hat to hat of one
of the remaining two colors such that the total number of lucky guests will not be decreased.
Note: For any pair of partygoers, they are either mutual friends or mutual strangers.
This is how I interpreted the problem.
We can divide the party into cliques. Within each clique everyone is friends, but any pair of people from two different clique are strangers.
A clique of 1 or 2 people can have a hat changed and not change the number of lucky people, since those people don't have enough friends to be lucky.
In one case changing a hat in a clique of 3 people can decrease the number of lucky people, the case where each person in the clique has a different hat color.
In any clique of four or more people we can always look at which hat color is the most frequent and change one of those hats and that will not decrease the number of lucky people.
So in a full party it is possible to change one hat so long as the party does not consist solely of 3 person cliques, where each clique has one of each color hat.
Then to answer the question, if the number of partygoers is not a multiple of 3 then it will always be possible to find a person and change their hat and not decrease the number of lucky people.
Solution?
