Waiting for the gravy at a dinner table
Clash Royale CLAN TAG#URR8PPP
$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.
mathematics
$endgroup$
add a comment |
$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.
mathematics
$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$
– Try Hard
Mar 5 at 9:25
add a comment |
$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.
mathematics
$endgroup$
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.
mathematics
mathematics
edited Mar 5 at 6:07
Jaap Scherphuis
asked Mar 4 at 19:13
Jaap ScherphuisJaap Scherphuis
16.6k12772
16.6k12772
$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$
– Try Hard
Mar 5 at 9:25
add a comment |
$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$
– Try Hard
Mar 5 at 9:25
$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$
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$
@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$
– Try Hard
Mar 5 at 9:25
$begingroup$
Is this the way one should organize seating and serving at a party?
$endgroup$
– Try Hard
Mar 5 at 9:25
add a comment |
2 Answers
2
active
oldest
votes
$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:
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')$.
beginequation
M=left(
beginarrayccc
0 &0 &0 &0 &0 ½ &0 &0 &0 &0 &0 ½ &0 \
frac12 &0 ½ &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 \
0 ½ &0 ½ &0 &0 &0 &0 &0 &0 &0 &0 &0 \
0 &0 ½ &0 ½ &0 &0 &0 &0 &0 &0 &0 &0 \
0 &0 &0 &0 &0 &0 &0 &0 &0 &0 ½ ½ &0 \
frac12 &0 &0 &0 &0 &0 ½ &0 &0 &0 &0 &0 &0 \
0 &0 &0 &0 &0 ½ &0 ½ &0 &0 &0 &0 &0 \
0 &0 &0 &0 &0 &0 ½ &0 &0 &0 &0 &0 ½ \
0 &0 &0 &0 &0 &0 &0 &0 &0 ½ &0 &0 ½ \
0 &0 &0 &0 &0 &0 &0 &0 ½ &0 ½ &0 &0 \
0 &0 &0 &0 ½ &0 &0 &0 &0 ½ &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
endarray
right)
endequation
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^infapprox M^2^100$ or do an inversion following the formula here. Either way, we get an absorbing probability of:
beginequation
B=left(
beginarraycc
frac45 &frac15 \
frac45 &frac15 \
frac45 &frac15 \
frac45 &frac15 \
frac45 &frac15 \
frac35 &frac25 \
frac25 &frac35 \
frac15 &frac45 \
frac15 &frac45 \
frac25 &frac35 \
frac35 &frac25
endarray
right)
endequation
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
$begingroup$
Wow this makes a whole lot of sense. rot13(Gur gnoyr tvirf n snyfr frafr bs cebterff jurer va ernyvgl vgf whfg yvxr lbh ner cnffvat vg qverpgyl gb n enaqbz crefba. Ab jbaqre gur ceboyrz vf cbchyne)
$endgroup$
– Adam
Mar 4 at 21:04
add a comment |
$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
$frac1text 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
|
show 2 more comments
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "559"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f80243%2fwaiting-for-the-gravy-at-a-dinner-table%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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:
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')$.
beginequation
M=left(
beginarrayccc
0 &0 &0 &0 &0 ½ &0 &0 &0 &0 &0 ½ &0 \
frac12 &0 ½ &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 \
0 ½ &0 ½ &0 &0 &0 &0 &0 &0 &0 &0 &0 \
0 &0 ½ &0 ½ &0 &0 &0 &0 &0 &0 &0 &0 \
0 &0 &0 &0 &0 &0 &0 &0 &0 &0 ½ ½ &0 \
frac12 &0 &0 &0 &0 &0 ½ &0 &0 &0 &0 &0 &0 \
0 &0 &0 &0 &0 ½ &0 ½ &0 &0 &0 &0 &0 \
0 &0 &0 &0 &0 &0 ½ &0 &0 &0 &0 &0 ½ \
0 &0 &0 &0 &0 &0 &0 &0 &0 ½ &0 &0 ½ \
0 &0 &0 &0 &0 &0 &0 &0 ½ &0 ½ &0 &0 \
0 &0 &0 &0 ½ &0 &0 &0 &0 ½ &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
endarray
right)
endequation
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^infapprox M^2^100$ or do an inversion following the formula here. Either way, we get an absorbing probability of:
beginequation
B=left(
beginarraycc
frac45 &frac15 \
frac45 &frac15 \
frac45 &frac15 \
frac45 &frac15 \
frac45 &frac15 \
frac35 &frac25 \
frac25 &frac35 \
frac15 &frac45 \
frac15 &frac45 \
frac25 &frac35 \
frac35 &frac25
endarray
right)
endequation
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
$begingroup$
Wow this makes a whole lot of sense. rot13(Gur gnoyr tvirf n snyfr frafr bs cebterff jurer va ernyvgl vgf whfg yvxr lbh ner cnffvat vg qverpgyl gb n enaqbz crefba. Ab jbaqre gur ceboyrz vf cbchyne)
$endgroup$
– Adam
Mar 4 at 21:04
add a comment |
$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:
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')$.
beginequation
M=left(
beginarrayccc
0 &0 &0 &0 &0 ½ &0 &0 &0 &0 &0 ½ &0 \
frac12 &0 ½ &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 \
0 ½ &0 ½ &0 &0 &0 &0 &0 &0 &0 &0 &0 \
0 &0 ½ &0 ½ &0 &0 &0 &0 &0 &0 &0 &0 \
0 &0 &0 &0 &0 &0 &0 &0 &0 &0 ½ ½ &0 \
frac12 &0 &0 &0 &0 &0 ½ &0 &0 &0 &0 &0 &0 \
0 &0 &0 &0 &0 ½ &0 ½ &0 &0 &0 &0 &0 \
0 &0 &0 &0 &0 &0 ½ &0 &0 &0 &0 &0 ½ \
0 &0 &0 &0 &0 &0 &0 &0 &0 ½ &0 &0 ½ \
0 &0 &0 &0 &0 &0 &0 &0 ½ &0 ½ &0 &0 \
0 &0 &0 &0 ½ &0 &0 &0 &0 ½ &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
endarray
right)
endequation
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^infapprox M^2^100$ or do an inversion following the formula here. Either way, we get an absorbing probability of:
beginequation
B=left(
beginarraycc
frac45 &frac15 \
frac45 &frac15 \
frac45 &frac15 \
frac45 &frac15 \
frac45 &frac15 \
frac35 &frac25 \
frac25 &frac35 \
frac15 &frac45 \
frac15 &frac45 \
frac25 &frac35 \
frac35 &frac25
endarray
right)
endequation
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
$begingroup$
Wow this makes a whole lot of sense. rot13(Gur gnoyr tvirf n snyfr frafr bs cebterff jurer va ernyvgl vgf whfg yvxr lbh ner cnffvat vg qverpgyl gb n enaqbz crefba. Ab jbaqre gur ceboyrz vf cbchyne)
$endgroup$
– Adam
Mar 4 at 21:04
add a comment |
$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:
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')$.
beginequation
M=left(
beginarrayccc
0 &0 &0 &0 &0 ½ &0 &0 &0 &0 &0 ½ &0 \
frac12 &0 ½ &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 \
0 ½ &0 ½ &0 &0 &0 &0 &0 &0 &0 &0 &0 \
0 &0 ½ &0 ½ &0 &0 &0 &0 &0 &0 &0 &0 \
0 &0 &0 &0 &0 &0 &0 &0 &0 &0 ½ ½ &0 \
frac12 &0 &0 &0 &0 &0 ½ &0 &0 &0 &0 &0 &0 \
0 &0 &0 &0 &0 ½ &0 ½ &0 &0 &0 &0 &0 \
0 &0 &0 &0 &0 &0 ½ &0 &0 &0 &0 &0 ½ \
0 &0 &0 &0 &0 &0 &0 &0 &0 ½ &0 &0 ½ \
0 &0 &0 &0 &0 &0 &0 &0 ½ &0 ½ &0 &0 \
0 &0 &0 &0 ½ &0 &0 &0 &0 ½ &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
endarray
right)
endequation
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^infapprox M^2^100$ or do an inversion following the formula here. Either way, we get an absorbing probability of:
beginequation
B=left(
beginarraycc
frac45 &frac15 \
frac45 &frac15 \
frac45 &frac15 \
frac45 &frac15 \
frac45 &frac15 \
frac35 &frac25 \
frac25 &frac35 \
frac15 &frac45 \
frac15 &frac45 \
frac25 &frac35 \
frac35 &frac25
endarray
right)
endequation
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$
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')$.
beginequation
M=left(
beginarrayccc
0 &0 &0 &0 &0 ½ &0 &0 &0 &0 &0 ½ &0 \
frac12 &0 ½ &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 \
0 ½ &0 ½ &0 &0 &0 &0 &0 &0 &0 &0 &0 \
0 &0 ½ &0 ½ &0 &0 &0 &0 &0 &0 &0 &0 \
0 &0 &0 &0 &0 &0 &0 &0 &0 &0 ½ ½ &0 \
frac12 &0 &0 &0 &0 &0 ½ &0 &0 &0 &0 &0 &0 \
0 &0 &0 &0 &0 ½ &0 ½ &0 &0 &0 &0 &0 \
0 &0 &0 &0 &0 &0 ½ &0 &0 &0 &0 &0 ½ \
0 &0 &0 &0 &0 &0 &0 &0 &0 ½ &0 &0 ½ \
0 &0 &0 &0 &0 &0 &0 &0 ½ &0 ½ &0 &0 \
0 &0 &0 &0 ½ &0 &0 &0 &0 ½ &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
endarray
right)
endequation
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^infapprox M^2^100$ or do an inversion following the formula here. Either way, we get an absorbing probability of:
beginequation
B=left(
beginarraycc
frac45 &frac15 \
frac45 &frac15 \
frac45 &frac15 \
frac45 &frac15 \
frac45 &frac15 \
frac35 &frac25 \
frac25 &frac35 \
frac15 &frac45 \
frac15 &frac45 \
frac25 &frac35 \
frac35 &frac25
endarray
right)
endequation
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.
edited Mar 6 at 22:54
answered Mar 4 at 20:30
Dr XorileDr Xorile
14k32977
14k32977
$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
$begingroup$
Wow this makes a whole lot of sense. rot13(Gur gnoyr tvirf n snyfr frafr bs cebterff jurer va ernyvgl vgf whfg yvxr lbh ner cnffvat vg qverpgyl gb n enaqbz crefba. Ab jbaqre gur ceboyrz vf cbchyne)
$endgroup$
– Adam
Mar 4 at 21:04
add a comment |
$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
$begingroup$
Wow this makes a whole lot of sense. rot13(Gur gnoyr tvirf n snyfr frafr bs cebterff jurer va ernyvgl vgf whfg yvxr lbh ner cnffvat vg qverpgyl gb n enaqbz crefba. Ab jbaqre gur ceboyrz vf cbchyne)
$endgroup$
– Adam
Mar 4 at 21:04
$begingroup$
Did you do a lot of calculations before you arrived at that answer? :-)
$endgroup$
– Jaap Scherphuis
Mar 4 at 20:33
$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$
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
$begingroup$
There is indeed a neat, calculation-free, argument for it.
$endgroup$
– Jaap Scherphuis
Mar 4 at 20:36
$begingroup$
Wow this makes a whole lot of sense. rot13(Gur gnoyr tvirf n snyfr frafr bs cebterff jurer va ernyvgl vgf whfg yvxr lbh ner cnffvat vg qverpgyl gb n enaqbz crefba. Ab jbaqre gur ceboyrz vf cbchyne)
$endgroup$
– Adam
Mar 4 at 21:04
$begingroup$
Wow this makes a whole lot of sense. rot13(Gur gnoyr tvirf n snyfr frafr bs cebterff jurer va ernyvgl vgf whfg yvxr lbh ner cnffvat vg qverpgyl gb n enaqbz crefba. Ab jbaqre gur ceboyrz vf cbchyne)
$endgroup$
– Adam
Mar 4 at 21:04
add a comment |
$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
$frac1text 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
|
show 2 more comments
$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
$frac1text 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
|
show 2 more comments
$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
$frac1text N$
$endgroup$
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
$frac1text N$
answered Mar 4 at 21:25
BassBass
30.8k472188
30.8k472188
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
|
show 2 more comments
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
1
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$
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
$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
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
$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
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
$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
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
$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
|
show 2 more comments
Thanks for contributing an answer to Puzzling Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f80243%2fwaiting-for-the-gravy-at-a-dinner-table%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$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$
– Try Hard
Mar 5 at 9:25