### Problem A tower of 8 disks, stacked with the largest on the bottom and decreasing in size, is situated on one of 3 pegs. A "move" is defined as taking the top disk on any peg and moving it to a tower topped with a larger disk, or an empty peg. How many moves are required to complete the objective of relocating the tower (like in its initial state) to another peg? #### Solution Generalize the problem to $n$ disks (but still keeping 3 pegs), and let $T_n$ be the number of moves to needed complete the objective To make notation easier, number the disks $1$ through $n$, where $n$ is the smallest and $1$ is the largest. The number $0$ represents a peg with no disk. Let the ordered set $(n,0,0)$ represent the initial state of the pegs by showing the number of the disk on top. The objective is to achieve the state $(0,0,n)$. Each move will be separated by $\textbf{ ; }$ 0. If $n=0$ then the concept of a 0 disk tower already exists on any peg without any moves. so $T_0=0$ - $\overset{0 \text{ moves }}{\overbrace{(0,0,0)}}$ 1. If $n=1$ then the process is almost as easy. Just move the disk. $T_1=1$ - $(1,\overset{1 \text{ move }}{\overbrace{0,0)\textbf{ ; }(0,0}},1)$. 2. If $n=2$, things get interesting. We do not want to move disk 2 to peg 3 immediately, because disk 1 cannot go on top. We need to move all (one) of the disks that start on top of disk 1 to peg 2 before we can place disk 1 on peg 3. The disk that was placed on peg 2, can be moved to disk 3 in $T_1$ moves - $(2,\underset{T_1 \text{ moves}}{\underbrace{0,0) \textbf{ ; } (1,2}}\overset{1 \text{ move}}{\overbrace{,0) \textbf{ ; } (0,}}\underset{T_1 \text{ moves}}{\underbrace{2,1) \textbf{ ; } (0,0}},2)$ 3. If $n=3$, the way $n=2$ was explained makes a lot more sense - $(3,\underset{T_2 \text{ moves}}{\underbrace{0,0)\textbf{ ; }(2,0,3)\textbf{ ; }(1,2,3)\textbf{ ; }(1,3}}\overset{1 \text{ move }}{\overbrace{,0)\textbf{ ; }(0,}}\underset{T_2 \text{ moves}}{\underbrace{3,1)\textbf{ ; }(3,2,1)\textbf{ ; }(3,0,2)\textbf{ ; }(0,0}},3)$ After this many cases, we can see a pattern for $T_n$. Defined recursively $T_n = 2\cdot T_{n-1}+1$ Using this to get a few more $T_n$ values: |n|T_n| |-|---| |0|0| |1|1| |2|3| |3|7| |4|15| |5|31| It becomes more obvious that an explicit form exists $T_n = 2^n-1$ To prove this, use [[Proof by Induction]] Base case: $T_0=2^0-1=0$ $T_{n+1}=2^{n+1}-1=2\cdot2^n-2+1=2(2^n-1)+1=2 T_n+1$ This satisfies the recursive form, so it is a valid explicit form. The problem as mentioned was for $n=8$ so $T_8=2^8-1=\boxed{255}$