Puzzle
4 minute read

Ponder This Challenge - December 2017 - Quad9 six degrees of separation

Recently, IBM announced the free Quad-9 service to protect your computer systems. This reminded us of the six degrees of separation idea that claims that every two people are no more six acquaintances apart when counting the minimal length of a chain of friends connecting them.
Of course, one can create a world where this rule does not hold.

Let's assume that our (small) world has only 100 people, and every one of them knows exactly nine other people, and that knowing someone must be symmetrical (i.e., a knows b if and only if b knows a).

What is the largest diameter of this connection graph?

To be listed as a solver - send us a possible "knowing graph" where there are at least two people whose shortest chain is 27 hops long.

Number the people from 1 to 100 and list the solution in 100 lines of nine numbers each.

There is a solution for a world of 12 people in which each person knows exactly three others with a chain length of six hops. However, to clarify the format, here is an example of that 12-person world with a maximum chain of three hops (the first line means that #1's friends are 2,7,12; the last line means that #12's friends are 1,6,11):

2 7 12
1 3 8
2 4 9
3 5 10
4 6 11
5 7 12
1 6 8
2 7 9
3 8 10
4 9 11
5 10 12
1 6 11

Solution

Solvers

  • Bryce Herdt (01/12/17 09:51 AM IDT)
  • Dan Dima (01/12/17 02:31 PM IDT)
  • Ariel Landau (01/12/17 05:50 PM IDT)
  • Oleg Vlasii (01/12/17 07:08 PM IDT)
  • Joseph DeVincentis (01/12/17 10:35 PM IDT)
  • Adam Daire (01/12/17 11:34 PM IDT)
  • Bert Dobbelaere (01/12/17 11:47 PM IDT)
  • Uoti Urpala (02/12/17 01:47 AM IDT)
  • Patrik Holopainen (02/12/17 03:57 AM IDT)
  • Kang Jin Cho (02/12/17 11:33 AM IDT)
  • Kaifei Chen (02/12/17 01:42 PM IDT)
  • Alper Halbutogullari (02/12/17 06:54 PM IDT)
  • Alex Fleischer (02/12/17 09:27 PM IDT)
  • James Dow Allen (02/12/17 10:10 PM IDT)
  • Lorenz Reichel (03/12/17 10:27 AM IDT)
  • Tyler Mullen (03/12/17 10:27 AM IDT)
  • Francis Golding (03/12/17 04:48 PM IDT)
  • Vladimir M. Milovanović (03/12/17 06:19 PM IDT)
  • Dan Salajan (03/12/17 06:43 PM IDT)
  • Todd Will (03/12/17 07:41 PM IDT)
  • Lavanya Kannan (03/12/17 10:07 PM IDT)
  • Pål Hermunn Johansen (04/12/17 12:20 AM IDT)
  • Jim Clare (04/12/17 06:00 PM IDT)
  • Graham Hemsley (04/12/17 07:09 PM IDT)
  • Colas Kerkhove (04/12/17 07:29 PM IDT)
  • Justin Stanley (05/12/17 12:56 AM IDT)
  • Paul Shaw (05/12/17 02:00 AM IDT)
  • Andreas Knüpfer (05/12/17 04:28 PM IDT)
  • Florian Fischer (06/12/17 01:02 AM IDT)
  • Jesse Rearick (06/12/17 02:36 AM IDT)
  • Guillaume Escamocher (06/12/17 04:51 PM IDT)
  • Vladimir Volevich (07/12/17 10:51 AM IDT)
  • Forrest McClellan (07/12/17 09:56 PM IDT)
  • Erik Wünstel (08/12/17 06:44 PM IDT)
  • James.Gleeson (08/12/17 08:18 PM IDT)
  • Maris Van Sprang (08/12/17 09:05 PM IDT)
  • Harald Bögeholz (09/12/17 08:07 AM IDT)
  • Andreas Eisele (09/12/17 11:47 AM IDT)
  • Omer Shechter & Nir Lavee (09/12/17 06:49 PM IDT)
  • Bryce Fore (09/12/17 09:39 PM IDT)
  • Shirish Chinchalkar (10/12/17 03:05 AM IDT)
  • Joaquim Neves Carrapa (10/12/17 07:17 PM IDT)
  • Luke Pebody (11/12/17 12:34 AM IDT)
  • David Friedman (11/12/17 01:22 AM IDT)
  • Reiner Martin (11/12/17 02:02 AM IDT)
  • Andrejs Pilka (11/12/17 10:11 PM IDT)
  • Amos Guler & Gadi Yuval (12/12/17 12:09 PM IDT)
  • Olaf Krzikalla (12/12/17 04:11 PM IDT)
  • Grégory Strubi (12/12/17 05:14 PM IDT)
  • Steven Langerwerf (13/12/17 04:45 PM IDT)
  • Ritesh Ranjan (13/12/17 07:40 PM IDT)
  • Noah Lordi & Paul Lucero (14/12/17 08:22 AM IDT)
  • Yash Pote (14/12/17 12:35 PM IDT)
  • Robert Lang (14/12/17 03:13 PM IDT)
  • Nicolas Villa (15/12/17 01:32 AM IDT)
  • Rogerio Ponce da Silva (15/12/17 02:35 PM IDT)
  • Dieter Beckerle (15/12/17 04:09 PM IDT)
  • Hugo Pfoertner (15/12/17 06:42 PM IDT)
  • Celine Lee (17/12/17 05:37 PM IDT)
  • Joehyun Kim (17/12/17 10:12 PM IDT)
  • Soumitra Agarwal (18/12/17 08:04 AM IDT)
  • Liubing Yu (18/12/17 06:16 PM IDT)
  • Nyles Heise (19/12/17 08:14 AM IDT)
  • Andreas Stiller (20/12/17 01:56 PM IDT)
  • Kolya Kolombet (20/12/17 03:29 PM IDT)
  • Adam Kozdroń (21/12/17 12:27 AM IDT)
  • David Greer (21/12/17 02:48 AM IDT)
  • Ulrich Junker (21/12/17 08:05 PM IDT)
  • Sri Mallikarjun J (21/12/17 09:25 PM IDT)
  • Erik Hostens (22/12/17 05:02 PM IDT)
  • Gil Citro (23/12/17 12:31 PM IDT)
  • Erica Choi (23/12/17 04:03 PM IDT)
  • Adrienne Ko (23/12/17 06:42 PM IDT)
  • Govind A N (25/12/17 04:11 PM IDT)
  • Gida Pataki (26/12/17 03:42 PM IDT)
  • Bharat Kumar Aryasomayajula (26/12/17 05:34 PM IDT)
  • Guangzhong Sun (26/12/17 05:38 PM IDT)
  • Joonsoo Lee (26/12/17 07:20 PM IDT)
  • Ayal Zaks (27/12/17 01:11 AM IDT)
  • Jio Jeong (27/12/17 03:38 PM IDT)
  • Jang Hun Choi (27/12/17 09:42 PM IDT)
  • Vladimir Dorofeev (28/12/17 03:55 PM IDT)
  • Chris Lee (28/12/17 05:27 PM IDT)
  • JJ Rabeyrin (29/12/17 12:23 AM IDT)
  • Oscar Volpatti (30/12/17 01:53 AM IDT)
  • Motty Porat (31/12/17 12:44 AM IDT)
  • Lakshman Inkulu (01/01/18 10:34 AM IDT)
  • Radu-Alexandru Todor (01/01/18 04:53 PM IDT)

Related posts