Ponder This

March 2010

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]