Evaluating Expected Values

Another week, another riddler. I really liked this one even if it was a bit linear. Ricky Jacobson’s problem reads:

You are given a fair, unweighted 10-sided die with sides labeled 0 to 9 and a sheet of paper to record your score. (If the very notion of a fair 10-sided die bothers you, and you need to know what sort of three-dimensional solid it is, then forget it — you have a random number generator that gives you an integer value from 0 to 9 with equal probability. Your loss — the die was a collector’s item.)

To start the game, you roll the die. Your current “score” is the number shown, divided by 10. For example, if you were to roll a 7, then your score would be 0.7. Then, you keep rolling the die over and over again. Each time you roll, if the digit shown by the die is less than or equal to the last digit of your score, then that roll becomes the new last digit of your score. Otherwise you just go ahead and roll again. The game ends when you roll a zero.

For example, suppose you roll the following: 6, 2, 5, 1, 8, 1, 0. After your first roll, your score would be 0.6, After the second, it’s 0.62. You ignore the third roll, since 5 is greater than the current last digit, 2. After the fourth roll, your score is 0.621. You ignore the fifth roll, since 8 is greater than the current last digit, 1. After the sixth roll, your score is 0.6211. And after the seventh roll, the game is over — 0.6211 is your final score.

What will be your average final score in this game?

This type of problem is fun because it relies on knowing expected values of lower rolls. Here is what a simple case looks like where you have a two sided die:

Value(2) #if you roll a 2 sided die:
	0: (1/2) * 0
	1: (1/2) * (1 + (1/10) * Value(2))

What does this mean? If you rolled a two sided die with these rules there are two possible outcomes and they each have an equal probability of coming up. The first is you roll a zero, in which case you get no additional points and the round is over. The second option is you roll a 1, in which you get one point and you get a tenth of the value of rolling another two sided die.

This is simple algebra and looks like this:

v2.png

Extending it here is what the 3 sided die case looks like:

Value(3) #if you roll a 3 sided die:
	0: (1/3) * 0
	1: (1/3) * (1 + (1/10) * Value(2))
	2: (1/3) * (2 + (1/10) * Value(3))

Now there are three options because we can roll a zero, one and two. Again, we use algebra:

v3.png

This can be extended all the way to the ten sided die case:

Value(10) #if you roll a 10 sided die:
	0: (1/10) * 0
	1: (1/10) * (1 + (1/10) * Value(2))
	2: (1/10) * (2 + (1/10) * Value(3))
	3: (1/10) * (3 + (1/10) * Value(4))
	4: (1/10) * (4 + (1/10) * Value(5))
	5: (1/10) * (5 + (1/10) * Value(6))
	6: (1/10) * (6 + (1/10) * Value(7))
	7: (1/10) * (7 + (1/10) * Value(8))
	8: (1/10) * (8 + (1/10) * Value(9))
	9: (1/10) * (9 + (1/10) * Value(10))

This evaluates to V(10) = 100/19 = 4.7368

Halloween Candy Problem

Another week, another Riddler. This is a puzzle about finding the number of combinations you can make of a candy:

Now that Halloween has come and gone, your chances of getting free candy have similarly disappeared. Desperate for sugar, you wander into the candy store, where three kinds of candy are being sold: Almond Soys (yummy, sounds vegan!), Butterflingers and Candy Kernels.

You’d like to buy at least one candy and at most 100, but you don’t care precisely how many you get of each or how many you get overall. So you might buy one of each, or you might buy 30 Almond Soys, six Butterflingers and 64 Candy Kernels. As long as you have somewhere between one and 100 candies, you’ll leave the store happy.

But as a member of Riddler Nation, you can’t help but wonder: How many distinct ways are there for you to make your candy purchase?

To solve this problem I used a summation of combinations. You can think of it in the following two forms:

T(s) = \sum_{n=1}^{s} \binom{n+2}{2} = \sum_{n=1}^{s} (n+1)(n+1)/2

 

Where s is the total number of candies. This evaluates to:

T(100) = 176,850

 

This is the same as summing the first one hundred terms of the Triangle Number Sequence (well, after skipping the first term).

 

New Sultan’s Dowry Problem

Another week, another Riddler. This is a puzzle about maximizing a selection with limited resources:

From Julien Beasley, a new spin on the Sultan’s Dowry Problem, a classic problem of matrimony:

The sultan has asked her vizier to present her with 10 candidates for marriage. The vizier has searched the kingdom for the 10 most desirable partners, but he does not know whom the sultan will prefer. If she saw them all at the same time, she would easily be able to rank them from 1 (the best partner) to 10 (the worst partner). But the vizier can only present the candidates one at a time — very hard to sync everybody’s calendars, even back then — and in a random order. Upon seeing each candidate, the sultan must reject or accept him. If a candidate is rejected, the sultan cannot pick him again. But on seeing each new candidate, she knows exactly where he’d stack up relative to the candidates she has rejected. If she strategizes, what’s the highest rank she can expect her chosen candidate to have on average?

For example, if she simply accepted the first candidate presented to her, his rank could be anywhere from 1 to 10 with equal probability, averaging to 5.5. Surely she can do better…

This was a difficult problem. With each candidate you have more information to make a decision — but wait too long and you don’t get to make a decision.

Here are the acceptance criteria that I suggest using:

[N/A, N/A, N/A, 3, 4, 4, 5, 6, 7, 0]

What does this mean? Start by always letting the first three candidates pass. Then, if the next candidate is better then 3 of the previous candidates accept them. If you don’t, accept the next if they are better than 4 of the previous candidates. Continue like this through the array — always accepting the last candidate if you get there.

Using this method you will have a suitor with an average value of 8.34166

I hope to have an explanation of the math behind why this works later in the week

 

Maze Problem

Another week, another riddler. This is a maze problem where your move distance is constrained but the direction is left open. Here is the problem:

From Tom Hanrahan, a maze you can solve without getting lost in a field of corn:

Number maze. Start from the yellow six in the bottom left corner and finish at the asterisk.

The number in each box tells you how many spaces up, down, left or right you must move. (No diagonal moves, people.) Starting at the yellow six in the bottom left corner, can you make your way to the asterisk?

The answer is  yes. Here is the path:

Capture2.JPG

To get this we work backwards and figure out the squares that lead to the asterisk (and then the squares that lead to the squares that lead to the asterisk)

For example, there is only one square that leads to the asterisk, this blue 2:

move1.gif

 

There is only one square that leads to the blue two, this green 6:

move2.gif

Doing this over and over leads to the following map:

Capture.JPG

Where the blue arrows show the direction that leads to the end. If it has red over it then there is no way to get to that square. Once you have a path that starts from the yellow square you are done.

 

Very fun problem!

 

IMO Windmill Problem

For those of us who play the game of math, recently one challenge has become pretty popular – the IMO 2011 Windmill Problem. It goes something like this:

Let $\mathcal{S}$ be a finite set of at least two points in the plane. Assume that no three points of $\mathcal S$ are collinear. A windmill is a process that starts with a line $\ell$ going through a single point $P \in \mathcal S$. The line rotates clockwise about the pivot $P$ until the first time that the line meets some other point belonging to $\mathcal S$. This point, $Q$, takes over as the new pivot, and the line now rotates clockwise about $Q$, until it next meets a point of $\mathcal S$. This process continues indefinitely. Show that we can choose a point $P$ in $\mathcal S$ and a line $\ell$ going through $P$ such that the resulting windmill uses each point of $\mathcal S$ as a pivot infinitely many times.

The problem and solution can be found here. I didn’t solve it but instead was able to create a rendering of what the process can look like

windmill10.gif

This was a challenge in itself – I was forced to think about how to predict collisions, pivot about points, see if they’d occur clockwise or counterclockwise and of course actually making the rendering

windmill.gif

Of course, if you haven’t seen the video that prompted this check it out by 3Blue1Brown

I attached the code here

Riddler League Baseball

Another week, another riddler. This week’s was a puzzle about baseball:

Riddler League Baseball, also known as the RLB, consists of three teams: the Mississippi Moonwalkers, the Delaware Doubloons and the Tennessee Taters.

Each time a batter for the Moonwalkers comes to the plate, they have a 40 percent chance of getting a walk and a 60 percent chance of striking out. Each batter for the Doubloons, meanwhile, hits a double 20 percent percent of the time, driving in any teammates who are on base, and strikes out the remaining 80 percent of the time. Finally, each batter for the Taters has a 10 percent chance of hitting a home run and a 90 percent chance of striking out.

During the RLB season, each team plays an equal number of games against each opponent. Games are nine innings long and can go into extra innings just like in other baseball leagues. Which of the three teams is most likely to have the best record at the end of the season?

For this I brute forced the problem and ran a season with 200,000 games. The results?

Mississippi Moonwalkers (singles): 106,879 wins
Delaware Doubloons (doubles): 79,189 wins
Tennesse Taters (homers): 114,345 wins

Therefore, I’d choose the Tennessee Taters to win the season

And here is the code:

import random

max_outs = 3
innings = 9
game_num = 100000 #num games to run for each matchup

def batter_up(batting_power,batting_perc,i_bases,i_outs):
    hit = random.random()  scores[1]

#Run games (can be done more efficiently but w/e)

#Singles team:
t1_wins = 0
for i in range(game_num):
    t1_wins += play_game(1,0.4,2,0.2)
    t1_wins += play_game(1,0.4,4,0.1)

print("Single team: ",float(t1_wins))

#Doubles team:
t2_wins = 0
for i in range(game_num):
    t2_wins += play_game(2,0.2,1,0.4)
    t2_wins += play_game(2,0.2,4,0.1)

print("Doubles team: ",float(t2_wins))

#Homers team:
t3_wins = 0
for i in range(game_num):
    t3_wins += play_game(4,0.1,2,0.2)
    t3_wins += play_game(4,0.1,1,0.4)

print("Homers team: ",float(t3_wins))

 

welcome to college football saturday

For the past five years Jon Bois has tweeted “welcome to college football saturday” during college football saturdays.

This tradition ended last week, here are some graphs to commemorate it

ECN2iXpWwAA5l6J.png

Figure 1: When Jon tweets

likes.png

Figure 2: How the public responds

This was done using tweepy to scrape the last 3.2k tweets from Jon