Ponder This Challenge - December 2013 - Gifts graph

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.

Solution

• Click here to view the solution

  The simplest solution is a star with four vertices:

  1111
  1100
  1010
  1001
  This gives 9/16 = 56.25%

  The best solution with up to eight vertices is structured like an Ethane molecule (C2H6), which gives 631/1120 =~ 56.339%
  10010000
  01010000
  00110000
  11111000
  00001111
  00001100
  00001010
  00001001

  And there are slightly better solutions: a cycle of length 5 with 3 extra nodes connected to every one of its vertices:
  11001111000000000000
  11100000111000000000
  01110000000111000000
  00111000000000111000
  10011000000000000111
  10000100000000000000
  10000010000000000000
  10000001000000000000
  01000000100000000000
  01000000010000000000
  01000000001000000000
  00100000000100000000
  00100000000010000000
  00100000000001000000
  00010000000000100000
  00010000000000010000
  00010000000000001000
  00001000000000000100
  00001000000000000010
  00001000000000000001
  which gives 81215/144144 = ~56.342%.

  ---

  If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solvers

• *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 Nas (12/03/2013 02:09 AM EDT)
• h (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)