December 2013
<<November December January>>
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.
We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!
We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com
Challenge:
11/29/2013 @ 01:00 PM EST
Solution:
01/02/2014 @ 01:00 PM EST
List Updated:
11/29/2013 @ 01:00 PM EST
People who answered correctly:
*Cynthia Beauchemin (11/29/2013 05:06 PM EDT)
Nicholas Ngiam & Liu Ren Wei (11/29/2013 06:00 PM EDT)
Philipp Seemann (11/29/2013 06:10 PM EDT)
Miha Muškinja (11/29/2013 07:16 PM EDT)
*Florian Fischer (11/29/2013 07:48 PM EDT)
*Radu-Alexandru Todor (11/29/2013 08:39 PM EDT)
Lars Nagel (11/29/2013 09:14 PM EDT)
*Benjamin Brumfield (11/29/2013 09:25 PM EDT)
*Adrian Orzepowski (11/30/2013 01:59 AM EDT)
*Ziqi Zhu (11/30/2013 05:37 AM EDT)
Alex Fleischer (11/30/2013 06:14 AM EDT)
Anatoli Plotnikov (11/30/2013 06:45 AM EDT)
*Vladimir Sedach (11/30/2013 09:10 AM EDT)
*Dan Dima (11/30/2013 10:39 AM EDT)
Lorenz Reichel (11/30/2013 12:30 PM EDT)
John Tromp (11/30/2013 06:01 PM EDT)
*Chudi Wang (11/30/2013 08:40 PM EDT)
Leandro Araújo (11/30/2013 11:21 PM EDT)
*Jesús Sanz (12/01/2013 04:45 AM EDT)
Michael Wilms (12/01/2013 04:53 AM EDT)
Shirish Chinchalkar (12/01/2013 07:32 AM EDT)
*Gilad Weiss (12/01/2013 09:09 AM EDT)
Pawel Milewski (12/01/2013 09:48 AM EDT)
Andreas Razen (12/01/2013 11:23 AM EDT)
*Walter Schmidt (12/01/2013 01:01 PM EDT)
*Reiner Martin (12/01/2013 02:16 PM EDT)
*Peter Gerritson (12/01/2013 02:31 PM EDT)
Dieter Beckerle (12/01/2013 03:40 PM EDT)
*Olivier Mercier (12/01/2013 06:14 PM EDT)
ZQ Bai (12/01/2013 08:54 PM EDT)
Benjamin Phillabaum (12/01/2013 10:05 PM EDT)
*Fedor Duzhin (12/02/2013 02:10 AM EDT)
Xia Dayu (12/02/2013 04:23 AM EDT)
Jgan (12/02/2013 06:36 AM EDT)
*José Eduardo Gaboardi de Carvalho (12/02/2013 06:50 AM EDT)
David Greer (12/02/2013 09:13 AM EDT)
János Csorba (12/02/2013 10:22 AM EDT)
*Don Dodson (12/02/2013 11:07 AM EDT)
I. J. Kennedy (12/02/2013 12:22 PM EDT)
Kan Shen (12/02/2013 12:35 PM EDT)
Tao Liu (12/02/2013 02:53 PM EDT)
Harald Bögeholz (12/02/2013 04:06 PM EDT)
*David Friedman (12/02/2013 08:37 PM EDT)
János Kramár (12/02/2013 10:21 PM EDT)
Movin Jain (12/03/2013 12:46 AM EDT)
Umut Uludag (12/03/2013 01:25 AM EDT)
*Jeffrey Nash (12/03/2013 02:09 AM EDT)
Christopher Marks (12/03/2013 02:45 AM EDT)
*Miha Muškinja (12/03/2013 04:00 AM EDT)
*Delfino Terol (12/03/2013 04:46 AM EDT)
Aviv Nisgav (12/03/2013 05:37 AM EDT)
Daniel König (12/03/2013 07:25 AM EDT)
*Andrew Gacek (12/03/2013 08:30 AM EDT)
*Andreas Stiller (12/03/2013 09:13 AM EDT)
Andreas Allemann (12/03/2013 01:06 PM EDT)
Alok Menghrajani (12/03/2013 01:09 PM EDT)
*Brian Mathason (12/04/2013 08:17 AM EDT)
*Joseph DeVincentis (12/04/2013 10:04 AM EDT)
John Duffield (12/04/2013 10:12 AM EDT)
*Tony Harrison (12/04/2013 04:15 PM EDT)
*Liubing Yu (12/05/2013 04:11 PM EDT)
*Michael Gurvich & Chintan Maggu (12/05/2013 08:16 PM EDT)
*Nell Kopel (12/06/2013 12:49 PM EDT)
*Tom Harley (12/06/2013 02:10 PM EDT)
Jeremy Kerfs (12/07/2013 12:04 AM EDT)
*James Dow Allen (12/07/2013 02:31 AM EDT)
*Clive Tong (12/07/2013 03:51 AM EDT)
*Sergey Subbotin (12/07/2013 06:50 AM EDT)
*Eugene Lee (12/07/2013 11:41 AM EDT)
*Katherine Oh (12/07/2013 01:57 PM EDT)
*David Chang (12/07/2013 07:56 PM EDT)
Zhenfei Liu (12/08/2013 12:27 AM EDT)
*Aharon Malachi (12/08/2013 01:49 AM EDT)
*Dieter Beckerle (12/08/2013 02:43 AM EDT)
*Andrea Andenna (12/08/2013 03:30 AM EDT)
*Daniel Bitin (12/08/2013 07:19 AM EDT)
*Todd Will (12/08/2013 11:46 AM EDT)
Payman Karvani (12/09/2013 12:07 AM EDT)
*Stéphane Higueret (12/09/2013 02:13 PM EDT)
*Jaesung Son (12/09/2013 03:18 PM EDT)
Nagendra Gulur (12/09/2013 04:09 AM EDT)
*Joe Clark (12/09/2013 04:16 PM EDT)
Bruno Santos (12/10/2013 06:32 AM EDT)
Michael Rosola (12/10/2013 09:43 AM EDT)
*Arthur Breitman (12/11/2013 10:11 AM EDT)
Milos Cubrilo (12/11/2013 01:15 PM EDT)
Yong Sun (12/11/2013 02:19 PM EDT)
Guillaume Bioche (12/11/2013 03:05 PM EDT)
Daniil Agashiyev (12/11/2013 04:12 PM EDT)
Chris Becker (12/11/2013 05:41 PM EDT)
*Edward Sullivan (12/11/2013 06:08 PM EDT)
*Andrei Prudius & Satish Vedantam (12/11/2013 07:01 PM EDT)
*Gyorgy Gyomai (12/12/2013 12:11 PM EDT)
*Maithem Munshed (12/11/2013 11:32 PM EDT)
*Vukasin Vucevic (12/12/2013 03:58 AM EDT)
*Guillaume Bioche (12/13/2013 04:01 PM EDT)
*Milos Cubrilo (12/14/2013 04:38 AM EDT)
*Ramezan Paravi Torghabeh (12/14/2013 07:37 PM EDT)
Franza Cavalcante Jr (12/16/2013 12:27 PM EDT)
*Hakan Summakoglu (12/16/2013 02:05 PM EDT)
*Marcel Caria (12/16/2013 02:35 PM EDT)
Shmuel Menachem Spiegel (12/16/2013 11:02 PM EDT)
*Antoine Comeau (12/17/2013 12:51 AM EDT)
*Stefano Leucci (12/17/2013 06:07 AM EDT)
*Armin Krauss (12/18/2013 04:41 AM EDT)
Shouky Dan & Tamir Ganor (12/18/2013 01:11 PM EDT)
*Brian Li (12/18/2013 04:25 PM EDT)
Raúl Mora Pastor (12/19/2013 08:54 AM EDT)
*Hugo Pfoertner (12/19/2013 02:14 PM EDT)
Marco Bellocchi (12/19/2013 07:00 PM EDT)
Ruchir Santuka (12/19/2013 08:09 PM EDT)
Sri Mallikarjun J (12/20/2013 05:42 PM EDT)
Bruno Curfs (12/22/2013 02:56 PM EDT)
*Jan Fricke (12/22/2013 04:03 PM EDT)
Jayakumar Hoskere (12/23/2013 08:44 AM EDT)
*Luke Pebody (12/24/2013 07:08 AM EDT)
*Tamir Ganor (12/24/2013 09:28 AM EDT)
Jacob Levinson (12/26/2013 12:45 PM EDT)
Juha Saukkola (12/25/2013 09:35 PM EDT)
*Oleg Vlasii (12/26/2013 05:47 PM EDT)
*Motty Porat (12/26/2013 08:02 PM EDT)
*Shmuel Menachem Spiegel (12/26/2013 10:59 PM EDT)
*Maris Van Sprang (12/28/2013 03:08 AM EDT)
*Peter Shim (12/30/2013 10:09 AM EDT)
*Michael Wilms (12/31/2013 01:25 PM EDT)
Michael Schuresko (12/31/2013 06:11 PM EDT)
Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.