IBM Ponder This #188 · December 2013

This month's challenge is from Michael Brand (thanks!) and a related riddle can be found as the December challenge on his site ("Using your Head is Permitted", http://www.brand.site.co.il/riddles).

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 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:

Find a connected graph of LinkedIn connections (with more than a single employee) for which, averaging over a random order of IDs, this game ends up with at least 9/16 of the employees receiving gifts. (Bonus for getting higher results.)

Supply your answer as an adjacency matrix, i.e., a table of bits where the j'th bit in the i'th line is 1 if and only if i is connected to j.

For example, the following matrix

1111

1110

1110

1001

corresponds to a connections graph in which the first three people are connected to each other and the fourth is only connected to the first. For this graph, the expected portion of the people to receive presents is 43.75%. Note that in a valid matrix such as the one given in the example, for any i and j, if i is connected to j then j is connected to i.

Solution

Best opened after a real attempt

To be added.