IBM Research | Ponder This | March 2002 challenges

# Ponder This

## March 2002

<<February March April>>

Ponder This Challenge:

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.)

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Challenge: 03/01/2002 @ 9:00 AM EST
Solution: 03/31/2002 @ 3:00 PM EST
List Updated: 04/01/2002 @ 10:00 AM EST

Part 1 Correct
Alexander Nicholson (3.5.2002 @ 1:00 PM EDT)
Vadim Alexandrov(4.01.2002 @ 10:00 AM EDT)
Nagendra(4.01.2002 @ 10:00 AM EDT)
Arun(4.01.2002 @ 10:00 AM EDT)

Part 2 Correct
Alexander Nicholson (3.5.2002 @ 1:00 PM EDT)
John G.Fletcher(3.14.2002 @ 3:00 PM EDT)
Vince Lynch(3.18.2002 @ 5:00 PM EDT)
Sarang Aravamuthan(3.18.2002 @ 5:00 PM EDT)
Sriram Sankaranarayanan(3.25.2002 @ 5:00 PM EDT)
Andrew Byde(4.01.2002 @ 10:00 AM EDT)
Lance Gay(4.01.2002 @ 10:00 AM EDT)
Vadim Alexandrov(4.01.2002 @ 10:00 AM EDT)
Ross Millikan(4.01.2002 @ 10:00 AM EDT)
Victor Chang(4.01.2002 @ 10:00 AM EDT)

Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.