Are you a professional problem solver? If so, we invite you to submit your “Ponder This” solution for this month’s challenge. Ponder This is IBM Research’s monthly brain-twister where you can match wits with some of the best minds at IBM.
Ponder This Challenge:
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.
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
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.
IBM Research will post the names of those who submit a correct, original solution to their website! If you don’t want your name posted then please include such a statement in your submission. Send your submission to the webmaster.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: firstname.lastname@example.org