## 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.

### 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]

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]