Speed Networking
Logic; Difficulty: easy
Can everyone potentially meet everyone else?
This is yet another easy yet interesting logic puzzle that was sent to me:
9 professionals are at a networking event where 9 seats are arranged in a 3×3 grid. The set up is such that people can only converse with another person that is adjacent to them – adjacency defined as sharing an edge in the grid: anyone in a corner cell’s can only talk to their two neighbors; the person at the center can only converse with their four adjacent folks; each of the remaining four can only talk to their 3 adjacent folks. This is depicted in the picture above with allowed conversations indicated by the arrows.
The organizers want to ensure that through the course of the event, every person has the opportunity to have talked with every other person. One of the organizers proposes that they can achieve this with two reconfigurations after the first seating i.e. 3 total configurations. Another one quickly says that’s not possible. Who is right? If it is possible, what three seating configurations allow all the nine to have conversed with each other? If not, why not?
*spoiler alert* solution and answer follow below
Solution
We recognize first that for everyone to have been able to talk to every other attendee, there need to be (9X8)/2 = 36 distinct conversations. Now each configuration allows for 12 conversations. Hence to be able to have all 36 conversations in 3 rounds, there can be no duplicate conversations. i.e. each person will have to have exactly 8 unique conversations in 3 rounds.
Now depending on the location, a person can have 4,3 or 2 conversations in one round. To have exactly 8 unique conversations in 3 rounds, the center will necessarily have to be taken up by 3 different individuals. Furthermore, these 3 people will have to occupy the corners in the two rounds they are not the center in, since that is the only way to ensure exactly 8 conversations. But this necessarily implies, these three folks will never have a chance to connect with each other!
Hence it is impossible to have all 9 participants connect with each other in just 3 rounds in this set up.