Quiz #3

Question 1:

You have a collection of different tiles with which to pave a path. You have 5 different colors of tiles: red, yellow, green, blue, and black. The red and yellow tiles are each 1x1, and the green, blue, and black tiles are each 1x2.

Let $a_n$ denote the number of ways to tile a path of dimensions $1\times n$. Find a recurrence relation for $a_n$.

Question 2:

In a group of 7 people, is it possible for everyone to be friends with exactly 3 other people?

(Hint: This is a graph theory question.)