# Waiting for the gravy at a dinner table

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.

• To clarify, for whatever reason, I'm not allowed to just pick up the gravy boat before anyone else does? Mar 4, 2019 at 22:05
• @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
Mar 4, 2019 at 23:01
• Is this the way one should organize seating and serving at a party? Mar 5, 2019 at 9:25

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:

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')$$.

$$$$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)$$$$

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:

$$$$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)$$$$

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.

• Did you do a lot of calculations before you arrived at that answer? :-) Mar 4, 2019 at 20:33
• 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. Mar 4, 2019 at 20:35
• There is indeed a neat, calculation-free, argument for it. Mar 4, 2019 at 20:36
• $(+1)$: congratulations on $14$k reputation! Apr 3, 2019 at 0:45
• @user477343, Thanks! You've pushed me over the edge! Apr 3, 2019 at 0:56

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}$$

• 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. Mar 4, 2019 at 21:49
• @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.
– Bass
Mar 4, 2019 at 22:16
• 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. Mar 4, 2019 at 22:25
• 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'?
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!
• 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. Apr 2, 2019 at 23:11