Don't Order The Same

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 a b , \frac{a}{b}, where a a and b b are coprime positive integers. What is a + b ? a+b?


The answer is 265.

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.

1 solution

Andy Hayes
Jun 1, 2017

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 . 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 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 \text{SBLBSB}

Construct a recurrence relation. Let d ( n ) d(n) be the number of ways to compose a string of n n letters such that adjacent letters are different and the first and last letters are different. Let s ( n ) s(n) be the number of ways to compose a string of n n letters such that adjacent letters are different and the first and last letters are the same. Then,

d ( n ) = d ( n 1 ) + 2 s ( n 1 ) s ( n ) = d ( n 1 ) \begin{aligned} d(n) &= d(n-1)+2s(n-1) \\ s(n) &= d(n-1) \end{aligned}

This gives d ( n ) = d ( n 1 ) + 2 d ( n 2 ) . d(n)=d(n-1)+2d(n-2). Now observe that d ( 1 ) = 0 d(1)=0 and d ( 2 ) = 6. d(2)=6. Using the recurrence relation, we find d ( 6 ) = 66. d(6)=66. Thus, the probability is 66 3 6 = 22 243 , \frac{66}{3^6}=\frac{22}{243}, and so a + b = 265 . a+b=\boxed{265}.

Nice question and solution! Just a thought on phrasing; perhaps "The probability that no two adjacent guests order the same entrées is a b \frac{a}{b} , ...." might be better. See what you think.

Brian Charlesworth - 4 years ago

Log in to reply

Yes, I think that's better, thanks!

Andrew Hayes Staff - 4 years ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...