# Can You Find a Tower of Hanoi Word?

Consider a simple Tower of Hanoi set consisting of three rods and three disks. This tower has an optimal solution of seven moves; these seven moves are the only ones allowed in what follows.

For the purposes of this puzzle, you are allowed to letter this set, which means engraving a letter on each disk and at the base of each rod. Any such assignment is a called a lettering.

But not all letterings are permissible. Whenever a disk is moved, let's say it clashes with its new spot (either an empty rod or another disk).

The only letterings that are permissible are those for which every clash in the optimal solution is one between letters that are a single letter distance apart in the alphabet. For example, a clash between a 'p' disk and an 'r' disk is acceptable because 'p' and 'r' are separated by a single letter, 'q'.

Every time a disk clashes with a spot, they interact, yielding the letter that's between them. For example, if a 'p' disk lands at an 'r' spot, a 'q' is generated.

Given that the optimal solution we are considering has seven moves, the resultant string of this solution is seven characters long.

Let's assume, for the sake of illustration, a lettering in which the disks are lettered 'g', 'e', and 'g', and the rods are lettered 'e', 'c', and 'i'. All the clashes in the optimal solution are legal under this lettering and the resultant string is "HDFHFFF". Here's an illustration: Question:

Can you find a lettering where the resultant string is a word of English?

If so, you'll be one of the first people to discover a Tower of Hanoi Word!

(I myself am not sure if they exist.)

Here's a hint to get you started:

Letting x, y, and z, be variables standing for the alphabetic positions of the letters assigned to the small, medium, and large disks respectively, and letting a, b, and c be variables standing for the alphabetic positions of the letters assigned to the first, second, and third rods respectively, given the optimal solution, the following equations must all be satisfied by the lettering:
|x-c|=2, |y-b|=2, |x-y|=2, |z-c|=2, |x-a|=2, |y-z|=2.

P.S. If anyone has any tag recommendations for this, let me know.

• Are you allowed to have a non-clash (e.g. G and G)? Nov 4, 2016 at 5:55
• Also, do A and Y make Z, and do B and Z make A? Nov 4, 2016 at 5:59
• @boboquack, every move must involve a clash, which means non-clashes are not allowed. I consider G to G a non-clash rather than a trivial one. Yes, I intended that A and Y yield Z and B and Z yield A. I will edit this fact into the question later. I was also thinking about broadening the puzzle so that legal clashes can involve letters that are any odd-number letter distance apart rather than a single letter distance. Such clashes would yield the letter directly between them (e.g., A and G would yield D). Nov 4, 2016 at 12:20
• I propose to ask a separate, more general question where hopefully some kind of solution exist. Nov 4, 2016 at 13:49

Let's call the letters on the disks $d_i$ and the letters on the pegs $p_i$. Then the seven "clashes" are:

$$(d_1, p_3), (d_2, p_2), (d_1, p_2), (d_3, p_3), (d_1, p_1), (d_2, p_3), (d_1, p_3)$$

The two letters in each pair must differ by $\pm 2$. We'll call the seven signs $s_i$. Then we have:

$$d_1 - p_3 = 2s_1 \\ d_2 - p_2 = 2s_2 \\ d_1 - p_2 = 2s_3 \\ d_3 - p_3 = 2s_4 \\ d_1 - p_1 = 2s_5 \\ d_2 - p_3 = 2s_6 \\ d_1 - p_3 = 2s_7$$

Solving these seven equations yields:

\begin{align} d_2 &= d_1 + 2 s_2 - 2 s_3 \\ d_3 &= d_1 - 2 s_1 + 2 s_4 \\ p_1 &= d_1 - 2 s_5 \\ p_2 &= d_1 - 2 s_3 \\ p_3 &= d_1 - 2 s_1 \\ s_6 &= s_1 + s_2 - s_3 \\ s_7 &= s_1 \end{align}

The resulting letters are the means of the seven pairs. Taking those means and substituting values from the above equations yields:

\begin{align} d_1 &- s_1 \\ d_1 &+ s_2 - 2 s_3 \\ d_1 &- s_3 \\ d_1 &- 2 s_1 + s_4 \\ d_1 &- s_5 \\ d_1 &- s_1 + s_2 - s_3 \\ d_1 &- s_1 \end{align}

Thus a solution can be identified by

an offset and five of the signs.

This gives us at most

$26\times 2^5=832$ solutions to check (assuming modular arithmetic, i.e. that $\mathrm{Z}+1=\mathrm{A}$).

Here are all the possible solutions, of which

none

are words.

• It would probably have been easier to use graph theory to sort out the signs bit. Nov 4, 2016 at 6:54
• @bobo What were you thinking of? I can see how to represent the problem as a graph, but not how to solve it without transforming back to a linear system. Nov 4, 2016 at 7:46
• @2012rcampion, nice work! I was afraid there wouldn't be any. I was also thinking about broadening the puzzle so that legal clashes can involve letters that are any odd-number letter distance apart rather than a single letter distance. Such clashes would yield the letter directly between them (e.g., A and G would yield D). In any event, good job! Nov 4, 2016 at 12:21
• @Silenus Don't you mean even distances? (e.g. A to G is 6...) Nov 5, 2016 at 14:27
• By odd, I meant the number of letters between them. My bad. Good point. Nov 5, 2016 at 17:05