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.006213
```

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
```

```
111846980495107//18014398509481984
```

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))
```

```
7175
```

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?

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

```
0.1281048419095557
```

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?

```
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
```

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
```

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
```

```
0.498872
```

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
```

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?

```
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.920383
```

Number of free drinks you can expect are available:

```
sum(drinks_left) / nsims
```

```
7.034115
```

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
```