Close
today i learned (til)

Cracking the Code: The Towers of Hanoi

December 1, 2023

Now that we have developed a fundamental understanding of how different counting systems, especially binary, work, we can begin to understand the optimal solution to the Towers of Hanoi.

One by One 

Because binary digits are restricted to just one of two values, counting in binary has a particularly interesting rhythm. Understanding this rhythm is crucial in solving the Towers of Hanoi problem. This online binary counter is particularly useful in visualizing this rhythm. Beginning from zero, continue to count up, adding one with each step. Keep track of the index of the value that switches to a 1 at each step:

0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, …

Solution to the Towers of Hanoi

Interestingly enough, the most optimal solution to the Towers of Hanoi comes from following this rhythm exactly. To tie the two together, first assign numeric indices to the disks: 0 is the smallest, 1 the next smallest, and so on. Then, simply follow the pattern, at each step moving the disk whose index matches the next number in the sequence.

For example, consider the 3 disk problem:

  • 0: move disk 0 to the right peg
  • 1: move disk 1 to the middle peg
  • 0: move disk 0 to the middle peg
  • 2: move disk 2 to the right peg
  • 0: move disk 0 to the left peg
  • 1: move disk 1 to the right peg
  • 0: move disk 0 to the right peg

And then we are done! There are some beautiful symmetries to this pattern. Also interesting is the fact that, for a setup with n disks, the optimal solution requires exactly 2^n – 1 moves.

Why Does This Work?

In so few words: recursion! Both the rhythm of binary counting and the problem of the Towers of Hanoi are self-similar problems. The idea of self-similarity ties directly into recursion: the full process, whether that’s counting up to a certain number or solving a problem with a certain number of disks, involves completing a smaller version of the process.

In the Towers of Hanoi, consider again the 3 disk problem. If we were somehow able to move the stack of the 2 smallest disks as a single unit, then the problem would reduce to three steps:

  1. Move the 2-disk unit off of the third disk
  2. Move the third desk to the right peg
  3. More the 2-disk unit onto the third disk

So, through a recursive approach, the problem becomes much simpler to solve.

In the process of binary counting, return to the counter visualizer. Count up to the number 7 (111 in binary). Notice that we count up to the number 3 (11 in binary), roll over to 4 (100 in binary), and then count up three more to get to 7 (111). This exactly mirrors the recursive pattern in the Towers of Hanoi!

Conclusion

Oftentimes in mathematics, and in problem solving in general, finding an inventive way to connect and reduce one problem to another can make understanding optimal solutions much easier. The Towers of Hanoi, though it may appear as a confusing game at first, cleanly works in parallel to just counting up by one in binary. 

References

  1. https://www.khanacademy.org/computing/computer-science/algorithms/towers-of-hanoi/a/towers-of-hanoi
  2. https://www.mathsisfun.com/games/towerofhanoi.html
  3. https://www.youtube.com/watch?v=2SUvWfNJSsM
0Likes
About Author

You May Also Like

Funny Bone, today i learned (til)
Carcinization: Evolution’s Favorite Shape is Crab
today i learned (til)
The Brachistochrone and Snell’s Law: A Surprising Connection
today i learned (til)
Are Sunscreen products reliable?
today i learned (til)
Your Water Was Poisoned – The Dupont Chemical Scandal

Your journey starts here! Let’s talk!

ThemeRex © 2026. All rights reserved.
  Timothy Durham was convicted of rape when a test showed his DNA genotype matched the DNA recovered from the crime scene. Eye witnesses testified that Durham was in a different state at the time of the incident, but he wasn’t exonerated from his 3000 year sentence until follow up DNA analysis showed that the preliminary forensic analysis used in the trial was misinterpreted (Thomas et al.). DNA testing serves an invaluable part in our criminal justice system, but it comes with complications and bias that can lead to wrongful convictions and misinformed juries.  

Background:

Forensic genetics aims to identify the origin of a biological sample. It can be traced back to Karl Landsteiner who discovered human ABO blood groups. With blood groups, suspects could be eliminated based on their blood type. For example, if a suspect had type A blood and there was type B blood left at the scene by the perpetrator, the investigators could rule out the suspect. Unfortunately, the reverse didn’t work. If the suspect and perpetrator both had the same blood type, it can’t be concluded that the suspect was guilty. Blood identifiers evolved into 8 distinct categories which improved the ability to eliminate suspects, but could only conclude that (if the system matched) it might be the perpetrator or this person might be related to the perpetrator (Jobling and Gill). The field evolved in the 1980s with the discovery of Minisatellites, lines of repetitive DNA that don’t encode proteins. Minisatellite patterns in DNA create what we know today as the DNA fingerprint, and it has a much higher accuracy rate than previous methods (Augustyn et al.). Around the same time, a breakthrough for victims of sexual assault was discovered. In the case of assault, bodily fluids of both the victim and the assaulter can get mixed. A process called differential lysis was created which could selectively increase the concentration of sperm in a fluid sample thereby allowing for accurate DNA testing (Jobling and Gill). Forensics evolved to use single-locus probe testing after several years because of its ease of interpretation. It looked at specific minisatellites that had high variability between subjects. This was the first DNA-based method to be used in a criminal investigation. Two murder homicides from several years apart were connected using DNA evidence. The evidence was then used to exonerate an innocent man, and the guilty party was found when he tried to evade mandatory DNA testing for all men in the small town. His guilt was then reinforced when the DNA profiles matched, and he gave a confession (Jobling and Gill). Finding DNA at a crime scene doesn’t guarantee that you’ll find a murderer. There are issues with non-pure samples and limited samples that make DNA work difficult, and accreditation of facilities and new techniques and take time (Jobling and Gill).  

Subjectivity of DNA Interpretation:

In a 2009 publication, the National Academy of Science discusses the possibility for subjective influence in lab based forensics. The interpretation bias happens in complex cases where, for example, there could be a mixture of DNA. A study published in 2011 looked specifically at this issue. A gang rape happened in Georgia, and the mixture in DNA from the case was used to prosecute one suspect after another suspect took a plea bargain to testify against him. With DNA mixtures, there are three possible conclusions: suspect excluded, suspect cannot be excluded, and inconclusive. If the suspect is excluded, it means that there’s little to no possibility that his DNA is part of the sample. If the suspect cannot be excluded, it means that there’s a possibility that his DNA is part of the sample. In the trial, the DNA examiners who knew the context of the case concluded that the suspect being prosecuted could not be excluded. The 2011 study gave the DNA evidence from this case and the DNA profiles of the suspects to 17 forensic examiners. These examiners had no context of the case, and they all worked independently. Of the 17, only 1 came to the same conclusion (suspect cannot be excluded) as the examiners who knew the context of the case. Twelve of the 17 concluded that the suspect who was prosecuted and convicted had no relation to the DNA found in the sample. Not only does this show that subjectivity occurs due to the context of the case, but the 17 examiners came up with different findings based on their past experiences meaning that not all DNA analysis is objective. Some organizations like the Scientific Working Group on DNA Analysis Methods say that quantitative statistical evidence should be presented with every categorical conclusion, but the US doesn’t require this (Dror and Hampikian).

False Positives:

There are two categories that cause wrongful identification in a DNA report: coincidental matches and false positives. Coincidental matches are DNA matches between two unrelated people. The probability of these matches is about 1 to 500,000 for white individuals and about 1 to 350,000 for black individuals. This small probability of coincidental matches makes people feel confident in DNA evidence. False positives, on the other hand, are matches between DNA and test DNA that result from issues in the forensics lab. There have been multiple cases of forensics labs accidentally switching victim and suspected rapist DNA which lead to convictions that were later overturned when the lab realized the error. There are also cases of misreading or misunderstanding a sample. In a case from 1993, a man was convicted of rape because someone interpreted a mixed sample of victim and perpetrator DNA as an individual sample. The conviction was again overturned. To prevent false convictions, retesting DNA is allowed, but it’s not an efficient solution. Many people are pushing for statistical information on the probability of false positives, so that the jurors can make accurate judgements based on DNA evidence (Thomas et al.).  

Conclusion:

DNA analysis is a useful tool for the criminal justice system, but subjectivity can be an issue in forensic testing. To combat wrongful convictions, there are organizations like The Innocence Project who use DNA testing to free the innocent, but reformed forensic testing standards should be put in place to prevent subjectivity and to ensure juries are correctly informed during trials. https://www.innocenceproject.org/    

Citation:

Augustyn , Adam, et al. “DNA Finerprinting.” Encyclopedia Britannica , 26 Apr. 2018, www.britannica.com/science/DNA-fingerprinting#ref153186. Dror, Itiel E., and Greg Hampikian. “Subjectivity and Bias in Forensic DNA Mixture Interpretation.” Science & Justice, vol. 51, no. 4, 2011, pp. 204–208., doi:10.1016/j.scijus.2011.08.004. Jobling, Mark A., and Peter Gill. “Encoded Evidence: DNA in Forensic Analysis.” Nature Reviews: Genetics, vol. 5, no. 10, Oct. 2004, pp. 739–751., doi:10.1038/nrg1455. Thompson, William C, et al. “How the Probability of a False Positive Affects the Value of DNA Evidence.” Journal of Forensic Sciences, vol. 48, no. 1, Jan. 2003, pp. 1–8., doi:10.1520/jfs2001171.