Sniff out the spies

This interesting problem appeared on the Riddler blog. Here it goes:

There are N agents and K of them are spies. Your job is to identify all the spies. You can send a given number of agents to a “retreat” on a remote island. If all K spies are present at the retreat, they will meet to strategize. If even one spy is missing, this spy meeting will not take place. The only information you get from a retreat is whether or not the spy meeting happened. You can send as many agents as you like to the retreat, and the retreat can happen as many times as needed. You know the values of N and K.

What’s the minimum number of retreats needed to guarantee you can identify all K spies? If each retreat costs \$1,000 per person, what is the total cost to identify all K spies?

To begin with, let’s assume you know that N = 1,024 and K = 17.

Here is my solution for $K=1$:
[Show Solution]

And here is a partial solution for $K \gt 1$:
[Show Solution]

Paths to work

This Riddler puzzle is a classic problem: how many lattice paths connect two points on a grid? Here is a paraphrased version of the problem.

The streets of Riddler City are laid out in a perfect grid. You walk to work each morning and back home each evening. Restless and inquisitive mathematician that you are, you prefer to walk a different path along the streets each time. How many different paths are there? (Assume you don’t take paths that are longer than required). Your home is M blocks west and N blocks south of the office.

Here is my solution:
[Show Solution]

Finding the doctored coin

This Riddler puzzle is about repeatedly flipping coins!

On the table in front of you are two coins. They look and feel identical, but you know one of them has been doctored. The fair coin comes up heads half the time while the doctored coin comes up heads 60 percent of the time. How many flips — you must flip both coins at once, one with each hand — would you need to give yourself a 95 percent chance of correctly identifying the doctored coin?

Extra credit: What if, instead of 60 percent, the doctored coin came up heads some P percent of the time? How does that affect the speed with which you can correctly detect it?

Here is my solution.
[Show Solution]

The lucky derby

In the spirit of the Kentucky Derby, this Riddler puzzle is about a peculiar type of horse race.

The bugle sounds, and 20 horses make their way to the starting gate for the first annual Lucky Derby. These horses, all trained at the mysterious Riddler Stables, are special. Each second, every Riddler-trained horse takes one step. Each step is exactly one meter long. But what these horses exhibit in precision, they lack in sense of direction. Most of the time, their steps are forward (toward the finish line) but the rest of the time they are backward (away from the finish line). As an avid fan of the Lucky Derby, you’ve done exhaustive research on these 20 competitors. You know that Horse One goes forward 52 percent of the time, Horse Two 54 percent of the time, Horse Three 56 percent, and so on, up to the favorite filly, Horse Twenty, who steps forward 90 percent of the time. The horses’ steps are taken independently of one another, and the finish line is 200 meters from the starting gate.

Handicap this race and place your bets! In other words, what are the odds (a percentage is fine) that each horse wins?

Here is my full derivation (long!):
[Show Solution]

For the tl;dr, the answer is:
[Show Solution]

Pick a card!

This Riddler puzzle is about a card game where the goal is to find the largest card.

From a shuffled deck of 100 cards that are numbered 1 to 100, you are dealt 10 cards face down. You turn the cards over one by one. After each card, you must decide whether to end the game. If you end the game on the highest card in the hand you were dealt, you win; otherwise, you lose.

What is the strategy that optimizes your chances of winning? How does the strategy change as the sizes of the deck and the hand are changed?

Here is my solution:
[Show Solution]

Lucky spins in roulette

Roulette is a game where the dealer spins a numbered wheel containing a marble. Once the wheel settles, the marble lands on exactly one (winning) number. A standard American roulette wheel has 38 numbers on it. Players may place bets on a particular number, a color (red or black), or a particular quadrant of the wheel.

I was recently in Las Vegas for a conference, and I noticed that the roulette tables in the conference hotel were equipped with screens that display real-time statistics! A computer keeps track of the winning numbers for the past 300 spins and shows how frequently each number was a winner (see photo on the right). The two “elite numbers” were 12 and 27 (each occurred 13 times in the past 300 games) and the “poor performer” was 0, which only occurred 2 times.

Even if the roulette wheel is equally likely to land on each number, there will be natural fluctuations. Some numbers will obviously win more frequently than others in any finite number of spins. But what sorts of deviations can we expect? In the picture above, the spread between most frequent winner and least frequent winner was 13 to 2 over the course of 300 games. Is this normal? In other words, how big would the spread have to be before you suspected that the roulette wheel was rigged and was favoring some numbers over others? Let’s find out!

Results via simulation

Let’s suppose the wheel has $n$ different numbers on it, which we label $\{1,2,\dots,n\}$, and we spin it $m$ times when we aggregate our statistics. Note that in the actual roulette game, $n=38$ and $m=300$. If the game is fair, then each number is equally likely to occur and the spins are mutually independent. In other words, rolling a 4 on your first spin doesn’t make you more or less likely to roll a 4 or any other number on subsequent spins.

This sort of game is straightforward to simulate in Matlab. I wrote code that plays 300 games, counts how many times the most and least frequent numbers occur, and then repeats the entire process a large number of times. Then, I plotted a histogram showing what proportion of the time the most frequent number occurred 10 times, 11 times, etc. This is known as the empirical distribution. Here are the results of the simulation (aggregated over 100 million trials).

As we can see, a spread from 2 to 13 is right around what we expect! Of course, outliers are still possible. For example, it’s possible for the luckiest number to win 30 times out of 300 spins, but this only happened twice out of 100,000,000 simulated runs.

Analytical results

The roulette wheel lands on one of the $n$ numbers with equal probability. We then perform $m$ spins and count how many times each number occurs. If we place the counts in the vector $(x_1,\dots,x_n)$, where $x_1+\dots+x_n=m$, then this vector follows a multinomial distribution. The probability mass function is therefore:
\[
p(x_1,\dots,x_n) = {m \choose {x_1,\dots,x_m}} \frac{1}{n^m}
\]The bracketed term is called a multinomial coefficient and it counts the number of ways we can spin a “$1$” $x_1$ times, a “$2$” $x_2$ times, and so on. This also corresponds to the number of ways of depositing $m$ distinct objects into $n$ distinct bins, with $x_1$ objects in the first bin, $x_2$ objects in the second bin, and so on. It’s also equal to $\frac{m!}{x_1! \cdot x_2!\cdots x_n!}$. Meanwhile, $n^m$ is the number of different ways we can spin the roulette wheel $m$ times.

The probability that the most frequent spin occurs at most $k$ times is:
\[
F_\text{max}(k) = \sum_{\substack{ x_1+\dots+x_n=m\\x_i\,\le\,k}} p(x_1,\dots,x_n)
\]In other words, we must sum over all tuples $(x_1,\dots,x_n)$ of nonnegative integers that sum to $m$, that are each no greater than $k$. This is the cumulative distribution function, and in order to obtain the probability that the most frequent spin occurs exactly $k$ times (the probability mass function), we compute the difference:
\[
q_\text{max}(k) = F_\text{max}(k)-F_\text{max}(k-1)
\]A similar expression can be obtained for the probability that the least frequent spin occurs exactly $k$ times. These sums are impractical to compute because they have an astronomical number of terms. We must resort to approximation!

In our multinomial distribution, each $x_i$ has mean $\frac{m}{n}$ and variance $\frac{m}{n}\left(1-\frac{1}{n}\right)$. We will make the approximation that the $x_i$ are independent binomial random variables. Of course the $x_i$ are not truly independent since they must sum to $m$, but $n$ is large enough that this is a good approximation. We can therefore compute the distribution of the maximum by using the cumulative distribution:
\begin{align}
F_\text{max}(k) &= \mathbb{P}(x_1\le k,\dots,x_n\le k) \\
&\approx \prod_{i=1}^n \mathbb{P}(x_i \le k) \\
&= \left( \sum_{j=0}^k { m \choose j } \left( \frac{1}{n} \right)^j \left( 1-\frac{1}{n}\right)^{m-j} \right)^n
\end{align}This sum is far more manageable and we can compute it exactly without any difficulty. Once we have this cumulative distribution, we compute our approximation to $q_\text{max}(k)$ as before, by taking the difference of successive cumulative sums. The result is shown in the plot below.

As we can see, this plot is very close to the one we obtained via simulation. So the binomial approximation is quite good! It’s tempting to approximate the binomial distribution even further as a normal distribution, but it turns out this approximation isn’t very good. A rule of thumb to see whether we should use a normal distribution is to check whether 3 standard deviations of the mean keeps us within the range of admissible values, i.e. $\{0,1,\dots,m\}$. This amounts to checking, in our case, that $m > 9(n-1)$. Since $n=38$ and $m=300$, the inequality doesn’t hold because the right-hand side equals $333$.

Conclusion

Seeing one number occur 13 times while another only occurs 2 times in the past 300 spins isn’t abnormal at all. In fact, it’s very much what you should expect! So don’t think of the real-time statistics as a means to help you predict “lucky” or “unlucky” numbers… think of it as a way to double-check that the roulette wheel is unbiased!

Impromptu gambling with dice

This Riddler puzzle is an impromptu gambling game about rolling dice.

You and I stumble across a 100-sided die in our local game shop. We know we need to have this die — there is no question about it — but we’re not quite sure what to do with it. So we devise a simple game: We keep rolling our new purchase until one roll shows a number smaller than the one before. Suppose I give you a dollar every time you roll. How much money do you expect to win?

Extra credit: What happens to the amount of money as the number of sides increases?

Here is my solution:
[Show Solution]

For a more in-depth analysis of the distribution, read on:
[Show Solution]

Unmasking the Secret Santas

This Riddler puzzle is about the popular Secret Santa gift exchange game. Can we guess who our Secret Santa is?

The 41 FiveThirtyEight staff members have decided to send gifts to each other as part of a Secret Santa program. Each person is randomly assigned one of the other 40 people on the masthead to give a gift to, and they can’t give to themselves. After the Secret Santa is over, everybody naturally wants to find out who gave them their gift. So, each of them decides to ask up to 20 people who they were a Secret Santa for. If they can’t find the person who gave them the gift within 20 tries, they give up. (Twenty co-workers is a lot of co-workers to talk to, after all.) Each person asks and answers individually — they don’t tell who anyone else’s Secret Santa is. Also, nobody asks any question other than “Who were you Secret Santa for?”

If each person asks questions optimally, giving themselves the best chance to unmask their Secret Santa, what is the probability that everyone finds out who their Secret Santa was? And what is this optimal strategy? (Asking randomly won’t work, because only half the people will find their Secret Santa that way on average, and there’s about a 1-in-2 trillion chance that everyone will know.)

Here is my solution:
[Show Solution]

Will you be the deciding vote?

Another timely election-related Riddler problem. What are the odds of being the deciding vote?

You are the only sane voter in a state with two candidates running for Senate. There are N other people in the state, and each of them votes completely randomly! Those voters all act independently and have a 50-50 chance of voting for either candidate. What are the odds that your vote changes the outcome of the election toward your preferred candidate?

More importantly, how do these odds scale with the number of people in the state? For example, if twice as many people lived in the state, how much would your chances of swinging the election change?

Here is my solution:
[Show Solution]

What if robots cut your pizza?

This Riddler puzzle is about random chords of a circle and the regions they describe.

At RoboPizza™, pies are cut by robots. When making each cut, a robot will randomly (and independently) pick two points on a pizza’s circumference, and then cut along the chord connecting them. If you order a pizza and specify that you want the robot to make exactly three cuts, what is the expected number of pieces your pie will have?

Here is a simple solution, which was pointed out to me in a comment to my original post.
[Show Solution]

The following solution is a bit more complicated, and computes the entire distribution rather than just its expected value.
[Show Solution]

If you’ve already read the solution above and you’re interested in the distribution of pieces for the general case, read on!
[Show Solution]