Problem 3 Recursion

Problem 3: Recursion

UIUC Comprehensive Exam 2005

Problem: Santa has fifteen presents to place in a circle under a Christmas tree (starting with one directly north). He has four kinds of wrapping paper, and packages wrapped in the same paper look identical. He insists that he not place two packages with the same wrapping paper next to each other, but is worried that he will not be able to make the base of every tree look different (when looking directly north). How many ways are there to wrap and place the packages? Solution: For a generic case of n presents, we will generate each arrangement using previous arrangements. Looking at each arrangement of n−1, we can see that to create an arrangement for n presents, we simply insert a present in between two presents. There will be two choices for this present’s wrapping paper because the ones on either side will have different colored paper, leaving two choices. However, this only counts the arrangements where the present is added between two different presents, excluding ones where the present is added between two of the same presents. To account for this, look at each arrangement of n − 2 presents. Two presents will be added, one will match, leaving the other with 3 arrangements. Thus, the recursion is Sn = 2Sn−1 + 3Sn−2 , which can also be written as f (n + 2) = 2f (n + 1) + 3f (n) To solve a recurrence, turn f (n + 0) into n0 , f (n + 1) into n1 , f (n + 2) into n2 , etc. and solve for n: n2 = 2n + 3 n = −1 or 3 Then f (n) = a ∗ (−1)n + b ∗ 3n for constants a and b. Then f (1) = 3b − a = 0 and f (2) = 9b + a = 12. Solving, b = 1 and a = 3, so f (n) = 3n + 3(−1)n f (15) = 315 − 3 = 14, 348, 904 Practice Problem: The tips of a five-pointed star are to be painted red, white and blue. How many ways can this be done if no adjacent points can be the same color? (North Carolina State High School Mathematics Contest 2003) [Answer: 30] Solution was written by Bryce Taylor and compiled from Art of Problem Solving Forums.