14
$\begingroup$

You are sitting at a round dinner table with $N$ other people (i.e. $N+1$ people all together). One of the other guests is the first to pick up the gravy boat and pour some on their potatoes. It then gets passed at random to either of the adjacent people ($50\%$ each way). This person, after pouring themselves some gravy, also passes it to a neighbour, and as they are so engrossed in conversation it is again equally likely to be either neighbour. This continues, with the gravy boat being passed from person to person in a random direction each time.

You don't want to be the last person to get any gravy. For you to have the smallest probability of being last, which other guest should be the first to use the gravy? And what is that probability?

I don't know the original source of this puzzle, but it has been doing the rounds for a few years and in my opinion it is destined to become a classic. See for example this Math SE question.

$\endgroup$
  • $\begingroup$ To clarify, for whatever reason, I'm not allowed to just pick up the gravy boat before anyone else does? $\endgroup$ – MikeTheLiar Mar 4 at 22:05
  • $\begingroup$ @MikeTheLiar "One of the other guests is the first to pick up the gravy" and "It then gets passed randomly to either adjacent person" and "which other guest should be first to use the gravy" is sufficient enough to clarify $\endgroup$ – Adam Mar 4 at 23:01
  • $\begingroup$ Is this the way one should organize seating and serving at a party? $\endgroup$ – Buck Thorn Mar 5 at 9:25
11
$\begingroup$

Fascinating.

The probability of being last is $1/N$ regardless of which guest starts with the gravy.

I had to do the calculation with Markov chains to get the answer. But after getting it I thought about it.

It is a certainty that one of your neighbors will get it before you. You can choose that neighbor by sitting next to the first person, or you can wait patiently until one of your neighbors gets it.

From there, to be the last person the gravy needs to go all the way around to your other neighbor without first getting to you. There is some probability that it does this.
But, actually, everyone has the same situation. One of their neighbors will get it and then there is some probability that it goes all the way around from there to your other neighbor without coming back to you through your first neighbor.

Since everyone is in the same situation, the probability of being the last is the same for everyone and so everyone has a $1/n$ chance to be the last person getting the gravy.

Out of interest, here's how I did the calculation beforehand. First I envisaged a state diagram (Markov) something like this:

Markov Chain

Here we start on the middle ring ($1-n$). If we get to the $1$ we move onto the inner ring, which I call $1'-n'$. As you can see, $1'=1$.

Similarly, if we get to $n$, then we move onto the outer ring, labeled $1''-n''$. Again $n''=n$.

This ends well if we get to 0 (gree), and it ends badly if we get to $n'$ or $1''$ (red). In fact, we may as well have $n'=1''$.

So now this leads to the following transition matrix when $n=5$. Here the columns and rows are $(1=1'),2,3,4,(5=5''),2',3',4',2'',3'',4'',0,(1''=n')$.

\begin{equation} M=\left( \begin{array}{ccccc|ccc|ccc|cc} 0 &0 &0 &0 &0 &\frac{1}{2} &0 &0 &0 &0 &0 &\frac{1}{2} &0 \\ \frac{1}{2} &0 &\frac{1}{2} &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 \\ 0 &\frac{1}{2} &0 &\frac{1}{2} &0 &0 &0 &0 &0 &0 &0 &0 &0 \\ 0 &0 &\frac{1}{2} &0 &\frac{1}{2} &0 &0 &0 &0 &0 &0 &0 &0 \\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &\frac{1}{2} &\frac{1}{2} &0 \\ \frac{1}{2} &0 &0 &0 &0 &0 &\frac{1}{2} &0 &0 &0 &0 &0 &0 \\ 0 &0 &0 &0 &0 &\frac{1}{2} &0 &\frac{1}{2} &0 &0 &0 &0 &0 \\ 0 &0 &0 &0 &0 &0 &\frac{1}{2} &0 &0 &0 &0 &0 &\frac{1}{2} \\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &\frac{1}{2} &0 &0 &\frac{1}{2} \\ 0 &0 &0 &0 &0 &0 &0 &0 &\frac{1}{2} &0 &\frac{1}{2} &0 &0 \\ 0 &0 &0 &0 &\frac{1}{2} &0 &0 &0 &0 &\frac{1}{2} &0 &0 &0 \\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &0 \\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 \end{array} \right) \end{equation}

where the vertical lines are a guide to the eye separating the $1-5$ from the $2'-4'$ from the $2''-4''$ from the two endings.

Then we can either run $M=M^2$ hundred times to calculate $M^\inf\approx M^{2^{100}}$ or do an inversion following the formula here. Either way, we get an absorbing probability of:

\begin{equation} B=\left( \begin{array}{cc} \frac{4}{5} &\frac{1}{5} \\ \frac{4}{5} &\frac{1}{5} \\ \frac{4}{5} &\frac{1}{5} \\ \frac{4}{5} &\frac{1}{5} \\ \frac{4}{5} &\frac{1}{5} \\ \frac{3}{5} &\frac{2}{5} \\ \frac{2}{5} &\frac{3}{5} \\ \frac{1}{5} &\frac{4}{5} \\ \frac{1}{5} &\frac{4}{5} \\ \frac{2}{5} &\frac{3}{5} \\ \frac{3}{5} &\frac{2}{5} \end{array} \right) \end{equation}

The only relevant numbers here are the first 5 rows (corresponding to states $1-5$). The remaining rows are if you start in states $2'-4'$ or $2''-4''$. The left column gives the probability of not being last to get the gravy and the right column gives the probability of being the last to get the gravy.

I ran this for a few different $n$ values and realized that it was a constant. I should have realized there would be something up with the reference to this becoming a classic puzzle.

Very neat puzzle.

$\endgroup$
  • $\begingroup$ Did you do a lot of calculations before you arrived at that answer? :-) $\endgroup$ – Jaap Scherphuis Mar 4 at 20:33
  • $\begingroup$ I did - I used Markov chains. I'll write it up, but I'm trying to think of the clever way of getting there which must exist. $\endgroup$ – Dr Xorile Mar 4 at 20:35
  • $\begingroup$ There is indeed a neat, calculation-free, argument for it. $\endgroup$ – Jaap Scherphuis Mar 4 at 20:36
  • 1
    $\begingroup$ $(+1)$: congratulations on $14$k reputation! $\endgroup$ – Mr Pie Apr 3 at 0:45
  • 1
    $\begingroup$ @user477343, Thanks! You've pushed me over the edge! $\endgroup$ – Dr Xorile Apr 3 at 0:56
6
$\begingroup$

Suppose that your neighbour starts, and call the probability of you being last "x".

Then, suppose that some other person starts.

There is exactly one way for you to be the last one:
* first, the gravy comes to your neighbour
* next, it goes all around the table to your other neighbour.

As we very well know, the first happens

with probability 1

and the second happens

with probability x.

Therefore,

it doesn't matter who starts, and the probability is always the same.

By symmetry

the same applies for all the guests who didn't pick up the gravy

so the probability of it being exactly you who is last is

$\frac{1}{\text N}$

$\endgroup$
  • 1
    $\begingroup$ can you expand on the "therefore" because I just see you restating your assumptions and then concluding something from them that I don't see following. $\endgroup$ – Kate Gregory Mar 4 at 21:49
  • $\begingroup$ @KateGregory You get the probability of two things both happening by multiplying their individual probabilities together. In this case, that product is x, which, well, is equal to x. $\endgroup$ – Bass Mar 4 at 22:16
  • 2
    $\begingroup$ But you said "the chance of it reaching you last is x therefore the chance of it reaching you last is x" -- how is that proving anything? It is the "therefore" part that makes no sense. $\endgroup$ – Kate Gregory Mar 4 at 22:25
  • 1
    $\begingroup$ I agree with Kate. I get what you are going for however the way you explained it on the surface can sound like you don't understand the conclusion at all. Explain how the gravy inevitably propagates around the table, not the consequence of the propagation. You say the probability of the consequence is 'X' and therefore the consequence of the probability is 'X' so where is the definition of 'X'? $\endgroup$ – Adam Mar 4 at 22:49
  • 1
    $\begingroup$ Well of course you say what 'X' is at the beginning however I was referring to how you explain the consequence of event 'X' and the probability of 'X' but never quite 'X'. It is difficult to explain, when you read your answer while already knowing the solution it makes perfect sense but in reality you have a jump in your argument at "therefore" (even although there is no jump in logic) and the reader is forced to make their own conclusion at this point. I don't think it helps that everything is in little pieces, its really just a structure problem. $\endgroup$ – Adam Mar 5 at 7:20
2
$\begingroup$

I agree this is a lovely surprising puzzle, deserving of an elegant solution.

Let $p_k$ be the probability that the $k^{th}$ guest, counted clockwise from the gravy's start point, is the last to have the gravy. There is a 50/50 chance of passing either left or right, after which we are left with a shifted version of the same problem. With a little thought, this implies $$p_k=\frac12p_{k-1}+\frac12p_{k+1}$$holds for all $2\le k\le n-1$. We therefore have a list of numbers $p_1,p_2,\dots,p_n$ where each number is halfway between its neighbors. This implies that the list grows linearly; that is, $p_k=ak+b$ is some linear function of $k$. But by the symmetry of the problem, you must have $p_1=p_n$, so the slope of this line must be zero, so in fact all $p_k$ are equal!

$\endgroup$
  • $\begingroup$ I'm not so sure this argument works. It completely ignores where the gravy has already been. After the gravy has been passed along once, the person who passed the gravy can no longer be the last to get the gravy, so it is no longer the same situation as before but shifted. So I'm not sure how you can relate the probabilities to each other like you do. $\endgroup$ – Jaap Scherphuis Apr 2 at 19:58
  • $\begingroup$ It turns out that this does not matter. True, we have one fewer constraint, because one person (person number $1$, say) has already been visited. However, that constraint was redundant anyway; you need to visit person $2$ before visiting person $k-1$, which implies you visit person $1$ before person $k-1$ automatically. So the fact that $k-1$ is already visited does not make visiting $k-1$ last any easier or harder. $\endgroup$ – Mike Earnest Apr 2 at 23:11
  • $\begingroup$ I got it now I think. I was confused because you made the claim that after the gravy has moved, the situation is the same, just shifted. That is not true for the situation as a whole because after it has moved, one person or other can no longer be the last to get gravy. However, I see now that it is true if you look at it from the point of view from any individual person other than those at starting locations 1 and n - their situation is essentially the same as before. For them the first gravy move does not really matter, and gives the equation you provided. $\endgroup$ – Jaap Scherphuis Apr 3 at 6:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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