Six guests sit around a circular table at a wedding reception. They each order one of three entrées: Salmon, Beef, or Lasagna. Each guest chooses their entrée independently at random, with each choice equally likely.
The probability that no two adjacent guests order the same entrées is where and are coprime positive integers. What is
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
The denominator of the probability will be the total number of ways for guests to choose their meals. Since there are 3 choices for each guest, this is 3 6 . The numerator will be the number of ways to choose entrées such that adjacent entrées are different.
Fix the sequence of guests at a point. Now, we're looking for the number of ways to compose a string of n letters using the letters S, B, and L such that adjacent letters are different and the first and last letters are different. For example:
SBLBSB
Construct a recurrence relation. Let d ( n ) be the number of ways to compose a string of n letters such that adjacent letters are different and the first and last letters are different. Let s ( n ) be the number of ways to compose a string of n letters such that adjacent letters are different and the first and last letters are the same. Then,
d ( n ) s ( n ) = d ( n − 1 ) + 2 s ( n − 1 ) = d ( n − 1 )
This gives d ( n ) = d ( n − 1 ) + 2 d ( n − 2 ) . Now observe that d ( 1 ) = 0 and d ( 2 ) = 6 . Using the recurrence relation, we find d ( 6 ) = 6 6 . Thus, the probability is 3 6 6 6 = 2 4 3 2 2 , and so a + b = 2 6 5 .