21st APMC 1998 Problem 2 n points lie in a line. How many ways are there of coloring the points with 5 colors, one of them red, so that every two adjacent points are either the same color or one or more of them is red?
½(3 n+1 + (-1) n+1 ). Solution Let r n be the number of colorings with n points and nth point red. Let s n be the number of colorings with n points and nth point not red. Put t n = r n + s n . We have: r n = t n-1 s n = 4r n-1 + s n-1 Hence t n = r n + sn = t n-1 + 4r n-1 + s n-1 = t n-1 + 3t n-2 + (r n-1 + s n-1 ) = 2t n-1 + 3t n-2 . This is a standard linear recurrence, with general solution t n = A3 n + B(-1) n . We have t 1 = 5, t 2 = 13, so A = 3/2, B = -1/2. Hence result. 21st APMC 1998 © John Scholes jscholes@kalva.demon.co.uk 28 Nov 2003 Last corrected/updated 28 Nov 03