Problem #03 - a quarrel in the Shire

 

 the scenery in which this problem takes place

Once again I bring you a problem alongside my proposed solution. If you find any mistakes or come up with a different solution, please let me know!

Problem statement (and a lovely short story):
The Shire is a lovely place where $N $ hobbits live in perfect harmony. Or at least they lived, until a hobbit decided to become an outside decorator and convinced some of its friends to paint their front doors with a very "fashionable" purple (all doors were yellow before that preposterous change).

Overnight, the perfect balance and harmony in which the hobbits lived shattered, and hobbits whose doors were different colours couldn't stand one another.

Worried, the great and wise Gandalf hurried to the Shire to try and settle this matter. This was what he decided to do: in alphabetical order, he would visit each hobbit. When visiting a hobbit $h $, he would change the colour of its door if and only if there were more hobbits mad at him than there were hobbits at peace with him. After visiting each hobbit once, he would visit them all again in the same order, and then again, and then again, ..., repeating this process until a complete round of visits didn't change a thing.

Q: Is Gandalf's task always going to end, regardless of $N$ and of the way the doors are coloured when he first arrives? Or are there values of $N$ and/or door colourings such that Gandalf will have to spend an eternity trying to solve the hobbits' problems?

Gandalf's endeavour is always a finite one.

Look for a "semi-invariant"; a quantity that can only change in a certain way, which allows you to verify that Gandalf will rest eventually.

Solution:
Gandalf's task always has an end. To see why, imagine the $N$ hobbits represented as dots, and every two hobbits are connected by a line. That line is green if they are friendly towards each other (their front doors have the same colour) and red if their front doors have different colours. Now count the number of red lines in that representation and call it $R_0$, where the $0$ indicates the number of visits Gandalf has already paid to the hobbits. If Gandalf already visited $t$ hobbits, let $R_t$ denote the number of red lines in the representation I defined earlier.

It should be fairly easy to see that we have $R_{t+1} \leq R_t$. This is true because when Gandalf visits a hobbit, he will only change its door if that means the number of green lines increases, i.e. the number of red lines decreases. This means only two things can happen:

1.  For a certain $k$, $R_k = 0$ and that means all hobbits are now friendly towards each other;
2.  For some $k, R_{k+N} = R_k$, which means that Gandalf visited every single hobbit in the Shire and didn't change a single door, which means his visits have no impact whatsoever.

Either way, we can see that another complete round of visits by Gandalf would change nothing, and thus Gandalf can now rest. QED

Bonus question: is there any $N > 1$ for which you can find a non-trivial starting configuration that doesn't change under the efforts of Gandalf?

Let me know what you think!

-RGS