(The Towers of Hanoi) In the temple of Benares, three diamond needles are erected. On the left needle are threaded 64 discs of pure gold, the largest at the base and the others, increasingly smaller, stacked to the top. Day and night, the monks move the discs from one needle to another, following two rules: they can only move one disc at a time, and they cannot place a disc on a smaller one. It is said that when the 64 discs are on the right needle, the temple will collapse and it will be the end of the world. How much time do we have left
Let $u_{n}$ be the minimum number of moves required to transfer a column of size $n$ from one peg to another. To transfer a column of size $n+1$ from the right peg to the left peg, it is necessary to move the top $n$ disks to the middle peg, then move the largest disk to the right peg, and finally move the $n$ other disks on top of it. This allows us to find the following recurrence relation: $u_{n+1}=2 u_{n}+1$. We initialize with $\mathfrak{u}_{1}=1$, and I leave it to the reader to prove by induction that $u_{n}=2^{n}-1$. If we consider that it takes the monks at least one second to make a move, the end of the world will not come before $2^{6} 4-1 \mathrm{~s} \approx 600$ billion years (we are being generous).