FiveThirtyEight Riddler Solutions

Every week, FiveThirtyEight offers up problems related to the things they hold dear: math, logic and probability. Sometimes I try to solve them. This is where you will find my solutions to the Riddler.

Nov 13, 2020 –– Can You Snatch Defeat From The Jaws Of Victory?

Riddler Express

This week's Riddler Express asks:

Last Sunday we lost Alex Trebek, a giant in the world of game shows and trivia. The show he hosted over the course of four decades — Jeopardy! — has previously appeared in this column. Today, it makes a return.

You’re playing the (single) Jeopardy! Round, and your opponents are simply no match for you. You choose first and never relinquish control, working your way horizontally across the board by first selecting all six $200 clues, then all six $400 clues, and so on, until you finally select all the $1,000 clues. You respond to each clue correctly before either of your opponents can.

One randomly selected clue is a Daily Double. Rather than award you the prize money associated with that clue, it instead allows you to double your current winnings or wager up to $1,000 should you have less than that. Being the aggressive player you are, you always bet the most you can. (In reality, the Daily Double is more likely to appear in certain locations on the board than others, but for this problem assume it has an equal chance of appearing anywhere on the board.)

How much money do you expect to win during the Jeopardy! round?

Extra credit: Suppose you change your strategy. Instead of working your way horizontally across the board, you select random clues from anywhere on the board, one at a time. Now how much money do you expect to win during the Jeopardy! round?

Solution

Since we are assuming that the Daily Double is equally likely to appear on every tile, we can calculate the winnings for each possible scenario and average them.

If the Daily Double is anywhere in the first row, the winnings would be $18,000 plus $800, since in the Daily Double, if you have less than $1,000 at the time you can bet up to that amount. If the Daily Double is on the first $400 clue, you can wager up to $1,200 (also $800 more than the value of the clue itself), for a total winning of $18,800. If it occurs on the second $400 clue, you can bet up to $1,600 for a total prize of $19,200. Calculate this for every possible outcome, and you arrive at the expected winnings of $23,800.

We can test this empirically by simulating the game. I wrote some code to simulate 10,000,000 times, and got... $23,799.29 on average. Pretty close!


# python
import random

def estExpWinnings():
  results = []
  for j in range(10000000):
    values = [200] * 6 + [400] * 6 + [600] * 6 + [800] * 6 + [1000] * 6
    dd = random.sample(list(range(30)), 1)[0]
    winnings = []
    for i in range(30):
      winningsSoFar = sum(winnings)
      if i == dd:
        if winningsSoFar <= 1000:
	  winnings.append(1000)
	else:
	  winnings.append(winningsSoFar)
      else:
        winnings.append(values[i])
    results.append(sum(winnings))
  return sum(results) / len(results)

estExpWinnings()
          		

For the extra credit, in some ways this is actually an easier problem to solve. When choosing questions in a random order, the expected value of each question flattens down to $600 exactly. So, to determine the expected winnings, we just have to conduct the same exercise as above, but where each question is worth $600 in expectation. On average, we get $26,146.67.

Again, we'll test our calculation against millions of simulated games:


# python
def estExpHuntWinnings():
  results = []
  for j in range(10000000):
    values = [200] * 6 + [400] * 6 + [600] * 6 + [800] * 6 + [1000] * 6
    dd = random.sample(list(range(30)), 1)[0]
    winnings = []
    playOrder = random.sample(list(range(30)), 30)
      for i in playOrder:
        winningsSoFar = sum(winnings)
	if i == dd:
	  if winningsSoFar <= 1000:
	    winnings.append(1000)
	  else:
	    winnings.append(winningsSoFar)
	else:
	  winnings.append(values[i])
    results.append(sum(winnings))
  return sum(results) / len(results)

estExpHuntWinnings()
          	  

And again, we get a value very close to our calculation. This time: $26,147.36

Finally, as an extension, I wonder what the expected winnings would be if you were so well-studied that you knew what the Daily Double distribution looked like, and strategized accordingly. In this case, the strategic player would aim to hit the Daily Double last, as to maximize its effect. Like before, finding the (weighted) average of the 30 possible outcomes gives us the expected winnings, given that the player will choose clues in a predetermined order. In this case, the expected winnings is $28,049.94. And finally (really this time), we can check our calculation by simulating.


# python
def estExpStratWinnings():
  results = []
  for j in range(10000000):
    values = [200] * 6 + [400] * 6 + [600] * 6 + [800] * 6 + [1000] * 6
    dailyDoubleDist = [
      2, 0, 3, 1, 2, 0, 286, 131, 202, 173, 214, 124, 703, 352, 581, 557,
      533, 358, 866, 508, 795, 719, 763, 518, 602, 281, 497, 530, 448, 355
      ]
    dd = random.choices(list(range(30)), weights = dailyDoubleDist, k = 1)
    playOrder = list(np.argsort(np.array(dailyDoubleDist)))
    winnings = []
    for i in playOrder:
      winningsSoFar = sum(winnings)
      if i == dd:
        if winningsSoFar <= 1000:
	  winnings.append(1000)
	else:
	  winnings.append(winningsSoFar)
      else:
        winnings.append(values[i])
    results.append(sum(winnings))
  return sum(results) / len(results)

estExpStratWinnings()
          	  

And, of course, we get a very close approximation: $28,048.76.

Riddler Classic

This week's Riddler Classic asks:

From Angela Zhou comes a bad football puzzle. The puzzle’s great, but the football is bad:

Football season is in full swing, and with it have been some incredible blown leads. The Atlanta Falcons know a few things about this, not to mention a certain Super Bowl from a few years back. Inspired by these improbabilities, Angela wondered just how likely one blown lead truly is.

The Georgia Birds and the Michigan Felines play a game where they flip a fair coin 101 times. In the end, if heads comes up at least 51 times, the Birds win; but if tails comes up at least 51 times, the Felines win.

What’s the probability that the Birds have at least a 99 percent chance of winning at some point during the game — meaning their probability of victory is 99 percent or greater given the flips that remain — and then proceed to lose?

Extra credit: Instead of 101 total flips, suppose there are many, many more (i.e., consider the limit as the number of flips goes to infinity). Again, the Birds win if heads comes up at least half the time. Now what’s the probability that the Birds have a win probability of at least 99 percent at some point and then proceed to lose?

Solution

I ran out of time on this one, but I was able to simulate it a bunch of (10,0000,000) times, and it seemed that 0.21% of the time, the Birds would reach a 99% chance of winning and then blow it.


# r
calcPOfWinning <- function(n, h, N){
  # n is the number of throws so far
  # h is the number of heads so far
  # N is the total number of throws
  # H is the heads needed to win
  H <- ceiling((N + 1) / 2)

  # R is the heads needed left to win
  R <- H - h
  # r is the remaining throws
  r <- N - n
  q <- 0
  if(h > n){
    q <- 0
  } else if(R > r){
    q <- 0
  } else {
    for(i in R:r){
      q <- q + (choose(r, i) / 2 ^ r)
    }
  }
  q
}

playGame <- function(N){
  H <- ceiling((N + 1) / 2)
  flips <- sample(c(0,1), N, replace = T)
  n <- 0
  h <- 0
  p <- 0
  for(f in flips){
    q <- calcPOfWinning(n, h, N)
    if(q > p){
      p <- q
    }
    h <- h + f
    n <- n + 1
  }
  r <- p > .99 & h < H
  r
}

playGameRepeatedly <- function(N){
  x <- replicate(10000000, playGame(N))
  y <- mean(x)
  y
}

playGameRepeatedly(101)
			

Oct 30, 2020 –– Beware the Hot Pumpkin

Riddler Classic

This week's Riddler Classic asks:

From Ricky Jacobson comes a party game that’s just in time for Halloween:

Instead of playing hot potato, you and 60 of your closest friends decide to play a socially distanced game of hot pumpkin.

Before the game starts, you all sit in a circle and agree on a positive integer N. Once the number has been chosen, you (the leader of the group) start the game by counting “1” and passing the pumpkin to the person sitting directly to your left. She then declares “2” and passes the pumpkin one space to her left. This continues with each player saying the next number in the sequence, wrapping around the circle as many times as necessary, until the group has collectively counted up to N. At that point, the player who counted “N” is eliminated, and the player directly to his or her left starts the next round, again proceeding to the same value of N. The game continues until just one player remains, who is declared the victor.

In the game’s first round, the player 18 spaces to your left is the first to be eliminated. Ricky, the next player in the sequence, begins the next round. The second round sees the elimination of the player 31 spaces to Ricky’s left. Zach begins the third round, only to find himself eliminated in a cruel twist of fate. (Woe is Zach.)

What was the smallest value of N the group could have used for this game?

Extra credit: Suppose the players were numbered from 1 to 61, with you as Player No. 1, the player to your left as Player No. 2 and so on. Which player won the game?

Extra extra credit: What’s the smallest N that would have made you the winner?

Solution

To start, we know that N must be 19, or 80, or 141... or in mathematical notation N mod 61 = 19. Next, and along the same lines, N mod 60 = 32. Finally, N mod 59 = 1. So, to find the answer to the question, we can simply loop through the integers until we find one that meets all these criteria.


# python
n = 1
while(True):
  if n % 61 == 19 and n % 60 == 32 and n % 59 == 1:
    print(n)
    break
  n += 1
            

We get N = 136,232.

Now we'll try the extra credit. Let's just simulate the rest of the game.


# python
def hotPumpkin(n):
  seats = list(range(1,62))
  while(len(seats) > 1):
    i = n % len(seats) - 1
    seats = seats[i:] + seats[:i]
    seats.pop(0)
  return seats[0]

hotPumpkin(136232)
            

We find that the winner of the game is person 58.

Finally, we'll find the minimum value of N that results in player 1 (you) winning the game. Again, we'll loop through integers until we find one.


# python
n = 1
while(True):
  if hotPumpkin(n) == 1:
    print(n)
    break
  n += 1
            

And we get 140.

Oct 2, 2020 –– Can You Eat All The Chocolates?

Riddler Classic

This week's Riddler Classic asks:

From mathematician (and author of Basic Probability: What Every Math Student Should Know) Henk Tijms comes a choice matter of chance and chocolate:

I have 10 chocolates in a bag: Two are milk chocolate, while the other eight are dark chocolate. One at a time, I randomly pull chocolates from the bag and eat them — that is, until I pick a chocolate of the other kind. When I get to the other type of chocolate, I put it back in the bag and start drawing again with the remaining chocolates. I keep going until I have eaten all 10 chocolates.

For example, if I first pull out a dark chocolate, I will eat it. (I’ll always eat the first chocolate I pull out.) If I pull out a second dark chocolate, I will eat that as well. If the third one is milk chocolate, I will not eat it (yet), and instead place it back in the bag. Then I will start again, eating the first chocolate I pull out.

What are the chances that the last chocolate I eat is milk chocolate?

Solution

Let's write a quick script to simulate the game a bunch of times.


# python
import random

def eatAllTheChocolates():
  bagOfChocolates = ['d', 'd', 'd', 'd', 'd', 'd', 'd', 'd', 'm', 'm']
  lastChocolate = ''
  while(len(bagOfChocolates) > 1):
    if(lastChocolate == ''):
      chocolate = random.sample(bagOfChocolates, 1)[0]
      bagOfChocolates.remove(chocolate)
      lastChocolate = chocolate
    else:
      chocolate = random.sample(bagOfChocolates, 1)[0]
      if chocolate == lastChocolate:
        bagOfChocolates.remove(chocolate)
      else:
        lastChocolate = ''
  return bagOfChocolates[0]

def eatAllTheChocolatesOverAndOverAndOver():
  results = []
  for i in range(10000000):
    results.append(eatAllTheChocolates())
  return results.count('m') / len(results)

eatAllTheChocolatesOverandOverAndOver()
						

After 10 million simulations, we find that the last chocolate will be milk chocolate half of the time.

Jan 29, 2016 –– Who Will Win The Politicians’ Secret Vote?

Riddler

This week's Riddler asks:

Now, here’s this week’s Riddler, which has quite the economic genealogy. It comes to us from Laura Feiveson, an economist at the Federal Reserve’s Board of Governors; it came to her from Yale economist Barry Nalebuff; and it came to him from Nobel-winning economist Thomas Schelling.

Suppose that five politicians, disgusted with the current two-party system, come together to choose a third-party candidate to run in the 2016 presidential election. The politicians’ names are Anders (A), Blinton (B), Cubio (C), Drump (D) and Eruz (E). Not wanting to spend all their time campaigning in Iowa and New Hampshire in winter, they decide instead to pick which of them will be the candidate at a secret meeting with just the five of them. The voting procedure is as follows: They will first hold a vote of A versus B. (The five politicians are the only voters.) The winner of that vote will then be paired against C. That winner will be paired against D, and finally that winner will be paired against E. They will declare the winner of that last matchup to be their candidate.

Each of A, B, C, D and E wants to be the presidential candidate themselves, but also has clear preferences over the others. Furthermore, the politicians’ preferences are common knowledge. Their preferences are as follows (“X > Y” means Candidate X is preferred to Candidate Y):

Candidate A: A > B > C > D > E

Candidate B: B > A > E > D > C

Candidate C: C > D > A > E > B

Candidate D: D > B > A > E > C

Candidate E: E > D > B > C > A

All of the politicians are forward-looking and vote strategically.

Question 1: Who will be chosen as the presidential candidate?

Now assume that A has the flu and is forced to miss the voting meeting. He is allowed to transfer his vote to someone else, but he can’t make that other person commit to vote against her own self-interest.

Question 2: To whom should he transfer his vote, given his candidate preference outlined above (A > B > C > D > E)?

Question 3: Who will win the candidacy now?

Question 4: A month before the meeting, Candidate A must decide whether or not to get the flu vaccine. Should he get it?

Solution

To solve this problem, we will have to figure out what the decision tree will look like. We know that either A or B will win the first ballot. Assuming A wins, then either A or C will can win the second ballot. This logic must be carried out until all contingencies are mapped. Then we need to figure out how each conceivable head-to-head matchup will be voted on. Finally, we can use backward induction to figure out how each sequential vote will go, and who the ultimate winner will be.

Question 1: Using regular backward induction, with all five candidates voting, we find that candidate D will win the election.

Question 2: To determine whom A should choose as their proxy, we can figure out how the puzzle will be solved with B's vote double counted, and C's, D's, and E's. Then, we'll look at the resulting outcome of the vote to determine which proxy best suits A's interests. We find, through this process, that E is the best proxy for A to choose.

Question 3: When E is chosen as A's proxy, A actually wins the election. Weird, right?

Question 4: Finally, should A choose to take a flu shot? Paradoxically, no. A is better of getting the flu and then being elected than staying healthy and D winning the election.

You can explore the different outcomes through this spreadsheet.

Jan 15, 2016 –– Will the Neurotic Basketball Player Make His Next Free Throw?

Riddler

This week's Riddler asks:

Now, here’s this week’s Riddler, which comes to us from Mike Donner, an engineer from Virginia Beach, Virginia:

A basketball player is in the gym practicing free throws. He makes his first shot, then misses his second. This player tends to get inside his own head a little bit, so this isn’t good news. Specifically, the probability he hits any subsequent shot is equal to the overall percentage of shots that he’s made thus far. (His neuroses are very exacting.) His coach, who knows his psychological tendency and saw the first two shots, leaves the gym and doesn’t see the next 96 shots. The coach returns, and sees the player make shot No. 99. What is the probability, from the coach’s point of view, that he makes shot No. 100?

Solution

We will solve by brute force: simulation!


# r
library(pbapply)

shootFreethrows <- function(){
  shots <- c(1, 0)
  for(i in 3:100){
    p <- mean(shots)
    shot <- sample(x = c(1, 0), size = 1, prob = c(p, 1 - p))
    shots <- c(shots, shot)
  }
  if(shots[99] == 1){
    return(shots[100])
  }
}

shootFreethrowsRepeatedly <- function(){
  results <- unlist(pbreplicate(10000000, shootFreethrows()))
  return(mean(results))
}

shootFreethrowsRepeatedly()
	          

After many, many (10,000,000) simulated games, we find that he makes his 100th freethrow 2/3rds of the time that he makes his 99th.

Dec 22, 2015 –– How Long Will Your Smartphone Distract You From Family Dinner?

Riddler

This week's Riddler asks:

Now, here’s this week’s Riddler, which comes to us from Olivia Walch, a mathematics Ph.D. student and cartoonist:

You’ve just finished unwrapping your holiday presents. You and your sister got brand-new smartphones, opening them at the same moment. You immediately both start doing important tasks on the Internet, and each task you do takes one to five minutes. (All tasks take exactly one, two, three, four or five minutes, with an equal probability of each). After each task, you have a brief moment of clarity. During these, you remember that you and your sister are supposed to join the rest of the family for dinner and that you promised each other you’d arrive together. You ask if your sister is ready to eat, but if she is still in the middle of a task, she asks for time to finish it. In that case, you now have time to kill, so you start a new task (again, it will take one, two, three, four or five minutes, exactly, with an equal probability of each). If she asks you if it’s time for dinner while you’re still busy, you ask for time to finish up and she starts a new task and so on. From the moment you first open your gifts, how long on average does it take for both of you to be between tasks at the same time so you can finally eat? (You can assume the “moments of clarity” are so brief as to take no measurable time at all.)

Solution

When we simulate this situation, as I did 10,000,000 times, you get 9 minutes on average.


# python
import random

def waitForDinner():
    a = random.sample((1,2,3,4,5), 1)[0]
    b = random.sample((1,2,3,4,5), 1)[0]
    while(a != b):
        if(a > b):
            b += random.sample((1,2,3,4,5), 1)[0]
        else:
            a += random.sample((1,2,3,4,5), 1)[0]
    return a

def waitForDinnerRepeatedly():
    waits = []
    for i in range(10000000):
        waits.append(waitForDinner())
    return sum(waits) / len(waits)

waitForDinnerRepeatedly()
	          
email github.com/alexvornsand