The Tower of Hanoi:
The French mathematician Edouard Lucas (1842-1891) constructed a puzzle with three pegs and seven rings of different sizes that could slide onto the pegs.
Legend has it that an order of monks had a similar puzzle with 64 large golden disks. Starting with all the rings on one peg in order by size, the problem is to transfer the pile to another peg subject to two conditions: rings are moved one by one, and no ring is ever placed on top of a smaller ring. The monks supposedly believed that the world would end when the job was finished. How many moves are required?
There are multiple applets on the web where you can experiment with the Towers of Hanoi problem.
Regions in a plane:
By a configuration of lines, we mean a finite collection of lines in the plane such that each pair of lines has one point in common and no three lines have a common point. Find the number of regions a configuration of n lines creates.
Rabbits and Cadillacs:
Suppose n spaces are available for parking along a curb. We can fill the spaces using Rabbits, which take one space, and/or Cadillacs, which take two spaces. In how many ways can we fill the spaces? (The analysis of this problem leads to Fibonacci numbers.)