Using your Head is Permitted

December 2013 riddle

This month, Using your Head is Permitted is teaming up again with IBM's Ponder This. See the Ponder This December challenge for a riddle related to this one.

Every Christmas, the employees of MegaCorp play a gift-giving lottery game. On the first of December, each of the company's N employees picks a number between 1 and N out of a hat (the same hat) to be their unique ID number in the game. On Christmas day, each employee sends a gift to the person who has the highest ID number among all employees who are directly connected to them on LinkedIn. We consider every employee to be connected to herself, so if every one of an employee's connections has a lower ID number than herself, that employee will be sending a self-addressed Christmas present.

The question:
Prove that for no connected graph of LinkedIn connections (with more than a single employee) this game ends up with more than 3/4 of the employees receiving gifts, in expectation. (Bonus for proving tighter bounds.) The order of the IDs is taken here to be random and uniformly distributed among all N! possibilities.

Note that in a valid graph of LinkedIn connections, for any i and j, if i is connected to j then j is connected to i.

List of solvers:

Radu-Alexandru Todor (*) (10 December 11:55)
Lian Wang (17 December 21:57)
Thomas Mack (*) (20 December 23:13)
Yury Volvovskiy (*) (26 December 13:23)

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