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 ti+1 tea drinkers and ci+1 coffee drinkers on day i+1, the number of influential edges going out of x is either ti+1 or ci+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 ti+1 tea drinkers and ci+1 coffee drinkers on day i+1, the number of influential edges going into x is the maximum of ti+1 and ci+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