Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This puzzle is from the book "Mathematical Puzzles: a connoisseur's collection", and I am only asking for a part of it.

48 people are seated in a big circular table, where they find between each pair of settings, there is one napkin. As each person is seated, he chooses one napkin from his left, or right. If both are present, he choose it randomly. The question is, if the maitre d' seats each guest and try to make the number of napkinless guests as many as possible, what is the expected number?

Suppose that the first guest take the napkin to his right, then the maitre d' should seat the second guest two spaces to the right of the first, making one open seat so that anyone who seats here can possibly have no napkins to choose. Then, if the second guest actually choose the left napkin, then the next guest is seated to the right position. Otherwise, if he chooses the right again, the next guest should be seated two space to the right of the second guest. Then, the expected number of napkinless guests is 1/6 of the total number of guests.

I don't follow the last conclusion. But in the book it seems to be obvious. How to compute this value?

share|improve this question

1 Answer 1

up vote 4 down vote accepted

The result "$1/6$ of the total number of guests" sounds as if it's independent of the given number of guests, $48$. It can't be correct in this generality, since there will not be any napkinless guests if there are only one or two guests. So I'm not sure whether you're looking for the solution for $48$ people or an asymptotic result. Here's how to derive the asymptotic result for a table large enough that we can ignore that we'll eventually get back where we started.

In that case, in the situation where guest $n$ has chosen the napkin to her right, there's a probability $1/2$ that guest $n+2$ also chooses right and we have to try again, and a probability $1/2$ that guest $n+2$ chooses left, leaving guest $n+1$ napkinless. In the latter case, we have to seat everyone to the right of guest $n+2$ until someone chooses right again to get back to the initial state, and the expected number of guests to seat until that happens is $2$. So the expected number $k$ of guests we have to seat in order to produce one napkinless guest is $k=2+(\frac12k+\frac12\cdot2)$, and thus $k=6$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.