The Riddler

Riddles from 538’s The Riddler solved with programming

Jonatan Pallesen https://jsmp.dk
05-22-2019

Table of Contents


In this document I solve riddles rom 538’s The Riddler, using programming, mainly in Julia. Updated continuously.

imports

using Random
using Statistics
using Memoize
using Base.Iterators
using Combinatorics
using Distributions

repeat(f::Function, n::Integer) = [f() for _ in 1:n]

nsims = 10^6
simprob(f) = sum(repeat(f, nsims)) / nsims

function ifirst(cond, itr)
    for elem in itr
        cond(elem) && return elem
    end
end

Random.seed!(0);


1. Knight on an infinite chessboard

From the Riddler book

Problem

Suppose that a knight makes a “random walk” on an infinite chessboard. Specifically, every turn the knight follows standard chess rules and moves to one of its eight accessible squares, each with probability 1/8.

What is the probability that after the twentieth move the knight is back on its starting square?

Simulation solution

The knight moves two tiles in any direction, and one tile in a direction perpendicular to that.


move() = shuffle(1:2) .* rand([-1, 1], 2)
is_back_to_start() = sum(repeat(move, 20)) == [0,0]

simprob(is_back_to_start)

0.006213

Exact solution

We recursively go through all moves the night can do, and count all the ones that return to the starting spot after 20 moves.


@memoize function knight_returns(moves_left, i, j)
    moves_left == 0 && return i == j == 0
    n_return = 0
    for(x,y) in product([(1,2),(2,1)], product([-1,1], [-1, 1]))
        n_return += knight_returns(moves_left - 1, i + x[1]*y[1], j + x[2]*y[2])
    end
    n_return
end

knight_returns(20,0,0) // 8^20


2. How large is Santa’s playlist?

Dec 21 2018

Problem

In Santa’s workshop, elves make toys during a shift each day. On the overhead radio, Christmas music plays, with a program randomly selecting songs from a large playlist.

During any given shift, the elves hear 100 songs. A cranky elf named Cranky has taken to throwing snowballs at everyone if he hears the same song twice. This has happened during about half of the shifts. One day, a mathematically inclined elf named Mathy tires of Cranky’s sodden outbursts. So Mathy decides to use what he knows to figure out how large Santa’s playlist actually is.

Solution

The risk of having a repeat song is the same as 1 minus the probability of no repeat songs. To get no repeat songs, the second played song needs to not be a repeat of the first (chance = 1/n), and the third song needs to not be a repeat of any of the two first ones (chance = 2/n), etc. So we find the first n so that this risk is just below 0.5.

(Note: this is the Birthday problem)


risk_of_repeated_song(n) = 1 - prod((n - i) / n for i in 1:99)

ifirst(n -> risk_of_repeated_song(n) < 0.5, countfrom(101))

7175


3. Numbers divisible by 100

Feb. 8, 2019

Problem

The song “Seasons of Love” from the musical “Rent” states that a year has 525,600 minutes. And, indeed, 365×24×60 = 525,600.

This, naturally, raises an abstract mathematical question: Given any three random integers — X, Y and Z — what are the chances that their product is divisible by 100?

Solution


count(a * b * c % 100 == 0 for a in 0:99, b in 0:99, c in 0:99) / 99^3

0.1281048419095557


4. Collecting cigarette cards

Mar 1, 2019

Problem

In the video game “Red Dead Redemption 2,” there is a side quest where the main character is supposed to collect 12 sets of cigarette cards, each consisting of 12 unique cards.

Some cards can be found lying around in the open world, but the easiest way to collect the cards is to buy cigarettes at the store and collect the single random card included in each pack. Suppose Arthur is too lazy to look for cards in the open world and tries to complete the set only by buying packs at the store.

At $5 a pack, how much money do we expect Arthur to spend to complete all 12 sets?

Simulation solution


function get_price()
    cards, dollars = Set(), 0
    while length(cards) < 144
        push!(cards, rand(1:144))
        dollars += 5
    end
    dollars
end

mean(repeat(get_price, nsims))

3995.29166

Exact solution

This is the Coupon collector’s problem. If you are only lacking one card out of 144, it will take an average of 144 packs to get it; if you are lacking two cards, it will take an average of 144 / 2 packs, and so on. So we sum all these averages.


sum(144 // n for n in 1:144) * 5

5. Ticket to Ride

Mar 29, 2019

Problem

You are playing your first ever game of “Ticket to Ride,” a board game in which players compete to lay down railroad while getting so competitive they risk ruining their marriages. At the start of the game, you are randomly dealt a set of three Destination Tickets out of a deck of 30 different tickets. Each reveals the two terminals you must connect with a railroad to receive points. During the game, you eventually pick up another set of three Destination Tickets, so you have now seen six of the 30 tickets in the game.

Later, because you enjoyed it so much, you and your friends play a second game. The ticket cards are all returned and reshuffled. Again, you are dealt a set of three tickets to begin play. Which is more likely: that you had seen at least one of these three tickets before, or that they were all new to you?

Simulation solution


seen_one_before = []
tickets = 1:30

for i in 1:nsims
    first_tickets = Set(sample(tickets, 6, replace=false))
    second_tickets = Set(sample(tickets, 3, replace=false))
    push!(seen_one_before, length(intersect(first_tickets, second_tickets)) == 0)
end

sum(seen_one_before) / nsims

Exact solution

6 out of 30 tickets have been picked before. The first one therefore has a 24/30 chance to not have been picked. The second pick is from the pile without the first pick, and thus has a 23/29 chance of not having been picked in the first round. 22/28 for the last pick.


24//30 * 23//29 * 22//28

506//1015


6. Gift cards

5 Apr, 2019

Problem

Lucky you! You’ve won two gift cards, each loaded with 50 free drinks from your favorite coffee shop, Riddler Caffei-Nation. The cards look identical, and because you’re not one for record-keeping, you randomly pick one of the cards to pay with each time you get a drink. One day, the clerk tells you that he can’t accept the card you presented to him because it doesn’t have any drink credits left on it.

What is the probability that the other card still has free drinks on it? How many free drinks can you expect are still available?

Simulation solution


drinks_left = []
for i in 1:nsims
    cards = [50, 50]
    while minimum(cards) >= 0
        cards[rand([1, 2])] -= 1
    end
    push!(drinks_left, maximum(cards))
end


Probability other card has drinks:


1 - sum(drinks_left .== 0) / nsims

0.9204330000000001


Number of free drinks you can expect are available:


sum(drinks_left) / nsims

7.034844

Exact solution

Using dynamic programming.


ntickets = 50
dim = ntickets + 2
a = fill(0.0, dim, dim)
a[2, 2] = 1

for diag in 5:2*dim, i in 2:dim, j in 2:dim
    if i + j == diag
        a[i, j] = a[i-1, j] / 2 + a[j-1, i] / 2
    end
end


Probability other card has drinks:


1 - a[dim, dim]

0.9204107626128212


Number of free drinks you can expect are available:


sum(a[i, dim] * (dim - i) for i in 2:dim-1)

7.038512976105056

7. Tour de FiveThirtyEight?

The Riddler, Dec 21 2018

Problem

You are the coach for Team Riddler at the Tour de FiveThirtyEight, where there are 20 teams (including yours). Your objective is to win the Team Time Trial race, which has the following rules:

Each team rides as a group throughout the course at some fixed pace, specified by that team’s coach. Teams that can’t maintain their pace are said to have “cracked,” and don’t finish the course. The team that finishes the course with the fastest pace is declared the winner. Teams ride the course one at a time. After each team completes its attempt, the next team quickly consults with its coach (who assigns a pace) and then begins its ride. Coaches are aware of the results of all previous teams when choosing their own team’s pace. Assume that all teams are of equal ability: At any given pace, they have the exact same probability of cracking, and the faster the pace, the greater the probability of cracking. Teams’ chances of cracking are independent, and each team’s coach knows exactly what a team’s chances of cracking are for each pace.

Team Riddler is the first team to attempt the course. To maximize your chances of winning, what’s the probability that your team will finish the course? What’s the probability you’ll ultimately win?

Extra Credit: If Team Riddler is the last team to attempt the course (rather than the first), what are its chances of victory?

Programming solution

I assume that you can beat the preceeding team by an infinitisimally small amount, and that coaches can set a pace at exactly this level.

Then the correct pace is the one such that chance of completing x chance of no one else completing at this pace is maximized. Instead of measuring the pace in miles / hour we measure it in chance of completing, since those are equivalent, just on different scales.

The optimize function finds both the optimal pace, and the resulting chance of winning overall at this pace.


m <- optimize(function(pace) pace * (1 - pace)^19, interval=c(0, 1), maximum=T)

tribble(~condition, ~chance,
        "Finishing if going first", m$maximum,
        "Winning if going first", m$objective)
condition chance
Finishing if going first 0.05
Winning if going first 0.0189


If the team before you failed, you can set your pace slightly lower, since there are fewer chances to beat your time. The table below shows the optimal pace depending on your starting position.


get_chance_finishing <- function(n){
  optimize(function(pace) pace * (1 - pace)^(20-n), interval=c(0, 1), maximum=T)$maximum
}

df <-  tibble(starting_pos = 1:20) %>% rap(pace = numeric() ~get_chance_finishing(starting_pos))

df
starting_pos pace
1 0.05
2 0.0526
3 0.0555
4 0.0588
5 0.0625
6 0.0667
7 0.0714
8 0.0769
9 0.0833
10 0.0909
11 0.1
12 0.111
13 0.125
14 0.143
15 0.167
16 0.2
17 0.25
18 0.333
19 0.5
20 1


If we assume all coaches make the optimal choice, the pace to beat will be the pace of the first team to complete. (Since we assume that this pace will be beat by an infinitisimally small amount by subsequent teams.) The chance that a team is the first one completed, is the chance that no previous team completed and that this team did complete.


get_chance <-  function(s){
  df %>% filter(starting_pos < s) %>% 
    mutate(one_minus_pace = 1 - pace) %>% 
    pull(one_minus_pace) %>% 
    prod()
}

df %<>% rap(chance_no_previous_team_completed = numeric() ~get_chance(starting_pos)) %>% 
  mutate(chance_pace_is_best = pace * chance_no_previous_team_completed)

df
starting_pos pace chance_no_previous_team_completed chance_pace_is_best
1 0.05 1 0.05
2 0.0526 0.95 0.05
3 0.0555 0.9 0.05
4 0.0588 0.85 0.05
5 0.0625 0.8 0.05
6 0.0667 0.75 0.05
7 0.0714 0.7 0.05
8 0.0769 0.65 0.05
9 0.0833 0.6 0.05
10 0.0909 0.55 0.05
11 0.1 0.5 0.05
12 0.111 0.45 0.05
13 0.125 0.4 0.05
14 0.143 0.35 0.05
15 0.167 0.3 0.05
16 0.2 0.25 0.05
17 0.25 0.2 0.05
18 0.333 0.15 0.05
19 0.5 0.1 0.05
20 1 0.05 0.05

We can calculate the chance that the last team wins by taking the chance that starting_pos 1 has the best pace multiplied by the chance of beating this pace, plus the chance that starting_pos 2 has the best pace multiplied by the chance of beating this pace, and so on, adding them all up.


df %>% mutate(chance = pace * chance_pace_is_best) %>% 
  summarise(chance = sum(chance))
chance
0.17989

Exact solution

From the tables above we can see that the chance for a certain team to set the winning pace level is equal for all the teams, 1/n And the pace that will be set is 1 / (n -s +1) where s is the starting position.

So we can calculate the exact solution by summing up the product of these for all s.


sum((1 // (20-i + 1)) * 1//20 for i in 1:20)

11167027//62078016