IBM Ponder This #047 · March 2002

This month's puzzle is based on a suggestion by Sharon Sela.

A club contains a finite number of members.
Some pairs of these members are friends (see the "fine print" below).They meet once a week and each member drinks one cup of either tea or coffee. At the first meeting each selects his favorite drink, but starting from the second week he chooses what to drink according to the following rule:

He remembers what each of his friends drank last week and chooses what the majority of them drank. If there was a tie (an equal number of coffee and tea drinkers among them) he drinks the same as he did last week.

Now suppose this club runs forever. It is easy to see that this process eventually becomes periodic because each state depends only on the previous one and there are only a finite number of possible choices.

Question 1:
Prove that the eventual period is 1 or 2 .
Question 2:
Show that a club with 1000 members might run 18 years before reaching its periodicity. Can it go longer?

( "Friendship" is symmetric but not reflexive and not necessarily transitive. This means that if Bob is Charlie's friend then Charlie is Bob's friend; Bob is not his own friend; if Bob and Charlie are friends and Charlie and David are friends, we cannot conclude whether or not Bob and David are friends. Also, friendships are permanent: Bob and Charlie are friends this week if and only if they were friends last week. Club membership is also permanent. So we're talking about an undirected graph with no loops or multiple edges -- same as always.)

Solution

Best opened after a real attempt

To be added.