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]

How many bananas can the camel carry?

This Riddler puzzle is a simple twist on a classic.

You have a camel and 3,000 bananas. You would like to sell your bananas at the bazaar 1,000 miles away. Your loyal camel can carry at most 1,000 bananas at a time. However, it has an insatiable appetite and quite the nose for bananas — if you have bananas with you, it will demand one banana per mile traveled. In the absence of bananas on his back, it will happily walk as far as needed to get more bananas, loyal beast that it is. What should you do to get the largest number of bananas to the bazaar? What is that number?

Here is my solution.
[Show Solution]

Baking the optimal cake

This Riddler puzzle asks about finding the maximum-volume shape subject to constraints.

A mathematician who has a birthday coming up asks his students to make him a cake. He is very particular and asks his students to make him a three-layer cake that fits under a hollow glass cone he has on his desk. He requires that the cake fill up the maximum amount of volume under the cone as possible and that the layers of the cake have straight vertical sides. What are the thicknesses of the three layers of the cake in terms of the height of the glass cone? What percentage of the cone’s volume does the cake fill?

Here is my solution.
[Show Solution]

Here, I go into more detail about bounding the optimal cake volume as the number of layers becomes large.
[Show Solution]

Can you outrun the angry ram?

The Riddler puzzle this week appears simple at first glance, but I promise you it’s not!

You, a hard-driving sheep farmer, are tucked into the southeast corner of your square, fenced-in sheep paddock. There are two gates equidistant from you: one at the southwest corner and one at the northeast corner. An angry, recalcitrant ram enters the paddock from the southwest gate and charges directly at you at a constant speed. You run — obviously! — at a constant speed along the eastern fence toward the northeast gate in an attempt to escape. The ram keeps charging, always directly at you.

How much faster than you does the ram have to run so that he catches you just as you reach the gate?

Here is a very simple solution by Hector Pefo. Minimal calculus required!
[Show Solution]

And here is my solution, which finds an equation for the path of the ram but requires knowledge of calculus and differential equations.
[Show Solution]