Talk:Towers of Hanoi

From Math Images
Jump to: navigation, search

Checklist for writing page

Completed by --Xtian1 11:03, 25 July 2013 (EDT)

Messages to the Future

  • Someone who knows graph theory: Show how this game and graph theory can be connected.

References and footnotes

  • All images and information are cited.

Good writing


  • The "Why It's Interesting" section covers why the game is interesting to study. The origin story of the game is also interesting.

Quality of prose and page structuring

  • Beginning page states our topic: Towers of Hanoi
  • Every section is relevant.
  • Purpose of section is stated either in the beginning of each section or as the section title.
  • Helper pages are linked.
  • No heavy math in this page.

Integration of Images of Text

  • Every image is referred to in the text if applicable.

Connections to Other Mathematical Topics

  • The "Why It's Interesting" section has the relationships to other areas of math and computer science.
  • Links to other Math Images pages are included.

Examples, Calculations, Applications, Proofs

  • Numerical example is provided.
  • Proofs are included.

Mathematical Accuracy and Precision of Language

  • All the math is free of error (to my knowledge anyway).
  • Statements have rigor but are not confusing to read.
  • Defined terms both in text and in mouse-over bubbles.


  • Short paragraphs of text with images.
  • Page is short, so hiding isn't as needed. Mouse-over bubbles are used.
  • No large chunks of white space.
  • Text wrapping is not a problem.
  • Images are in the right place.
  • No weird computer code.
  • Page is viewed in different window sizes and nothing weird happened.

Older Comments

Overall Comments

I made some minor edits directly on the page; you can check them in your history.

-Diana 09:48, 15 July 2013 (EDT)

Add citations for your claims about the history of the game, the lifespan of the sun, and the game's uses in comp sci instruction and psychological testing.

- Diana 12:50, 6 June 2013 (EDT)

Basic Description

Three minor changes for this section:

  • Paragraph 1: "increasing size from top to bottom" would make more sense in the context of game play as "decreasing size from bottom to top."
  • Paragraph 3: A lot of readers won't know the term "minimal algorithm." Something like "quickest solution" would be better for the basic description.
  • Paragraph 3: At "if the priests move..." start a new paragraph and remind the reader what you're talking about. So it might look like:
...the relationship is exponential (see A More Mathematical Section for details)
¶ We can see the effects of this exponential relationship in the legend about the priests, who had to move 64 disks from one pole to the other. If they move one disk per second, then...

- Diana 12:50, 6 June 2013 (EDT)

Play the Game

Example of Solving the Game

A More Mathematical Explanation

The Recursive Solution

  • Add labels for poles A, B, and C in Image 1.
    • This is one of my comments, too; add the labels for Image 1 and Image 2. -Diana 09:48, 15 July 2013 (EDT)
  • When I google the term "minimal algorithm", nothing comes up without a word in between, like "Minimal MapReduce Algorithm." You are interested in the algorithm that produces the fewest number of moves—I think you should either rephrase it or at least define it.
  • In the paragraph that begins "To solve the game with k disks", change the paragraph break to "Note that there are..." and remove paragraph break two sentences later.
  • The paragraph beginning "If we wish to move the kth disk directly to Pole C" is unnecessarily long. You have already shown that moving it to Pole B is much longer than needed. You can probably condense this into one sentence.

- Chris 4:45, 26 June 2013 (EDT)

The paragraph beginning, "If we wish to move the kth disk onto Pole B..." is confusing; you just said pole C is the correct choice, and it’s not clear until two sentences after this that you’re not contradicting that. Moreover, you need to make it clear why you’ve included this algorithm, given that it’s not the optimal one. There are infinite non-optimal algorithms, and you only talk about this one. Say why you chose it, and say where you’re going with it (that you’re setting up a comparison between two algorithms) before launching into describing it.

-Diana 09:48, 15 July 2013 (EDT)

Mostly minor points in this section, too:

  • Paragraph 1: For clarity, add: "...the number of moves our algorithm needs to solve the game for k disks...."
  • Last Paragraph: Break this up into paragraphs based on its steps:
    • "...So Tk-1 is minimized. To solve the game ..."
    • "...disks onto Pole B. After the k -1 disks are placed..."
    • " best one step. Finally, the game will be solved..."
    • "...steps to do so. Thus the minimum number..."
  • Last Paragraph: I mentioned this in our meeting: Refer explicitly to your images to illustrate the concepts you use. (Add “Image 1” and “Image 2” to the captions to make this easier.)
  • Last Paragraph: Change: "...our algorithm needs the the least uses minimal moves...."
  • Last Paragraph: Change: "...this takes at best least one step...."

- Diana 12:50, 6 June 2013 (EDT)

Diana 13:17, 31 May 2013 (EDT)

Hi Xintong,

Some general points on the more mathematical section:

  • Make sure to italicize all your variable names when you type them in-line.
  • Consider using in-line math more often to keep the formatting cleaner; that is, "This takes Tk-1 steps" rather than "This takes T_{k-1} steps."
  • Watch out for unnecessary usage of the word "that." Phrases such as, "We know that Tk≥Sk" can simply be, "We know Tk≥Sk."

Also, re-reading your recursive proof more closely, I have some specific ideas for how you can streamline the second half to make it clearer and less of a repeat of the first half. Here are some changes I recommend:

1. At some point in the game, the top k-1 disks must be on Pole B in order for the kth disk to move onto Pole C. Since we know that S_{k-1} is the least number of moves to move k-1 disks onto a different pole, we can assume this step takes a minimum of S_{k-1} moves.
2. Once the top k-1 disks are on Pole B, we need at least one step to move the kth disk from Pole A to Pole C.
3. After the kth disk is on Pole C, we must move the remaining k-1 disks from Pole B to Pole C. Again, this step takes a minimum of S_{k-1} moves.
Thus we know that:
T_k\geq S_k=S_{k-1}+1+S_{k-1}=2S_{k-1}+1
Since T_k and S_k have the same recursive formula AND the same base case, we know that T_k=S_k. Hence, Tk is the quickest solution for k disks.

The Explicit Formula

  • In the third step of the inductive proof, consider putting 2 to the first power next to 2^k-1 to help the reader know to add the exponents to get 2^k.

- Chris 4:45, 26 June 2013 (EDT)

Four changes for clarity:

  • Line 1: Add: "...the explicit formula for the number of steps in this minimal algorithm is..."
  • Line 2: Use regular text for “for some positive integer.” If you think it looks weird as regular text next to the math text, you could also put “for some positive integer k” in regular text on a new line.
  • Line 6: Break this up into four lines, with each of your algebraic steps on a separate line.
  • Line 7: Change: "Thus we have shown the explicit formula holds for any Towers of Hanoi game with k disks minimal algorithm for any Towers of Hanoi game with k disks has Tk = 2k – 1 steps."

- Diana 12:50, 6 June 2013 (EDT)

Back to the Legend

The final equation here is still quite long; I suggest either

T_{64}\text{s}\cdot \left(\frac{1\text{m}}{60\text{s}}\right)\left(\frac{1\text{h}}{60\text{m}}\right)\left(\frac{1\text{d}}{24\text{h}}\right)\left(\frac{1\text{y}}{365.25\text{d}}\right)\approx584.54\text{ billion years}


18,446,744,073,709,551,615\text{s}\cdot \left(\frac{1\text{m}}{60\text{s}}\right)\left(\frac{1\text{h}}{60\text{m}}\right)\left(\frac{1\text{d}}{24\text{h}}\right)\left(\frac{1\text{y}}{365.25\text{d}}\right)

\approx584.54\text{ billion years}

-Diana 11:41, 15 July 2013 (EDT)

Remind the reader what you're talking about: "...we can verify the numbers listed in the Basic Description time we said was needed to complete the game in the legend in the basic description. A Towers of Hanoi game..."

- Diana 12:50, 6 June 2013 (EDT)

Why It's Interesting

  • The mathematical nature of the game teaches recursion.
    • I think this is fine; it's clear from the previous sentence that you're talking about recursion in the sense of recursive programs. -Diana 09:48, 15 July 2013 (EDT)
  • What is "basic graphics processing"? Explain that this is from a computer programming perspective.
  • Provide greater clarity about the concept of "exponential time."

- Chris 4:45, 26 June 2013 (EDT)

I mentioned this in our meeting: Do something with "recursive nature of the game teaches recursion" to make it less tautological.

I also made some tense and spacing corrections to this section; you can see them in your page history.

- Diana 12:50, 6 June 2013 (EDT)