Riddles from 538’s The Riddler solved with programming
In this document I solve riddles rom 538’s The Riddler, using programming, mainly in Julia. Updated continuously.
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);
From the Riddler book
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?
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.006213We 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
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.
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))
7175The 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?
count(a * b * c % 100 == 0 for a in 0:99, b in 0:99, c in 0:99) / 99^3
0.1281048419095557In 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?
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.29166This 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
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?
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
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//1015Lucky 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?
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.9204330000000001Number of free drinks you can expect are available:
sum(drinks_left) / nsims
7.034844Using 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.9204107626128212Number of free drinks you can expect are available:
sum(a[i, dim] * (dim - i) for i in 2:dim-1)
7.038512976105056You 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?
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 |
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