Ponder This Challenge - March 2010 - Spell names by passing phones

Ponder This Challenge:

Three people named Erne, Neer, and Rene are standing in a circle. Two of them hold a phone and talk to one another -- Neer is holding the first phone and Erne is holding the second phone. After they talk, Erne passes his phone to Rene and now Neer talks to Rene. After that, Neer passes his phone to Erne and the last pair, Rene and Erne, speak to one another. At this point, all three pairs have talked, each one exactly once. If we write the initial letter of the people who talked in order by phone, it looks like this:

1. The initial holder of the first phone (Neer) = N
2. The initial holder of the second phone (Erne) = E
3. The final holder of the first phone (Erne) = E
4. The final holder of the second phone (Rene) = R

We get NEER, one of the names in the list. It's easy to verify that Rene can not be a solution while Erne can be; and there is only one possible scenario of phone-passing for each of the two names.

Now consider the list of 21 people below, who are all standing in a circle, when moving clockwise their names are sorted in alphabetical order. Our riddle this month is to find out how many possible scenarios of 209 phone passes exist that spell out each name in that list, based on the initial letter of the names of the four people who speak -- the initial holders of the first and second phone, and the final holders of the first and second phone, in that order. On each phone pass, one phone is passed to one of a person's two neighbors in the alphabetically ordered cycle. In each scenario of 209 passes, every pair of people talks exactly once.

The 21 names are Adam, Boga, Dave, Eric, Fred, Gale, Ioan, John, Karl, Luke, Mark, Nick, Oded, Phil, Rani, Siva, Tony, Udit, Wolf, Yury, and Zhou.

Bonus question - what is common to all these names?

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

Solution

• Click here to view the solution

  The question was to find a Hamiltonian path in the graph whose vertices are the 210 pairs and edges determined by the possible moves of the phones. The degree of the vertices for the adjacent pairs is two and combining these pairs of edges yields a circle (AB-AD-BD-BE-DE-...-YZ-YA-ZA-ZB-AB). Thus we must start (or end) the path with an adjacent pair. This rules out all the names but two (Fred and Oded).

  All the other vertices in the graph have degree four. But after taking out the almost-circle mentioned above, we get more vertices with effective degree two. Consequently, the solution fuses 10 circles. There are degrees of freedom in where to cut and paste these circles, but there is only one way to get from "OD" to "ED" and no way to get from "FR" to "ED".

  And the answer to the bonus question: All are first names of ponder-this solvers.

  Some of our solvers sent us beautiful solution. Thanks to Adam Daire for the following elaborate solution:

  Start by picturing the entire number of possible conversations in a grid format, rather than a circle.

  Click here to see the graphic for this step

  Note that the diagonal, which would be conversations between someone and him/herself is not allowed. You can see that when either phone is handed off, it must move to an adjacent person, so the next conversation must be one of the four adjacent squares. Also observe that when a conversation AB has occurred, the conversation BA will not be allowed in the future. Lastly, when a handoff takes a path out of any of the edges of the box, it reenters on the opposite side (since the person to the left of A is Z)

  Now think about the conversations that are up against the diagonal, which must occur at some point during the string of 210 conversations. If this is one of the many conversations that is neither at the beginning nor an end of the chain, the path must enter the box from one of the two adjacent squares, and leave via the other (which I’ve decided arbitrarily).

  Click here to see the graphic for this step

  You can see that the box directly below the out-path box will be isolated and never visited if not on the next handoff, making it the only allowable next move, from which there is also only one out-path. You continue to follow this forced path until you run into the path you started from.

  Click here to see the graphic for this step

  Now you can see that the completely isolated square must be either the beginning or the end of the path, and thus, there are only 42 spots along either side of the diagonal from which the path must have originated (or if you follow the same path in the reverse order, the path ends on one of these) there are only two names in the list whose first or last pair of letters are adjacent, FRED and ODED, so the path ends on the diagonal, at ED. The permutations of paths that end there are easier for me to think about if we follow them backwards, so let’s just say we’re trying to start at ED and go to OD or FR

  As we complete a “loop”, forced along the diagonal from our starting point, we will end up constructing a new diagonal “keep-out” zone, and finish in one of the two boxes adjacent to our starting point, depending on which way (up and left or down and right) we opted to leave the ED box.

  Click here to see the graphic for this step

  From either of these two 1st-loop finish points, we can go up or right, and from each of those, can choose to complete our second loop, finishing either up or right from that loop-start. The number of ways to reach each of these loop-finishes follows a binomial distribution.

  Click here to see the graphic for this step

  If we continue looping until the entire conversation space has been covered, we see that there are only 10 final locations. FR is not among them and there is only one path to get to OD.

  Click here to see the graphic for this step

  Close [x]

  Close [x]

  Close [x]

  Close [x]

  Close [x]

  Close [x]

Solvers

• David Friedman (03/02/2010 03:08 PM EDT)
• Liubing Yu (03/04/2010 08:42 AM EDT)
• T (03/05/2010 02:30 PM EDT)
• om Sirgedas (03/05/2010 02:30 PM EDT)
• (03/05/2010 02:30 PM EDT)
• B (03/06/2010 12:19 AM EDT)
• rian Chen (03/06/2010 12:19 AM EDT)
• (03/06/2010 12:19 AM EDT)
• Chuck Carroll (03/06/2010 12:37 AM EDT)
• (03/06/2010 12:37 AM EDT)
• Dan Dima (03/07/2010 08:21 AM EDT)
• (03/07/2010 08:21 AM EDT)
• Alex Shnaidman (03/07/2010 12:06 PM EDT)
• (03/07/2010 12:06 PM EDT)
• Lachezar Hristov (03/08/2010 07:21 AM EDT)
• (03/08/2010 07:21 AM EDT)
• Alexander Ivrii / Sergey Novikov (03/08/2010 09:46 AM EDT)
• (03/08/2010 09:46 AM EDT)
• Ben Tarlow (03/08/2010 02:14 PM EDT)
• (03/08/2010 02:14 PM EDT)
• Phil Muhm (03/09/2010 01:02 PM EDT)
• (03/09/2010 01:02 PM EDT)
• Adam Daire (03/09/2010 05:49 PM EDT)
• (03/09/2010 05:49 PM EDT)
• Nagy Zoltan (03/11/2010 11:09 AM EDT)
• (03/11/2010 11:09 AM EDT)
• Jeff Steele (03/12/2010 01:24 AM EDT)
• (03/12/2010 01:24 AM EDT)
• John T. Robinson (03/12/2010 11:34 PM EDT)
• (03/12/2010 11:34 PM EDT)
• Daniel Bitin (03/16/2010 01:36 PM EDT)
• (03/16/2010 01:36 PM EDT)
• Clive Tong (03/17/2010 06:15 PM EDT)
• (03/17/2010 06:15 PM EDT)
• Mark Mixer (03/17/2010 11:47 PM EDT)
• (03/17/2010 11:47 PM EDT)
• Anurag Anshu (03/19/2010 01:39 PM EDT)
• (03/19/2010 01:39 PM EDT)
• Alan Murray (03/21/2010 07:00 PM EDT)
• (03/21/2010 07:00 PM EDT)
• Aliaksei Sanko (03/23/2010 02:36 PM EDT)
• (03/23/2010 02:36 PM EDT)
• Dan Ignatoff (03/24/2010 05:07 AM EDT)
• (03/24/2010 05:07 AM EDT)
• (03/27/2010 12:03 AM EDT)
• Hongcheng Zhu (03/27/2010 12:03 AM EDT)
• (03/27/2010 12:03 AM EDT)
• John G Fletcher (03/30/2010 09:09 PM EDT)
• (03/31/2010 09:36 AM EDT)
• Nyles Heise (03/31/2010 09:36 AM EDT)