Ponder This Challenge - March 2002 - Coffe or tea majority club

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

Solution

• Click here to view the solution

  Answer 1:
  Let t=1 denote the first week.
  For member x, let x(t) denote either "Coffee" or "Tea", whichever member x drinks in week t.
  (We are resisting the impulse to joke about drinking weak tea during week t.)

  For t>1, define g(x,t) to be twice the number of friends y of x such that
  x(t)=y(t-1), plus one if x(t)=x(t-1).
  For t>2, define h(x,t) to be twice the number of friends y of x such that
  x(t-2)=y(t-1), plus one if x(t-2)=x(t-1).

  For t>1, define f(t) to be twice the number of pairs (x,y) of friends such that
  x(t)=y(t-1) (both (x,y) and (y,x) should be considered),
  plus the number of members x such that x(t)=x(t-1).

  Claim 1: f(t) = sum g(x,t), where the sum runs over members x.

  Claim 2: f(t-1) = sum h(x,t), where the sum again runs over x. (This uses the fact that if (x,y) is an edge then (y,x) is an edge.)

  Claim 3: g(x,t) is at least as large as h(x,t).
  That's because they differ only in the choice of x(t), and x(t) is chosen to make g(x,t) as large as possible, because of the majority vote with the tie-breaker.
  Further, g(x,t)=h(x,t) only if x(t)=x(t-2). (If x(t) is different from x(t-2) then exactly one of g(x,t), h(x,t) is even and the other is odd.)

  Clearly f(t) is an integer function of t.
  Also f(t) is at least as large as f(t-1), with f(t)=f(t-1) only when x(t)=x(t-2) for all x.
  Also f(t) is nonnegative, and it is bounded above by 2N(N-1)+N, where N is the number of members.
  Wait until f hits its maximum at f(T); then for all t>T+1, we have x(t)=x(t-2).
  So the club's behavior is periodic with period 1 or 2 after time T.

  An example of period 2 is a bipartite graph: the only friendships are between men and women, all men initially drink tea and all women initially drink coffee. Then each week they exchange roles.

  Answer 2:
  The following elegant solution to Part 2 was given by Alexander Nicholson.

  A club with 1000 members that has the friendship graph
  1--2--3--4--...--998--999--1000 and starts with the assignment (1,1,0,1,0,1,0,1,...,0,1) (i.e. all even-numbered members, as well as member 1, drink coffee on the first week, and tea for all odd-numbered members except member 1), will run for 998 weeks before settling into an all-coffee regime on the 999th week.

  ---

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

Solvers

• Part 1 Correct (None)
• 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 (None)
• 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)