November 23, 2020
In my previous post where I debuted my series on solving puzzles published on FiveThirtyEight Riddler by Zach Wissner-Gross, I discussed my solution to the Riddler Express puzzle. In this blog, I will be talking about my approach to solving the Riddler Classic puzzle, something that I'm sure my readers will be "thankful" for ;-).
(Disclaimer: each week the puzzles are published on the Friday, and the deadline to submit the solution is by Monday at 11:59pm EST. Therefore, if I do post solutions as part of my blog for the puzzles that week, I will NOT actively publicize the blog until the following Tuesday. If you happen to come across my blog before then, out of courtesy of other puzzle solvers, please also do not share until then! Thanks!)
Date published: Friday, November 20, 2020
Please do not share until: Tuesday, November 24, 2020
Happy Thanksgiving! I wish all of my readers a wonderful, joyous, and most importantly, safe Thanksgiving this year. In extraordinary times like this, I just remind everyone to look out for each other and be mindful of those around you. If you don't have to, please do not travel. Virtual Thanksgiving might not sound fun, but please remember we are doing this for the good of everyone around us. If we all do our parts, we will get through this together very soon!
In this week's thankful Riddler Classic puzzle, Zach published the following question, whereby you and 19 of your family members are seated virtually around a dinner table for the Thanksgiving dinner. You currently hold the cranberry sauce, and after giving yourself a generous serving, you pass it to either the person to your left or your right, at random, and the process continues until the last person has had a chance at the cranberry sauce. Among all of you, who has the greatest chance of getting the sauce last? Of course, that person won't be you, as you started with the sauce.
(Original link here).
First of all, I want to label the people around the table for easy naming. I am assigning you as person 1, and in a counter-clockwise fashion, enumerate up to 20, so that the person immediately to your right is person 2 and the person immediately to your left is person 20. All of you sit in a circle, as described.
(My terrible attempt at drawing a circle of numbers. :P)
Next, I thought about the answer from an intuition standpoint. I'd figured that since you (person 1) started with the cranberry sauce, then the people near you would have a greater chance at getting the cran sauce then the people sitting furthest away from you, namely persons 10 and 11. However, times have taught me in the past that intuitions are not always correct, and so the very next thing I decided to do was a Monte-Carlo simulation.
I want to use the power of Matlab, once again, to my advantage. However, unlike the Riddler Express, this time I am not performing a brute-force search, but rather, trying to produce an empirical result on who shall receive the cran sauce last. This is based on a Monte-Carlo simulation which I will execute a million trials of passing the cran sauce, starting with you, and see who would be the unlucky person to receive the cran sauce last the greatest number of times. The program is pretty straightforward:
function lastPersonIdx = getLastPerson()
% This function gets the last person index (1-20) of the Cranberry
% Sauce problem via Monte-Carlo simulation. Starting from person 1,
% the cranberry saunce is passed either to the current person's left
% (person 20) or to person 1's right (person 2), with equally likely
% probability (1/2). Then the process continues. This function
% generates and returns the index of the last person to have the
% cranberry sauce passed.
lastPersonIdx = -1;
CranSauceRcvd = zeros(1, 20); % Cranberry sauce received tracker
CranSauceRcvd(1) = 1; % You start by having the cran sauce.
CurrentSauceHolder = 0; % You are person 0 in the simulation for easy mod op;
% Matlab, however, is 1-based.
while true
passLeft = rand < 0.5; % 50% chance of passing left
if passLeft
CurrentSauceHolder = mod(CurrentSauceHolder-1, 20);
else
CurrentSauceHolder = mod(CurrentSauceHolder+1, 20);
end
% Update the CranSauceRcvd Info
CranSauceRcvd(CurrentSauceHolder+1) = 1; % Again Matlab is 1-based
% fprintf('Current saunce holder is person %d\n.', CurrentSauceHolder+1);
if all(CranSauceRcvd)
lastPersonIdx = CurrentSauceHolder+1;
break;
end
end
end
Here I am assuming there is an equally likely probability of any person passing the sauce to his/her left vs right, and hence the "rand < 0.5" line. By the way, "rand" function in Matlab generates a number between 0 and 1 according to the uniform distribution, so "rand < 0.5" is truly a fair coin flip.
Then, I pass this function to the simulation, as follows:
%% Start of Simuation
simCount = 1e6; % Number of Trials
lastPersonCounter = zeros(20, 1); % 20 people at dinner
for k = 1:simCount
lastPersonIdx = getLastPerson();
lastPersonCounter(lastPersonIdx) = lastPersonCounter(lastPersonIdx) + 1;
end
%% Display in Histogram
figure;
bar(lastPersonCounter/simCount);
title('Normalized Bar Graph of Number of Times Each Person Last Received the Cran Sauce');
xlabel('Person');
ylabel('Fraction of Last Cransauce Received');
The output is a normalized bar graph showing the fraction of times each person from 1-20 received the cran sauce last. Of course, person 1 would have fraction of 0 since you start with the sauce. And what did I get?
What?? It appears that persons 2-20 each had about equal fraction of times receiving the cran sauce last, which is about \(\frac{1}{19}\). Did my eyes deceive me? Was there something wrong with my program?
Well, it turned out that there was nothing wrong with my program and no, my eyes did not deceive me.
Before I jump into the analysis, let me explore a bit more. In the previous Monte-Carlo Simulation, I assumed that each person had equal probability of passing the sauce either way. However, what if one direction had a greater probability than the other? I simulated this by introducing a "leftLean", i.e. the probability of each person passing the sauce to his/her left. If leftLean is greater than 0.5, then the direction trends to left, and vice versa for right.
My new "getLastPerson" function is thus as follows:
function lastPersonIdx = getLastPersonExtended(leftLean)
% This function gets the last person index (1-20) of the Cranberry
% Sauce problem via Monte-Carlo simulation. Starting from person 1,
% the cranberry saunce is passed either to the current person's left
% (person 20) or to person 1's right (person 2), with equally likely
% probability (1/2). Then the process continues. This function
% generates and returns the index of the last person to have the
% cranberry sauce passed.
% In this extended version, we introduce a "lean" for passing to the
% left. That is, if leftLean is > 0.5, the current sauce holder is
% more likely to pass to his/her left, and vice versa.
lastPersonIdx = -1;
CranSauceRcvd = zeros(1, 20); % Cranberry sauce received tracker
CranSauceRcvd(1) = 1; % You start by having the cran sauce.
CurrentSauceHolder = 0; % You are person 0 in the simulation for easy mod op;
% Matlab, however, is 1-based.
while true
passLeft = rand < leftLean;
if passLeft
CurrentSauceHolder = mod(CurrentSauceHolder-1, 20);
else
CurrentSauceHolder = mod(CurrentSauceHolder+1, 20);
end
% Update the CranSauceRcvd Info
CranSauceRcvd(CurrentSauceHolder+1) = 1; % Again Matlab is 1-based
% fprintf('Current saunce holder is person %d\n.', CurrentSauceHolder+1);
if all(CranSauceRcvd)
lastPersonIdx = CurrentSauceHolder+1;
break;
end
end
end
Pretty much the same as before, except passLeft is no longer constraint to 0.5 but any arbitrary probability. In that case, let's simulate for some probabilities!
The last graph is for sanity check to ensure we have the same result as before when "leftLean" is equal = 0.5.
When the probability of passing to the left is greater than 0.5, from the first two graphs it is clear that the probability of person 2, i.e. the person immediately to your right has the greatest chance of receiving the sauce last. This is not surprising, as the sauce tends to go leftward. What is perhaps a bit surprising would be how fast the graph skews. You can already see an exponential decay when passLeft probability goes from 0.5 to 0.6, and when passLeft is only at 0.7, we have extreme skewing. In fact, below is the raw data count on the number of times each person received the cran sauce last over 1 million trials:
lastPersonCounter =
0
570887
244834
105889
44849
19285
8009
3600
1469
686
290
114
52
23
4
5
2
1
1
0
Remember, you are the first person, so you never receive the cran sauce last. However, starting with the person immediately to your right, that person received the cran sauce last about 57% of the time. In one million trials, the person immediately to your left never received the cran sauce last even once! And remember this is only with passLeft probability of 0.7!
So it appears the answer is as follows: when there is an equal probability for each person to pass the cran sauce either to his/her left or right, each person other than you has the same probability of receiving the cran sauce last (1/19). If the probability of passing to the left is greater than 0.5, then the person to your immediate right has the greatest chance of getting the sauce last. Conversely, if the probability of passing to one's right is greater than that to the left, then the person to your immediate left has the greatest chance of receiving the sauce last.
First of all I just want to remark how this disproves the intuition here. In no scenarios does the person sitting across from you risk getting the sauce last. In a postmortem analysis, this is no longer surprising, as if there is a skew in the direction, the people that won't be mostly affected would be those not on the wrong end of the stick, so to speak.
But why is everyone else but you have an equal chance of getting the sauce last when the direction is not skewed? One way to see this, perhaps, is by symmetry. When a new person receives the sauce, and over long periods of time, the sauce has equal chances of ending up in anyone's hand, that person becomes the new "you". If there are any special persons in the table that are more likely than others to receive the sauce last, since the direction of the sauce is not skewed, then when the new "you" gets the sauce, it would mean that some other people around the table would become new "favorites" to get the sauce last. If everyone is special the same way, then no one is.
Please find the Simulation Code here.