March 2002
<<February March April>>
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
People who answered correctly:
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.