Tanner Helton

I have always loved math and would love to chat about it.

Here are three classic mathematical problems I enjoy:

Tower of Hanoi

The recursive solution can be expressed mathematically as:

\[ T(n) = \begin{cases} 1 & \text{if } n = 1 \\ 2T(n-1) + 1 & \text{if } n > 1 \end{cases} \]

Which simplifies to: \[ T(n) = 2^n - 1 \]

Josephus Problem

For n people numbered from 1 to n and counting out every k-th person:

\[ J(n,k) = \begin{cases} 1 & \text{if } n = 1 \\ ((J(n-1,k) + k-1) \bmod n) + 1 & \text{if } n > 1 \end{cases} \]

For the special case where k = 2, there's a beautiful binary solution:

\[ J(n,2) = 2L + 1 \]

where L is the number left after writing n in binary and removing the leftmost 1.

Nim Game

A classic impartial combinatorial game involves n piles of objects (e.g., stones), with the i-th pile having \( x_i \) stones. On a player's turn, they may remove any positive number of stones from exactly one pile. The goal is typically to be the player who makes the last move.

The fundamental solution to Nim is expressed through the bitwise xor (also called the "Nim-sum") of the pile sizes:

\[ x_1 \oplus x_2 \oplus \cdots \oplus x_n \]

where \(\oplus\) denotes the bitwise xor operation. A position is a losing position if and only if this Nim-sum is zero. Otherwise, it's a winning position, meaning there is a winning move for the current player.