Here’s my solution to this weeks Riddler Classic puzzle from FiveThirtyEight. Here’s the question: “While traveling in the Kingdom of Arbitraria, you are accused of a heinous crime. Arbitraria decides who’s guilty or innocent not through a court system, but a board game. It’s played on a simple board: a track with sequential spaces numbered from 0 to 1,000. The zero space is marked “start,” and your token is placed on it. You are handed a fair six-sided die and three coins. You are allowed to place the coins on three different (nonzero) spaces. Once placed, the coins may not be moved.
After placing the three coins, you roll the die and move your token forward the appropriate number of spaces. If, after moving the token, it lands on a space with a coin on it, you are freed. If not, you roll again and continue moving forward. If your token passes all three coins without landing on one, you are executed. On which three spaces should you place the coins to maximize your chances of survival?
Extra credit: Suppose there’s an additional rule that you cannot place the coins on adjacent spaces. What is the ideal placement now? What about the worst squares — where should you place your coins if you’re making a play for martyrdom?”
Again, there are lots of ways to solve this but I chose to go the simulation route. I wrote up a little program in C to do 10,000,000 trials and kept track of how many times a particular space was landed on. Each trial the space is set to zero and then a random dice is rolled and the token moved forward and the space counter incremented. Here’s the commented code:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// returns a random dice roll
int roll()
{
return 1 + rand() % 6;
}
int main()
{
// Array to keep track of number of times a space was landed on
// Each time a space is landed on the number in the array is incremented
int spaces[1001] = {0};
int currentSpace, trialCount;
// Seed random number generator
srand(time(NULL));
// Each loop represents one trial from start to space 1000
for(trialCount=0; trialCount<10000000; trialCount++)
{
// Reset currentSpace to start and then begin trial
currentSpace = 0;
// While currentSpace is still on the board (<1000), roll again
// and increment that space in the array
while(currentSpace <= 1000)
{
spaces[currentSpace] += 1;
currentSpace += roll();
}
}
// Print out the results
for(int i=0; i<1000; i++)
{
printf("%3d %d \n", i, spaces[i]);
}
}
After printing these results I graphed them in Excel. Honestly, these weren’t the results I expected at all. I thought that the numbers at the end would be larger since there would be more ways to end up on those spaces but almost all of the spaces have the same probability. The notable exceptions are the three couple spaces since there are very few ways to land on them.
The second picture is zoomed in to the beginning to look at the interesting stuff. The three highest numbers are 5, 6, and 11 and when you add these up there is a 96.3% chance of hitting a coin and living. If you aren’t allowed to use consecutive spaces the best choice is 6, 10, and 12 with a 94.3% chance of living.
UPDATE: When I did the simulation the first time I always went all the way to the end of the 1000 spaces. So some of the times that it landed on eleven it actually would have already ended because it would have landed on five or six. So I redid the results stopping when it landed on a five or six. And this time the highest probability spaces were 5, 6, and 7 with a 76% chances of living.
UPDATE 2: When I did the math by hand, the percentage I found above was correct but I realized that I had forgotten about 4. So I reran it and indeed, 4, 5, and 6 is the best combination.
Thoughts? Questions? Concerns? Leave them in the comments below, especially if you found an error.
The Wandering Engineer 