The lonesome king

This Riddler puzzle is about a random elimination game. Will someone remain at the end, or will everyone be eliminated?

In the first round, every subject simultaneously chooses a random other subject on the green. (It’s possible, of course, that some subjects will be chosen by more than one other subject.) Everybody chosen is eliminated. In each successive round, the subjects who are still in contention simultaneously choose a random remaining subject, and again everybody chosen is eliminated. If there is eventually exactly one subject remaining at the end of a round, he or she wins and heads straight to the castle for fêting. However, it’s also possible that everybody could be eliminated in the last round, in which case nobody wins and the king remains alone. If the kingdom has a population of 56,000 (not including the king), is it more likely that a prince or princess will be crowned or that nobody will win? How does the answer change for a kingdom of arbitrary size?

Here is my solution:
[Show Solution]

Adversarial map coloring

This Riddler problem considers the classical map-coloring problem with an adversarial twist! One player draws countries and the other player colors them.

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.

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?

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]

Rig the election with math!

This Riddler problem is about gerrymandering. How to redraw borders to sway a vote one way or another.

Below is a rough approximation of Colorado’s voter preferences, based on county-level results from the 2012 presidential election, in a 14-by-10 grid. Colorado has seven districts, so each would have 20 voters in this model. In each district, the party with the most votes will win. The districts must be non-overlapping and contiguous (that is, each square in a district must share an edge with at least one other square in the district). What is the most districts that the Red Party could win? What about the Blue Party? (Assume ties within a district are considered wins for the party of your choice.)

Two boards are provided, a test 5×5 grid and the larger 14×10 grid:
gerry_combo

Here is a first solution, using some simple logic and intuition:
[Show Solution]

And here is a computational approach, using integer programming:
[Show Solution]

The deadly board game

This Riddler classic puzzle involves a combination of decision-making and probability.

While traveling in the Kingdom of Arbitraria, you are accused of a heinous crime. Arbitraria decides who’s guilty or innocent not through a court system, but a board game. It’s played on a simple board: a track with sequential spaces numbered from 0 to 1,000. The zero space is marked “start,” and your token is placed on it. You are handed a fair six-sided die and three coins. You are allowed to place the coins on three different (nonzero) spaces. Once placed, the coins may not be moved.

After placing the three coins, you roll the die and move your token forward the appropriate number of spaces. If, after moving the token, it lands on a space with a coin on it, you are freed. If not, you roll again and continue moving forward. If your token passes all three coins without landing on one, you are executed. On which three spaces should you place the coins to maximize your chances of survival?

Extra credit: Suppose there’s an additional rule that you cannot place the coins on adjacent spaces. What is the ideal placement now? What about the worst squares — where should you place your coins if you’re making a play for martyrdom?

Here is my solution:
[Show Solution]

Non-intersecting chessboard paths

This Riddler classic puzzle is about finding non-intersecting paths on a chessboard:

First, how long is the longest path a knight can travel on a standard 8-by-8 board without letting the path intersect itself?

Second, there are unorthodox chess pieces that don’t exist in the standard game, which are known as fairy chess pieces. What are the longest nonintersecting paths that can be taken by the camel (which moves like a knight, except 3 squares by 1 square), the zebra (3 by 2), and the giraffe (4 by 1)?

This is a very challenging problem, and there doesn’t appear to be any way to solve it via some clever observation or simplification. Of course, we can try to come up with ever longer tours by hand, but we’ll never know for sure that we have found the longest one.

Much like the recent Pokemon Go problem, we must resort to computational means to obtain a solution. In this case, however, the problem is “small enough” that we can find exact solutions!

Here are some optimal tours:
[Show Solution]

If you’re interested in the details of how I found my solutions, read on:
[Show Solution]

Betting on the world series

This Riddler classic puzzle is about placing bets on baseball:

You are a gambler and a Cubs fan. The Cubs are competing in a seven-game series against the Red Sox — first to four games wins. Your bookie agrees to take any even-odds bets on any of the individual games. Can you construct a series of bets such that the guaranteed outcomes are: You win \$100 if the Cubs wins the series and lose \$100 if the Red Sox win it?

The challenge here is that we don’t know ahead of time when the series will end. It could end in a four-game blowout, or it could last the full seven games. How should we construct our bets so that the result is the same regardless of series length? Here is my solution:
[Show Solution]

Cutting a circular table

This Riddler Classic puzzle is about cutting circles out of rectangles!

You’re on a DIY kick and want to build a circular dining table which can be split in half so leaves can be added when entertaining guests. As luck would have it, on your last trip to the lumber yard, you came across the most pristine piece of exotic wood that would be perfect for the circular table top. Trouble is, the piece is rectangular. You are happy to have the leaves fashioned from one of the slightly-less-than-perfect pieces underneath it, but there’s still the issue of the main circle. You devise a plan: cut two congruent semicircles from the perfect 4-by-8-foot piece and reassemble them to form the circular top of your table. What is the radius of the largest possible circular table you can make?

Here is my solution to the case of a general rectangular table. The result may surprise you!
[Show Solution]

Randomized team drafting strategy

This Riddler Classic puzzle explores a randomized team drafting strategy designed to prevent teams from throwing games.

You are one of 30 team owners in a professional sports league. In the past, your league set the order for its annual draft using the teams’ records from the previous season — the team with the worst record got the first draft pick, the team with the second-worst record got the next pick, and so on. However, due to concerns about teams intentionally losing games to improve their picks, the league adopts a modified system. This year, each team tosses a coin. All the teams that call their coin toss correctly go into Group A, and the teams that lost the toss go into Group B. All the Group A teams pick before all the Group B teams; within each group, picks are ordered in the traditional way, from worst record to best. If your team would have picked 10th in the old system, what is your expected draft position under the new system?

Extra credit: Suppose each team is randomly assigned to one of T groups where all the teams in Group 1 pick, then all the teams in Group 2, and so on. (The coin-flipping scenario above is the case where T = 2.) What is the expected draft position of the team with the Nth-best record?

Here is my solution to the general case:
[Show Solution]

While the expected draft position is not that difficult to characterize, one can also ask about the distribution of draft positions:
[Show Solution]

Splitting a hundred dollar bill

This Riddler puzzle investigates a method for deciding who should get a $100 bill found on the ground. It leads to some interesting consequences…

You and four statistician colleagues find a \$100 bill on the floor of your department’s faculty lounge. None of you have change, so you agree to play a game of chance to divide the money probabilistically. The five of you sit around a table. The game is played in turns. Each turn, one of three things can happen, each with an equal probability: The bill can move one position to the left, one position to the right, or the game ends and the person with the bill in front of him or her wins the game. You have tenure and seniority, so the bill starts in front of you. What are the chances you win the money? What if there were N statisticians in the department?

Here is my solution to the first part, assuming five statisticians.
[Show Solution]

Here is my solution to the second part, assuming $N$ statisticians.
[Show Solution]

For the brave and curious, this next section explores connections between the problem and Fourier Transforms, complex analysis, and Chebyshev polynomials. Fair warning: advanced math!
[Show Solution]