Riddler Classic – 10-14-2016 – Arbitraria

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.

prob1

prob2

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s