MHB How Can You Paint 16 Seats in Consecutive Odd Red or Green Colors?

  • Thread starter Thread starter anemone
  • Start date Start date
  • Tags Tags
    2017
AI Thread Summary
The discussion revolves around the mathematical problem of painting 16 seats in a row either red or green, ensuring that the number of consecutive seats of the same color is always odd. Participants explore various approaches to solve this combinatorial challenge. The correct solution was provided by a user named Opalg, highlighting the importance of understanding patterns in color arrangement. The thread encourages engagement with the Problem of the Week format and invites users to submit their solutions. This mathematical inquiry emphasizes the complexity of combinatorial coloring problems.
anemone
Gold Member
MHB
POTW Director
Messages
3,851
Reaction score
115
Here is this week's POTW:

-----

In how many ways can we paint 16 seats in a row, each red or green, in such a way that the number of consecutive seats painted in the same color is always odd?

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!
 
Physics news on Phys.org
Congratulations to Opalg for his correct solution:), which you can find below:

Let $C_n$ be the number of ways of painting a row of $n$ seats according to those rules.

Notice that $C_1 = C_2 = 2$. (A single seat can be either red or green. A row of two seats can be either 1 red followed by 1 green, or 1 green followed by 1 red.)

Now think about a row of $n$ seats, divided into batches consisting of an odd number of consecutive seats of the same colour. There are two cases: the first seat in the row is either in a batch consisting of just that single seat, or it is in a batch of at least three seats.

Case 1 (a batch consisting of just one seat): There are then $n-1$ remaining seats, with $C_{n-1}$ ways of colouring them. In each case, the first seat will have to have the opposite colour to the first batch of the remaining seats. So that gives $C_{n-1}$ ways of colouring the row.

Case 2 (a batch consisting of at least three seats): Think of the first three seats as being a single unit (perhaps it is a three-seater bench?). Counting that bench as a single seat, we then have a total of $n-2$ units, and therefore $C_{n-2}$ ways of colouring them.

Putting the two cases together, you see that $C_n = C_{n-1} + C_{n-2}$. So the $C_n$s look exactly like the Fibonacci numbers $F_n$, except for the initial conditions $C_1 = C_2 = 2$ instead of $F_1 = F_2 = 1$. Therefore $C_n = 2F_n$, and $C_{16} = 2F_{16} = 2*987 = 1974.$
 
Back
Top