Here is a puzzle based on a neat graph theory counting problem.
Eleven white rabbits live in eleven white houses, all in a row. One day, the rabbits get together and decide that they should spruce up their rabbit row by painting some or all of their houses. They decide that while they don't necessarily need to paint every single house, they will definitely NOT leave any two adjacent houses white. How many choices do they have for which collection of houses to paint?
Another group of eleven white rabbits also live in eleven white houses, but these are positioned in a large circle. Again, they want to repaint some or all of the houses, leaving no two adjacent houses white. How many ways can they do this?
Of course, we could also ask these questions and include paint color choices. For example, what if every house would be painted red, white or blue, but we don't want any two adjacent houses to be colored identically. How many choices do the rabbits have?
The original puzzle asks for the number of independent sets of the path graph . An independent set is a set of vertices in a graph no two of which are adjacent (connected by an edge). The first variation asks for the number of independent sets in a cycle graph. The second variation asks for the number of proper 3-colorings of such graphs.