Ponder This: December’s Challenge!

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.

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.

__________

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: webmster@us.ibm.com

Comments

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s