March 2002
<<February March April>>
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