Skip to content
Get started

Tower of Hanoi, adjacent moves only

MediumBrainteasers5 min

Three pegs stand in a row: left, middle and right. Three disks of different sizes sit on the left peg, largest at the bottom. You move one disk at a time and may never place a larger disk on a smaller one. The twist: a disk may only move to an adjacent peg (left↔middle or middle↔right - never directly between left and right). What is the minimum number of moves to transfer all three disks to the right peg?

Show hints (2)+
  1. The largest disk can't jump from left to right - it must stop on the middle peg, and each of its moves needs every smaller disk parked on the other end.
  2. This gives an=3an−1+2a_n = 3a_{n-1} + 2 with a0=0a_0 = 0, so an=3n−1a_n = 3^n - 1.

Answer

Reveal answer →

26

Create a free account to see the full worked solution and track your progress.

Interview format: Trading Aptitude Tests, Betting Game Rounds

Related questions