Using your Head is Permitted

February 2011 riddle

UPDATE (1 March): Despite the fact that one solution has already been submitted to this month's riddle, the riddle will run an extra month in order to give other solvers additional opportunity to reach a solution.

For all who enjoyed the September 2010 riddle, here is another one from the same source: it was relayed to me by Oded Margalit, who heard it from Noga Alon.

In the company MegaCorp, all employees arrive at 8:00am sharp every day, and immediately proceed to brew either a cup of tea or a cup of coffee.

Besides this caffeine dependency, the employees of MegaCorp are also highly susceptible to peer pressure. The way this works is as follows: each one of the employees of MegaCorp has a set of other employees that that employee views as her friends. (Friendship is a symmetric relationship.) At 8:00am, when employees drink their morning drinks, each one of them observes the tea/coffee choice of the rest of her peer group. If, in the group, there is a majority for tea, the next day that employee will make tea for herself. If there is a majority for coffee, she will go with coffee. If there is a tie, the employee will simply drink the following day whatever she had to drink on the previous day.

The question: it is clear that ultimately the drinking patterns of MegaCorp's employees will settle on a cycle. Show that this cycle has a period length of at most two.

List of solvers:

Sumit Sanghai and Dharmadeep Muppalla (3 February 20:34)

Elegant and original solutions can be submitted to the puzzlemaster at Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.


To solution

Back to main page