Allison, Bob And The Technicolor Dream Map

Welcome to The Riddler. Every week, I offer up problems related to the things we hold dear around here: math, logic and probability. These problems, puzzles and riddles come from many top-notch puzzle folks around the world — including you! There are two types: Riddler Express for those of you who want something bite-sized and Riddler Classic for those of you in the slow-puzzle movement.

You can mull them over on your commute, dissect them on your lunch break and argue about them with your friends and lovers. When you’re ready, submit your answer(s) using the buttons below. I’ll reveal the solutions next week, and a correct submission (chosen at random) will earn a shoutout in this column.1

Before we get to the new puzzles, let’s reveal the winners of last week’s. Congratulations to 👏 Adrianna Whitehouse 👏 of New York and 👏 Hart Levy 👏 of Toronto, our respective Express and Classic winners. You can find solutions to the previous Riddlers at the bottom of this post.

First, for Riddler Express, a dinner party puzzle from Robin Stewart:

A musician and her partner attended a dinner party with four other couples. At the party, as with most good dinner parties, both members of the couple had the opportunity to hug some of the other people at the party. There are three things we know about that evening: If an attendee hugged someone, they only hugged that person once; no one hugged him or herself; and no one hugged his or her partner.

On the way home, the musician, known to be an astute and accurate observer of interesting mathematical happenings, remarked to her partner: “Did you notice that everyone at the party other than me received a unique number of hugs?” How many hugs did the musician’s partner engage in?

If you need a hint, you can try asking me nicely. Want to submit a new Riddler Express? Email me.

Riddler Classic is something a little different and cool and colorful — a cartographical game from Dave Moran:

Allison and Bob decide to play a map-coloring game. Each turn, Allison draws a simple closed curve on a piece of paper, and Bob must then color the interior of the “country” that curve creates with one of his many crayons. If the new country borders any pre-existing countries, Bob must color the new country with a color that is different from the ones he used for the bordering ones.

For example, Allison creates Country 1 and Bob colors it green. Then Allison creates Country 2, which Bob colors purple, and so on.

Allison wins the game when she forces Bob to use a sixth color. If they both play optimally, how many countries will Allison have to draw to win?

If you need a hint, you can try asking me nicely. Want to submit a new Riddler Classic? Email me.

Here’s the solution to last week’s Riddler Express, which asked how quickly four people could cross a very scary bridge. Person 1 takes one minute to cross, Person 2 takes two minutes, Person 5 takes five and Person 10 takes 10; the bridge can support only two people at any time; and whoever is crossing needs to carry the group’s only flashlight. If two people cross at once, they cross at the speed of the slower person. The quickest they can get across is 17 minutes.

Here’s how to do it, from the puzzle’s submitter, Brent Edwards:

Person 1 crosses with Person 2, which takes two minutes. We’re at two minutes total.

Person 1 returns, which takes one minute. That’s three minutes total.

The flashlight is handed to Persons 5 and 10, who cross. That takes 10 minutes. We’re at 13 minutes total.

The flashlight is handed to Person 2, who returns in two minutes. That’s 15 minutes.

Finally, Persons 1 and 2 cross, which takes two minutes. That’s 17 minutes!

And here’s the solution to last week’s Riddler Classic, which asked if you (yes, you!) would change the results of an election. If the N voters who aren’t you each vote randomly and independently for one of two candidates, with a 50 percent chance of each, and you vote for your preferred candidate, there is about a $$\sqrt{\frac{2}{N \pi}}$$ chance that your vote will be decisive.

Why? Your vote will be decisive if and only if half of the N voters vote for one candidate and half of them vote for the other candidate. (For simplicity, let’s assume N is even. If N is odd, the best your vote can do is to move the election into a tie. You can tweak the formula above slightly to reflect that, but the distinction won’t make any meaningful difference when N is relatively large.) This distribution of voters, like the flipping of many coins, follows a binomial distribution, with N trials and a 0.5 probability of “success” (voting for a specific one of the candidates) in each trial. According to this distribution, the probability of a specific number, k, of successes if there is a probability p of success in any one trial is given by:

$${N \choose k} p^k (1-p)^{N-k}$$

Plugging in the specifics from our voting scenario gives our answer:

$${N \choose {N/2}} (1/2)^{(N/2)} (1/2)^{(N/2)}$$

Which simplifies a little to:

$${N \choose {N/2}} \frac{1}{2^N}$$

We can stop there and be completely correct, but it’s still a little hard to understand what happens to our chances of turning the election as the number of voters grows simply by looking at that formula. To see that more clearly, the puzzle’s submitter, Andrew Spann, suggests using Stirling’s approximation. That delivers this close approximation of your chances:

$$\sqrt{\frac{2}{N \pi}}$$

Laurent Lessard created the following graph of your chances as the number of voters grows:

Elsewhere in the puzzling world:

Have a great weekend!

## Footnotes

1. Important small print: To be eligible, I need to receive your correct answer before 11:59 p.m. EST on Sunday. Have a great weekend!

Oliver Roeder is a senior writer for FiveThirtyEight.