# 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