Using your Head is Permitted

February 2011 solution

To simplify the terminology, we'll consider each employee as a vertex on a graph. The friendship relationships are modeled as edges between the vertices. Notably, even though friendship relationship is symmetric, and therefore suits a non-directional graph, we will, in the present proof, want to consider the friendship of x to y separately from the friendship of y to x. Therefore, we will model MegaCorp as a directional graph.

For employees that have an odd number of friends, the algorithm for choosing tea or coffee on any given day is very simple: they go with the majority of what their friends chose on the previous day. Employees that have an even number of friends have a slightly more complex algorithm, because they need to also account for the possibility of a tie. To simplify our own model of the problem, for all employees that have an even number of friends we will add a self-edge. This will make sure that all employees have an odd number of friends and ties cannot occur. Readers are left with the simple exercise to prove that this self-edge has the same effect as the original tie-breaker.

Let us define an edge from x to y as "influential" on day i if x's drink on day i is the same as y's drink on day i+1. Let us count how many influential edges there are in the graph on day i.

We sum over all x the number of edges from x to y that are influential. If, among x's friends, there are t_i+1 tea drinkers and c_i+1 coffee drinkers on day i+1, the number of influential edges going out of x is either t_i+1 or c_i+1 (depending on what x herself drank on day i). Summing over these for all x gives us the correct answer.

How many edges are influential on day i+1? Let us sum differently this time:

We sum over all x the number of edges from y to x that are influential. If, among x's friends, there are t_i+1 tea drinkers and c_i+1 coffee drinkers on day i+1, the number of influential edges going into x is the maximum of t_i+1 and c_i+1, because x herself, on day i+2, will, by design, always go with the majority. We see that for each x in the summation, the number of influential edges we counted on day i is no larger than the number of influential edges we counted on day i+1, so, summing over these for all x, we see that the total number of influential edges in the graph can never decrease from one day to the next.

The number cannot increase indefinitely, either, because it is bounded by the total number of edges in the graph. This means that at some point we will have two consecutive days, i and i+1, in which the total number of influential edges is the same. However, recalling the previous argument, this means that for all x, x drank on day i what the majority of her friends drank on day i+1, which is what she herself will drink again on day i+2. So, we have a cycle of period length 2 at most.

Back to riddle

Back to main page