The Riddler - Book Proofs

The number line game

This Riddler puzzle is a game theory problem: how should each player play the game to maximize their own winnings?

Ariel, Beatrice and Cassandra — three brilliant game theorists — were bored at a game theory conference (shocking, we know) and devised the following game to pass the time. They drew a number line and placed \$1 on the 1, \$2 on the 2, \$3 on the 3 and so on to \$10 on the 10.

Each player has a personalized token. They take turns — Ariel first, Beatrice second and Cassandra third — placing their tokens on one of the money stacks (only one token is allowed per space). Once the tokens are all placed, each player gets to take every stack that her token is on or is closest to. If a stack is midway between two tokens, the players split that cash.

How will this game play out? How much is it worth to go first?

A grab bag of extra credits: What if the game were played not on a number line but on a clock, with values of \$1 to \$12? What if Desdemona, Eleanor and so on joined the original game? What if the tokens could be placed anywhere on the number line, not just the stacks?

Here are the details of how I approached the problem:
[Show Solution]

This problem is different from previous game theory problems I’ve written about such as the war game or the dodgeball duel, where all players in the game act simultaneously. In such games, you can assume a strategy for each player, and then look for the strategy that yields a Nash equilibrium, which is a set of strategies such that no player has any incentive to change their actions. Sometimes, the optimal strategy is a mixed strategy, which means it involves randomness. This is the case in rock-paper-scissors, for example, where the Nash-optimal strategy is to choose randomly.

What makes the present problem quite different is that it’s a sequential game in which each player gets to see the previous players’ moves when it comes their turn to play. This means that there can be no advantage to playing randomly. The standard way to solve such problems is via backward induction (also known as dynamic programming). I will illustrate the approach for the basic version of the problem: 10 stacks and 3 players. A strategy is a set of moves $(a,b,c)$ where $a$ is Ariel’s move, $b$ is Beatrice’s move, and $c$ is Cassandra’s move. We proceed by backward induction as follows:

Given a strategy $(a,b,c)$, let’s call Ariel’s payout $P_A(a,b,c)$. Similarly, we’ll call Beatrice’s and Cassandra’s payouts $P_B$ and $P_C$, respectively.
Imagine it’s Cassandra’s turn. She observes Ariel and Beatrice’s moves $a$ and $b$. For each potential choice of $c$, we can compute Cassandra’s payout $P_C(a,b,c)$ and then select the most profitable choice of $c$. Let’s call Cassandra’s strategy $K_C(a,b)$. Mathematically, we’re defining:
\[
K_C(a,b) = \arg\max_{c} P_C(a,b,c)
\]
Now imagine it’s Beatrice’s turn. She observes Ariel’s move ($a$). She also knows that if she chooses $b$, then Cassandra will follow up with $K_C(a,b)$. So she must choose the best $b$ in anticipation of what Cassandra will do. If we call Beatrice’s strategy $K_B(a)$, then we have:
\[
K_B(a) = \arg\max_{b} P_B(a,b,K_C(a,b))
\]
Finally, imagine it’s Ariel’s turn. Although she’s the first to move, no matter which $a$ she picks, she can be assured Beatrice will choose $b = K_B(a)$ and Cassandra will follow-up with $c = K_C(a,b)$. So Ariel can examine all of her options and predict her payout. Ultimately, her decision will be $K_A$, which is given by:
\[
K_A = \arg\max_{a} P_A(a,K_B(a),K_C(a,K_B(a)))
\]

Computational details

Writing code to implement the backward induction above was quite a challenge. I will include my finished code later so you can play with it, but for now I’ll just highlight two of the major hurdles I had to overcome.

A naive implementation of the above steps quickly becomes computationally intractable as we make the problem larger. If there are $N$ money stacks and $M$ players, the number of possible strategies is $N(N-1)\cdots(N-M+1)$, which can be quite large. So if $N=12$ and $M=9$, the $K$ function for the last player will depend on how the first $8$ players moved, and there are about 20 million possibilities there. Things deteriorate rapidly as we further increase $N$ or $M$. I observed that the best move for any player does not depend on the order in which the previous players moved. So for the intent of making the functions $K_A$, $K_B$, etc., we may assume the inputs are sorted. This reduces the number of possible strategies to $\binom{N}{M}$. So in the example above, the 20 million possibilities reduces to 500, a far more manageable number.
The optimal solution may not be unique. At each step, there may be several choices that produce identical payouts for the deciding player. Keeping track of all possibilities is tedious because it means that each $\arg\max$ can return many solutions, and each of those must be propagated back through the other functions. I implemented the recursion using lists of strategies, so at every step I was passing around lists of optimal strategies rather than just one strategy.
Extensions and bonus questions. After some thought, I was able to write the code in a way that solves the bonus questions with only minor modifications. Writing generic code in terms of $N$ and $M$ allows the easy addition of more stacks or more players. Writing the number line so it wraps around (on a clock) just amounts to redefining the function that computes the payouts for each strategy. Solving the continuous version amounts to adding extra slots in between the stacks and suitably redefining the payout function.
Bugs. So many bugs! This was the trickiest piece of code I’ve written in awhile, and tracking down indexing errors in the recursion was a challenge to say the least. I think I got everything working in the end and I’m quite please with it!

The results from my simulation are in the next section.

And here are the answers:
[Show Solution]

Adding more players

Let’s call $N$ the number of money stacks and $M$ the number of players. Here is a table showing the case $N=10$ as we add more players.

Players	Optimal strategies (number line)	Optimal payouts (in dollars)
$2$	$(7,8)$	$(28,27)$
$3$	$(5, 9, 8)$	$(21, 19, 15)$
$4$	$(7, 4, 9, 10)$	$(17, 15, 13, 10)$
$5$	$(4, 6, 8, 10, 9)$	$(12.5, 12, 11.5, 10, 9)$
$6$	$(4, 10, 9, 6, 8, 7)$	$(12.5, 10, 9, 8.5, 8, 7)$
$7$	$(10, 9, 3, 8, 5, 7, 6)$ $(10, 9, 3, 8, 7, 5, 6)$ $(10, 9, 8, 3, 5, 7, 6)$ $(10, 9, 8, 3, 7, 5, 6)$	$(10, 9, 8, 8, 7, 7, 6)$
$8$	$(10, 9, 8, 7, 3, 6, 5, 4)$ $(10, 9, 8, 7, 6, 3, 5, 4)$	$(10, 9, 8, 7, 6, 6, 5, 4)$
$9$	$(10, 9, 8, 7, 6, 5, 4, 2, 3)$ $(10, 9, 8, 7, 6, 5, 4, 3, 2)$	$(10, 9, 8, 7, 6, 5, 4, 3, 3)$
$10$	$(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)$	$(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)$

At the onset, it wasn’t clear whether it would be best to move first in order to stake claim to the best spots or to move later on and have the advantage of playing reactively. As we can see from the table above, the first player always has the highest payout and it gets worse for subsequent players. Some of the rows contain multiple strategies. These are cases with multiple Nash equilibria. All produce identical payoffs.

In the original problem with $M=3$ players, it’s worth \$21 to go first. Of course, this assumes everybody is playing in a greedy fashion and trying to maximize their own payoffs. If Beatrice and Cassandra conspired to ruin Ariel’s day, they could reduce Ariel’s winnings to \$5 (by placing tokens at 4 and 6) but they would have to trust each other enough to split their \$50 winnings evenly after the game is over!

Playing around the clock

If we wrap the number line around a clock, the game changes slightly, but the code only requires minor modification. All we need to do is define how payoffs are computed, since the “closest” token may be either clockwise or counterclockwise from a given stack. Here are the results with $N=12$ as we add more players.

Players	Optimal strategies (clock)	Optimal payouts (in dollars)
$2$	$(9, 10)$ $(10, 9)$	$(39, 39)$
$3$	$(7, 11, 10)$	$(31.5, 27.5, 19)$
$4$	$(6, 9, 12, 11)$	$(23.5, 22, 16.5, 16)$
$5$	$(8, 5, 12, 10, 11)$	$(19.5, 18, 15, 14.5, 11)$
$6$	$(5, 12, 7, 9, 11, 10)$ $(12, 5, 7, 9, 11, 10)$	$(15, 15, 14, 13, 11, 10)$
$7$	$(12, 9, 7, 11, 4, 10, 6)$ $(12, 9, 11, 7, 4, 10, 6)$	$(14, 13, 11, 11, 10.5, 10, 8.5)$
$8$	$(12, 11, 4, 10, 9, 6, 8, 7)$	$(14, 11, 10.5, 10, 9, 8.5, 8, 7)$
$9$	$(12, 11, 10, 9, 8, 3, 5, 7, 6)$ $(12, 11, 10, 9, 8, 3, 7, 5, 6)$ $(12, 11, 10, 9, 8, 7, 3, 5, 6)$	$(13, 11, 10, 9, 8, 7, 7, 7, 6)$
$10$	$(12, 11, 10, 9, 8, 7, 6, 3, 5, 4)$ $(12, 11, 10, 9, 8, 7, 6, 5, 3, 4)$	$(13, 11, 10, 9, 8, 7, 6, 5, 5, 4)$
$11$	$(12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2)$	$(12.5, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2.5)$
$12$	$(12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1)$	$(12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1)$

As in the number line case, there are many instances with multiple Nash equilibria and each case leads to the same payoff.

Continuous number line

I adapted my code to handle the continuous case by adding intermediate slots in between each stack. This allows players to play “in between” the stacks if they so choose. If I return to $N=10$ on the number line add 4 slots between each stack for $M=2$ and $M=3$. Here are the results:

Players	Optimal strategies (continuous)	Optimal payouts (in dollars)
$2$	$(7.0, 7.2)$ $(7.0, 7.4)$ $(7.0, 7.6)$ $(7.0, 7.8)$ $(7.0, 8.0)$ $(7.0, 8.2)$ $(7.0, 8.4)$ $(7.0, 8.6)$ $(7.0, 8.8)$	$(28, 27)$
$3$	$(5.0, 9.0, 7.2)$ $(5.0, 9.0, 7.4)$ $(5.0, 9.0, 7.6)$ $(5.0, 9.0, 7.8)$ $(5.0, 9.0, 8.0)$ $(5.0, 9.0, 8.2)$ $(5.0, 9.0, 8.4)$ $(5.0, 9.0, 8.6)$ $(5.0, 9.0, 8.8)$	$(21, 19, 15)$

Here it’s clear what’s going on; given the option, the first players do not choose to deviate. Ultimately, the last player has freedom to move their token in the range $7 \lt c \lt 9$ and the payoff doesn’t change, and it matches the solution in the integer case (where $c=8$ is optimal). So at least in these cases, making the problem continuous doesn’t change a thing.

This isn’t always true. The solution gets more complex if we examine the case $M=4$. Here, I tried solving the problem with different discretizations and I found the following:

Players	Optimal strategies (continuous)	Optimal payouts (in dollars)
$4$	Steps of $0.50$: $(9.00, 3.50, 6.50, 7.50)$ Steps of $0.25$: $(9.00, 3.25, 6.75, 7.25)$ Steps of $0.20$: $(9.00, 3.20, 6.80, 7.20)$ Steps of $0.10$: $(9.00, 3.10, 6.90, 7.10)$	$(19, 12.5, 12, 11.5)$

This case highlights when using a discretization breaks down. We would never expect any stacks to be evenly split in the continuous case because you can always nudge your token a little bit in order to be a little closer to either stack and win it all. It also appears that as we reduce the discretization to $\epsilon$, the unique optimal strategy is $(9, 3+\epsilon, 7-\epsilon, 7+\epsilon)$. This solution is an artifact of our discretization. Indeed, the last player could do better by picking $7+\tfrac{1}{2}\epsilon$.

One way around this would be to give each successive player a finer discretization to choose from. This would prevent the case above from occurring. I didn’t code this up so I didn’t verify that the Nash-optimal solution for the discrete case is the same in the continuous case. Future work!

My code

I wrote my code in Julia (version 0.6.2.1). For those that don’t know about Julia, it’s a fast language for scientific computing that is syntactically similar to Matlab and Python. If you are interested in seeing my code, here is my Jupyter notebook.

Rug quality control

This Riddler puzzle is about rug manufacturing. How likely are we to avoid defects if manufacture the rugs randomly?

A manufacturer, Riddler Rugs™, produces a random-pattern rug by sewing 1-inch-square pieces of fabric together. The final rugs are 100 inches by 100 inches, and the 1-inch pieces come in three colors: midnight green, silver, and white. The machine randomly picks a 1-inch fabric color for each piece of a rug. Because the manufacturer wants the rugs to look random, it rejects any rug that has a 4-by-4 block of squares that are all the same color. (Its customers don’t have a great sense of the law of large numbers, or of large rugs, for that matter.)

What percentage of rugs would we expect Riddler Rugs™ to reject? How many colors should it use in the rug if it wants to manufacture a million rugs without rejecting any of them?

Here is my solution:
[Show Solution]

Since every possible rug is equally likely to occur, the probability of a rug being rejected is equal to the total number of defective rugs divided by the total number of rugs. Let’s assume the rug is $n\times n$, there are $d$ distinct color choices, and we’re looking to avoid $m\times m$ same-color patches. There are $N = (n-m+1)^2$ different $m\times m$ patches on the rug. For easier bookkeeping, let’s number these using a single index $1 \le i \le N$. Let’s define the following event:
\[
X_{i} = \left\{
\begin{array}{l}\text{the }i^\text{th} \text{ }m\times m \text{ patch}\\\text{is all the same color}\end{array}\right.
\]The union of these events $X = \bigcup_{i=1}^N X_{i}$ describes the case where there is at least one same-color patch on the rug and therefore the rug must be rejected. We seek to compute the probability $\mathbb{P}(X)$.

The inclusion-exclusion principle allows us to express $X$ in terms of the $X_i$, which will be useful because of the inherent symmetry present in the problem. Specifically, each $X_i$ has the same probability of occurrence! If we define the probabilities:
\begin{align}
S_1 &= \sum_{1\le i \le N} \mathbb{P}(X_i) \\
S_2 &= \sum_{1\le i\lt j\le N} \mathbb{P}(X_i \cap X_j) \\
&\,\,\,\vdots \\
S_k &= \sum_{1\le i_1 \lt\cdots\lt i_k\le n} \mathbb{P}(X_{i_1} \cap \cdots \cap X_{i_k})
\end{align}then the inclusion-exclusion principle states that:
\[
\mathbb{P}(X) = \sum_{k=1}^N (-1)^{k-1}S_k
\]We mentioned that the individual probabilities $\mathbb{P}(X_i)$ are easy to compute. Indeed, each color occurs with probability $1/d$ and there are $m^2$ cells in each patch. So the probability that all cells are of a particular color is $1/d^{m^2}$. Multiplying by $d$ to account for the $d$ possible colors, we obtain:
\[
\mathbb{P}(X_i) = \frac{1}{d^{m^2-1}}\qquad\text{for all }i
\]Therefore, $S_1 = N/d^{m^2-1}$. Setting $n=100,\,m=4,\,d=3$, we find:
\[
S_1 = 0.065573\%
\]To compute $S_2$, we must compute the probability of the intersection of two events, i.e. the probability that two patches are simultaneously mono-colored. There are two possibilities:
\[
\mathbb{P}(X_i \cap X_j) = \begin{cases}
\frac{1}{d^{2(m^2-1)}} & \begin{array}{l}\text{if the patches don’t overlap}\end{array}\\
\frac{1}{d^{c-1}} & \begin{array}{l}
\text{if the patches overlap and}\\
\text{together cover }c\text{ cells in total}
\end{array}
\end{cases}
\]This follows because when patches don’t overlap, the events are independent, so the probability that both patches are mono-colored is the product of probabilities that each is mono-colored. When the patches overlap, however, they can only both be mono-colored if they are both the same color! And here, the probability depends on how much the patches overlap. I wrote a simple script that loops over all pairs of patches, computes the above probabilities, and sums them up. The result was:
\[
S_2 = 0.0017071\%
\]We could continue in this fashion, computing $S_3,S_4,\dots$ but this is a hopeless endeavor as we must account for the probability that $k$ patches are simultaneously mono-colored… which will get messy in a hurry. Instead, we’ll use an additional piece to the inclusion-exclusion principle, called the Bonferroni inequality, which states that as we add and subtract the $S_k$ terms on our way to computing $\mathbb{P}(X)$, they alternate between providing upper and lower bounds!. This means that we can use $S_1$ and $S_2$ to compute an approximation:
\[
S_1-S_2 \le \mathbb{P}(X) \le S_1
\]Substituting the numbers we computed above, we obtain:

$\displaystyle
0.063866\% \lt \mathbb{P}(\text{rug is rejected}) \lt 0.065573\%
$

It’s reasonable to expect that $S_k$ will continue to decrease as $k$ increases. If we assume that the $S_k$ will decrease geometrically, that would give us $S_3 \approx 0.000044\%$, which would tighten our bound to $0.06387 \lt \mathbb{P}(X) \lessapprox 0.06391\%$. So if I had to guess a single number, it would be that the probability of rejection is about $0.0639\%$.

For the second part of the problem, we are asked about how many colors we should use in order to be ensured that we can manufacture one million rugs and have no rejections. Each rug is independently manufactured, so if we call $p$ the probability of one rug being rejected, the probability that no rugs get rejected after one million rugs are made is:
\[
\mathbb{P}(\text{no rejections}) = (1-p)^{1,000,000}
\]Since we don’t know the exact value of $p$, we can again compute upper and lower bounds. Since we want a conservative estimate of how many colors to use, it makes sense to under-estimate the probability of having no rejections. This amounts to using our upper bound for $p$. Here is a plot showing the probability of no rejections in the entire batch, as a function of $d$, the number of colors used.

Remember that these are lower bounds on the probability that no rugs get rejected. The true probability will be higher. Based on this fact, we’ll likely be safe if we pick $6$ colors.

Here are the probabilities in tabular form, and I also included the corresponding upper bound using the Bonferroni inequality discussed earlier.

Colors	lower bound on probability	upper bound on probability
$3$	$0$	$3.9\times 10^{-8}$
$4$	$0.01564\%$	$93.320\%$
$5$	$73.4684\%$	$99.901\%$
$6$	$98.0188\%$	$99.996\%$
$7$	$99.802\%$	$100\%$
$8$	$99.973\%$	$100\%$
$9$	$99.9954\%$	$100\%$
$10$	$99.9991\%$	$100\%$

The upper bound makes a big jump when we add a fourth color, and as discussed previously, this bound is likely the tighter of the two. So although we argued for 6 colors before, this is probably overly conservative and we could get away with using 5 colors.

A coin-flipping game

This Riddler puzzle involves a particular coin-flipping game. Here is the problem:

I flip a coin. If it’s heads, I’ve won the game. If it’s tails, then I have to flip again, now needing to get two heads in a row to win. If, on my second toss, I get another tails instead of a heads, then I now need three heads in a row to win. If, instead, I get a heads on my second toss (having flipped a tails on the first toss) then I still need to get a second heads to have two heads in a row and win, but if my next toss is a tails (having thus tossed tails-heads-tails), I now need to flip three heads in a row to win, and so on. The more tails you’ve tossed, the more heads in a row you’ll need to win this game.

I may flip a potentially infinite number of times, always needing to flip a series of N heads in a row to win, where N is T + 1 and T is the number of cumulative tails tossed. I win when I flip the required number of heads in a row.

What are my chances of winning this game? (A computer program could calculate the probability to any degree of precision, but is there a more elegant mathematical expression for the probability of winning?)

Here is my solution:
[Show Solution]

L-bisector

This post is about a geometry Riddler puzzle involving bisecting a shape using only a straightedge and a pencil. Here is the problem:

Say you have an “L” shape formed by two rectangles touching each other. These two rectangles could have any dimensions and they don’t have to be equal to each other in any way. (A few examples are shown below.)

Using only a straightedge and a pencil (no rulers, protractors or compasses), how can you draw a single straight line that cuts the L into two halves of exactly equal area, no matter what the dimensions of the L are? You can draw as many lines as you want to get to the solution, but the bisector itself can only be one single straight line.

Here is my solution:
[Show Solution]

This is a wonderful little puzzle with a very elegant solution. This solution is based on three observations:

You can find the center of a rectangle using only a straightedge and pencil. This can be done by drawing a straight lines connecting opposite corners of the rectangle. The center of the rectangle is where the two lines intersect.
Any line passing through the center of a rectangle bisects its area. This follows because of symmetry. The two halves of the rectangle thus created are actually rotated versions of one another (180 deg. about the center).
The “L” shape is simply two smaller rectangles. Alternatively, you can think of it as a large rectangle with a smaller rectangle subtracted from it. This is evident if you look at the shapes in the problem statement.

And now, the solution is simple. Extend side lengths of the “L” shape to mark all the corners of the rectangles involved. Then find the centers of those rectangles as described in item 1 above, and join the centers using a straight line. This line bisects the L-shape because it bisects each of the rectangles. Depending on how you partition your L-shape, you can get two different bisectors:

Alternatively, you can think of the L-shape as the difference of two rectangles. The logic is similar: since the line bisects each rectangle, it must also bisect their difference! Here is an illustration of this construction:

This strategy works for any shape that is the sum or difference of two rectangles! So it’s not restricted to L-shapes. More examples:

Finally, the construction also works if the rectangles are replaced by parallelograms, or any other shapes with the two properties that we can construct the center easily and all lines through the center bisect the area. For example…

But why stop there? You can also extend this construction to 3D! Any plane passing through the center of a rectangular prism bisects its volume. Therefore, if you made a shape by adding and/or subtracting three rectangular prisms, the plane passing through the three centers would bisect the volume of the entire shape!

Smudged secret messages

This Riddler is a twist on a classic problem: decoding equations! Here is the paraphrased problem:

The goal is to decode two equations. In each of them, every different letter stands for a different digit. But there is a minor problem in both equations. In the first equation, letters accidentally were smudged and are now unreadable. (These are represented with dashes below.) But we know that all 10 digits, 0 through 9, appear in the equation.

What digits belong to what letters, and what are the dashes? In the second equation, one of the letters in the equation is wrong. But we don’t know which one. Which is it?

Here is my detailed solution:
[Show Solution]

This type of puzzle is called a cryptarithm, but this variant has the additional twist of smudges or errors that make the puzzle more challenging. Just like Sudoku, the puzzle involves filling numbers in a grid subject to several rules. Similarly, we can solve the problem by carefully and methodically deducing the solution using logic. In this post, I’m going to present a completely different approach; integer programming! By encoding the problem as an integer program, we can leverage powerful solvers to rapidly find the solution.

You might be thinking: if we’re asking a computer to solve the problem, then why not just have the computer check all possibilities? In this case, there are 10! = 3,628,800 different ways to assign the letters to the digits 0 through 9. This is certainly within the realm of possibility. I wrote code to do this and it took about 16 seconds to loop through all permutations. If we stop once we find a solution, we can expect this approach to take about 8 seconds. Not bad, but not particularly elegant either… I’ve included a link to all my code at the bottom of this post in case you’re interested in seeing how I went about coding it.

First problem

The secret code is:
\[
EXMREEK + EHKREKK = -K\!-\!H\!-\!X\!-\!E
\]The first thing to observe is that there are six distinct letters: $\{E,X,M,R,K,H\}$ and there are four smudges. Since each number 0 through 9 must appear exactly once, this tells us that the four smudges must correspond to different numbers. Therefore, we can add more variables and write the equation as:
\[
EXMREEK + EHKREKK = AKBHCXDE
\]

We will use ten binary numbers to encode each letter. For example, the letter $E$ is encoded using the list of binary numbers $\{E_0,E_1,\dots,E_9\}$ and represented as:
\[
E = E_1 + 2 E_2 + 3 E_3 + \cdots + 9 E_9
\]We then add the constraint:
\[
E_0 + E_1 + \cdots + E_9 = 1\qquad\text{for }\{E,X,M,\dots,D\}
\]This forces exactly one of the $E_j$ to equal $1$. This will be our way of encoding $E=j$. We also encode the other 9 letters in a similar way. Next, we must ensure that each letter corresponds to a distinct number. We do this by adding the constraints
\[
E_j + X_j + M_j + \cdots + D_j = 1\qquad\text{for }j=0,\dots,9
\]This ensures that the digit $j$ is associated to exactly one of the letters.

Next, we introduce variables to represent the “carry-over” digits. Since we’re adding two numbers, we will only ever carry over 0 or 1 for each digit. Let’s call these variables $Q_j$. The sum then looks like:
\[
\begin{array}{cccccccc}
Q_1&Q_2&Q_3&Q_4&Q_5&Q_6&Q_7& \\
& E & X & M & R & E & E & K \\
+ & E & H & K & R & E & K & K \\ \hline
A & K & B & H & C & X & D & E
\end{array}
\]We then add a constraint for each of the “columns” that includes the carry-over digits. Starting from the right, we have:
\begin{align}
K + K &= 10 Q_7 + E \\
Q_7 + E + K &= 10 Q_6 + D \\
Q_6 + E + E &= 10 Q_5 + X \\
&\;\;\vdots \\
Q_2 + E + E &= 10 Q_1 + K \\
Q_1 &= A
\end{align}Taking a tally of what we’ve got so far, each letter above is encoded using ten binary variables, which we can substitute into each of the constraints above. The net result is that we must find 107 binary variables that satisfy 28 linear equality constraints. There is no objective function here; it’s just a feasibility problem. In other words, any combination of the variables that satisfies the equality constraints is a legitimate solution.

I coded this up in Julia using JuMP and the Gurobi solver. It took about 0.005 seconds to solve on my laptop (1,600 times faster than the brute-force solution!) and the solution turned out to be:
\begin{align}
B &= 0 & A &= 1 & X &= 2 & K &= 3 & M &= 4 \\
C &= 5 & E &= 6 & R &= 7 & H &= 8 & D &= 9
\end{align}

Second problem

In the second problem, the equation is:
\[
YTBBEDMKD + YHDBTYYDD = EDYTERTPTY
\] In this variant, there is an “error” somewhere in the above sum. In other words, one of the letters is wrong. This seems rather difficult to model, so we will model something related (and equivalent) instead. Instead of saying that one of the letters is wrong, we’ll say that one of the column sums is wrong. Proceeding as we did in the first problem, the equations (with carry-overs) look like:
\[
\begin{array}{cccccccccc}
Q_1&Q_2&Q_3&Q_4&Q_5&Q_6&Q_7&Q_8&Q_9& \\
&Y&T&B&B&E&D&M&K&D \\
+&Y&H&D&B&T&Y&Y&D&D \\ \hline
E&D&Y&T&E&R&T&P&T&Y
\end{array}
\]Let’s introduce new binary variables $Z_1,\dots,Z_{10}$ that encode whether the corresponding column sum is incorrect or not. We want:
\begin{align}
\text{if }Z_1&=0 & &\text{then} & Q_1 &= E \\
\text{if }Z_2&=0 & &\text{then} & Q_2 + Y + Y &= 10 Q_1 + D \\
\text{if }Z_3&=0 & &\text{then} & Q_3 + T + H &= 10 Q_2 + Y \\
&\;\;\vdots & &\quad \vdots & &\;\;\vdots \\
\text{if }Z_9&=0 & &\text{then} & Q_9 + K + D &= 10 Q_8 + T \\
\text{if }Z_{10}&=0 & &\text{then} & D + D &= 10 Q_9 + Y
\end{align}Therefore, if one of the equalities does not hold, this will result in the corresponding $Z_j$ being equal to $1$. We can then add an objective function; we seek the choice of $\{Y,T,B,\dots,P\}$ and $\{Q_j\}$ and $\{Z_j\}$ such that the sum $Z_1+\dots+Z_{10}$ is minimized. We are told there is one error, so we expect to be able to achieve a sum of 1, and we’ll know where the error lies.

So how do we encode these logical “if this then that” constraints into something more manageable (i.e. something algebraic)? A popular way to do this is via the big M method. I’ll use the third constraint as an example, and let’s rearrange it so it’s equal to zero:
\begin{align}
\text{if }Z_3&=0 & &\text{then} & Q_3+T+H-10 Q_2-Y&=0
\end{align}Since $Q_2,Q_3\in\{0,1\}$ and $T,H,Y\in\{0,\dots,9\}$, by substituting in order to minimize or maximize, we obtain the following bounds:
\[
-19 \le Q_3+T+H-10 Q_2-Y \le 19
\]We can then encode the logical “if this then that” constraint as:
\[
-19Z_3 \le Q_3+T+H-10 Q_2-Y \le 19Z_3
\]Note that when $Z_3=0$, both sides of the inequality become zero, effectively turning it into an equality, which is what we wanted! Conversely, if $Z_3=1$ the left and right sides are replaced by global lower and upper bounds, so the constraint becomes a tautology. I coded this up using Julia/JuMP/Gurobi as before. The result is an integer linear program with 119 binary variables, 20 equality constraints, and 20 inequality constraints. It took about 0.3 seconds to solve on my laptop and the solution turned out to be:
\begin{align}
R&=0 & E&=1 & M&=2 & D&=3 & K&=4 \\
B&=5 & Y&=6 & H&=7 & P&=8 & T&=9
\end{align}The error occurs in the second-last column (K+D=T), which translates to (4+3=9). There are three possible ways to cause this error by changing a single letter:

change the 4 to a 6 (i.e. the K should have been a Y)
change the 3 to a 5 (i.e. the D should have been a B)
change the 9 to a 7 (i.e. the T should have been an H)

If you’re just interested in the answers, here they are:
[Show Solution]

Minimal road networks

This Riddler problem is about efficient road-building!

Consider four towns arranged to form the corners of a square, where each side is 10 miles long. You own a road-building company. The state has offered you \$28 million to construct a road system linking all four towns in some way, and it costs you \$1 million to build one mile of road. Can you turn a profit if you take the job?

Extra credit: How does your business calculus change if there were five towns arranged as a pentagon? Six as a hexagon? Etc.?

Here is a longer explanation:
[Show Solution]

This is actually a famous combinatorial optimization problem with a long history. So rather than attempt to re-invent the wheel, I’ll summarize what is known about the problem and give some pointers to the relevant literature. The problem is known as the Steiner tree problem and shows up, for example, in circuit design. The problem of connecting components on a circuit board using as little wire as possible is precisely the Steiner problem!

In the graph version of the Steiner problem, you have a graph with edge weights (think of the weights as distances) and some of the nodes are labeled as “terminals”. The goal is to find a set of edges that connect all the terminals together. Not all nodes need to be part of the path. This is similar to the minimum spanning tree problem (if all nodes are terminals) or the shortest path problem (if there are only two terminals). Although these simpler variants have polynomial-time algorithms (they’re efficiently solvable), the graph version of the Steiner problem is NP-Hard. So there is likely no efficient algorithm for solving it in general. One thing we know for sure is that the optimal solution should not contain any cycles, because removing an edge from the cycle still connects the same nodes yet has a shorter path. In other words, the solution will always be a tree. This is why it’s called the “Steiner tree problem”.

If we consider the general (non-graph) version of the problem, the solution will still be a tree. A key insight is that we may need to add extra nodes to help make the path shorter. These extra nodes are called Steiner points. For example, consider the equilateral triangle case:

In this case, the version on the left has the shorter path. So we benefit from adding a Steiner point. For an arbitrary triangle, this point is called the Fermat point. The problem gets progressively more difficult as we add more terminal points. The solution for a square involves adding two Steiner points:

Some things are known about more general geometries. The following results, which I will summarize in bullet points, come from a paper from 1930 by Vojtěch Jarník. The paper is open-access so feel free to take a (free) look!

The optimal solution is a tree whose nodes are a combination of the original nodes of the problem as well as some number of Steiner points.
If $S_n$ is the number of Steiner points for the problem with $n$ points, then $0 \le S_n \le n-2$. The actual value of $S_n$ will depend on the particular arrangement of the points.
Every Steiner point has a degree of exactly three. So every Steiner point we add has exactly three roads connecting to it.
The roads that connect to each Steiner point do so at angles of 120 degrees.

The proofs of the last two facts uses contradiction. For example, we might assume that there exists a Steiner point with three roads at angles that are not 120 degrees, and then we show that it’s possible to move that Steiner point slightly and make the total sum of the roads shorter. Therefore, we conclude that the original geometry could not have been optimal.

These facts alone aren’t enough to tell us exactly what the solutions will be, but it can help us narrow down the search! Also, it’s a quick sanity check to see whether a proposed solution can be improved in an obvious way.

Here is the solution with minimal explanation:
[Show Solution]

Counting coconuts

This Riddler problem is about divisibility… of coconuts!

Seven pirates wash ashore on a deserted island after their ship sinks. In order to survive, they gather as many coconuts as they can find and throw them into a central pile. As the sun sets, they all go to sleep.

One pirate wakes up in the middle of the night. Being the greedy person he is, this pirate decides to take some coconuts from the pile and hide them for himself. As he approaches the pile, though, he notices a monkey watching him. To keep the monkey quiet, the pirate tosses it one coconut from the pile. He then divides the rest of the pile into seven equally sized bunches and hides one of the bunches in the bushes. Finally, he recombines the remaining coconuts into a single pile and goes back to sleep. (Note that individual coconuts are very hard, and therefore indivisible.)

Later that night, a second pirate wakes up with the same idea. She tosses the monkey one coconut from the central pile, divides the pile into seven bunches, hides her bunch, recombines the rest, and goes back to sleep. After that, a third pirate wakes up and does the same thing. Then a fourth. Then a fifth, and so on until all seven pirates have hidden a share of the coconuts.

In the morning, the pirates look at the remaining central pile and notice that it has gotten quite small. They decide to split the pile into seven equal bunches and take one bunch each. (Note: The monkey does not get one this time.) If there were N coconuts in the pile originally, what is the smallest possible value of N?

Here is a short solution:
[Show Solution]

If you’d like to learn more about how to solve such problems (what is modular arithmetic anyway!?) then read on!
[Show Solution]

I’ll assume you already read the above solution. In order to understand where the solution comes from, we need to take a brief detour into the world of modular arithmetic…

Detour: modular arithmetic

I’ll illustrate the technique using a simpler example. Let’s find the smallest positive $k$ such that $\frac{5k+2}{3}$ is an integer. Put another way, we want $5k+2$ to be divisible by 3. This is written as:
\[
5k+2 \equiv 0 \pmod{3}
\]The only thing that matters when we’re working “modulo 3” is the remainder upon division by 3. For example, the numbers $\{\dots,-3,0,3,6,\dots\}$ are all equivalent to 0 mod 3 because they are divisible by 3. Likewise, the numbers $\{\dots,-2,1,4,7,\dots\}$ are all equivalent to 1 mod 3 because they have a remainder of 1 (i.e. they are of the form $3k+1$ for some integer $k$). When adding or multiplying numbers together, we can replace them by any equivalent numbers modulo 3 and this doesn’t change the result. So, for example:
\[
5k+2\equiv 0 \pmod{3}
\quad\text{is the same as solving}\quad
2k\equiv 1\pmod{3}
\]Naturally, because we’re working modulo 3, we only need to try $k=\{0,1,2\}$, and we find the solution is $k\equiv 2$. This means, of course, that we could have used any $k$ of the form $3m+2$ and it would have also worked. The smallest positive $k$ is therefore $k=2$, and this works; $5\times 2+2=12$, which is divisible by 3.

Let’s turn our attention to the question of solving $ak\equiv b \pmod{m}$. Here, $a$, $b$, $m$ are fixed, and we want to solve for $k$. This is called a linear congruence equation and it is a well-known concept in number theory. I’ll summarize the key results below.

First, note that there need not be any solutions at all! For example, $5k\equiv 2 \pmod{15}$ clearly has no solution, since $5k$ can only be equal to $\{0,5,10\}$ modulo 15. There can also be multiple solutions. For example, $4k\equiv 2 \pmod{6}$ has solutions $k\equiv 2$ or $k\equiv 5$. In general,

Let $g=\textrm{gcd}(a,m)$ (greatest common divisor). Then the equation $ak\equiv b\pmod{m}$ has a solution if and only if $g$ divides $b$.
If $k_0$ is a particular solution, then there are $g$ solutions in total, given by: $\left\{k_0,\, k_0+\frac{m}{g},\, k_0+\frac{2m}{g},\,\dots,\,k_0+\frac{(g-1)m}{g} \right\}$
The modified equation $(\tfrac{a}{g})k \equiv \tfrac{b}{g} \pmod{\tfrac{m}{g}}$ reduces to the case $g=1$ because $\textrm{gcd}(\tfrac{a}{g},\tfrac{m}{g})=1$ by definition. Consequently this modified equation has a unique solution, which can serve as $k_0$ for the original equation.
To solve the case $g=1$, Bézout’s Identity states that there must exist $s$ and $t$ such that $sa+tm=1$. Then, we have $bsa+btm=b$, which implies that $k_0 = bs$ solves our equation. Bézout’s Identity can be solved via the Extended Euclidean Algorithm.

Back to coconuts!

Our goal was to find the smallest positive integer $k$ such that $N=\frac{5764801 k+3261642}{279936}$ is also an integer. This amounts to solving the linear congruence equation
\[
5764801k+3261642 \equiv 0\pmod{279936}
\]Reducing and rearranging this is equivalent to:
\[
166081k \equiv 97590\pmod{279936}
\]The first thing to observe is that $279936=2^7\cdot 3^7$ whereas $166081$ is a prime number. Therefore, $\mathrm{gcd}(166081,279936)=1$. So we know the linear congruence has a unique solution. The solution to the Bézout Identity can be computed using the Mathematica function:
{g, {s, t}} = ExtendedGCD[166081, 279936].
This yields the result:
\[
(123073)(166081)+(-73017)(279936)=1
\]So the solution is $k\equiv 97590 \cdot 123073 \equiv 39990\pmod{279936}$. We can now compute $N$ as:

$\displaystyle
N=\frac{5764801\cdot 39990 +3261642}{279936} = 823537
$

If we want to find all solutions, we can add multiples of $279936$ to the base $k_0$ we found. This yields a solution set of the form:
\[
N = 823537 + 5764801m\qquad\text{for: }m=0,1,2,\dots
\]

Nightmare Solitaire

This Riddler problem is a probability question about an old favorite: Solitaire!

While killing some time at your desk one afternoon, you fire up a new game of Solitaire (also called Klondike, and specifically the version where you deal out three cards from the deck at a time). But your boredom quickly turns to rage because your game is unplayable — you can flip through your deck, but you never have any legal moves! What are the odds?

Here is my solution:
[Show Solution]

I hope you’re in the mood for some counting! First, the basics: the deck contains 52 cards. Once we deal the cards, there are 7 face-up and 21 face-down. That leaves 24 cards in the deck. If we cycle through the deck 3 cards at a time and don’t play any of them, then we will see the same 8 cards over and over again. So whether a particular instance of Solitaire qualifies as “Nightmare” or not is completely characterized by the 7 face-up cards and the 8 deck cards we get to see.

To compute the probability of dealing a Nightmare game, we’ll count the number of Nightmare games and divide it by the total number of games. When counting, we can restrict our attention to possible choices of the 7+8 cards we see. Of course, the games will play out differently depending on the hidden cards, but these don’t matter for the purpose of counting Nightmare games. Let’s start with the denominator because that’s the easiest thing to calculate:

Total number of games

Since there are 52 total cards, we must choose 7 to be face-up and then choose 8 deck cards. Therefore, the total number of games is:
\[
N_\text{tot} = \binom{52}{7}\binom{52-7}{8} = \frac{52!}{7!\cdot 8!\cdot 37!} = 28,837,689,349,669,200
\]As mentioned earlier, we didn’t distinguish between games where the cards we see are the same but the hidden cards are different. You might be wondering why the total number of games isn’t just $\binom{52}{7+8}$. The reason is that the face-up cards and deck cards are not interchangeable. For example, if you have a face-up $3♣$ and a $\color{red}{4♥}$ in the deck, there are no legal moves. If instead you have a face-up $\color{red}{4♥}$ and a $3♣$ in the deck, you can play the 3 on the 4 when it comes up.

Counting nightmare games

This counting is a bit involved, so we’ll do it in steps. We can partition the cards into two groups:
\begin{align}
\text{Group }1:&\quad \left\{
\begin{array}{rrrrrr}
2♠ & 4♠ & 6♠ & 8♠ & 10♠ & \text{Q}♠ \\
\color{red}{3♥} & \color{red}{5♥} & \color{red}{7♥} & \color{red}{9♥} & \color{red}{\text{J}♥} & \color{red}{\text{K}♥} \\
2♣ & 4♣ & 6♣ & 8♣ & 10♣ & \text{Q}♣ \\
\color{red}{3♦} & \color{red}{5♦} & \color{red}{7♦} & \color{red}{9♦} & \color{red}{\text{J}♦} & \color{red}{\text{K}♦}
\end{array}\right\} \\[3mm]
\text{Group }2:&\quad \left\{
\begin{array}{rrrrrr}
3♠ & 5♠ & 7♠ & 9♠ & \text{J}♠ & \text{K}♠ \\
\color{red}{2♥} & \color{red}{4♥} & \color{red}{6♥} & \color{red}{8♥} & \color{red}{10♥} & \color{red}{\text{Q}♥} \\
3♣ & 5♣ & 7♣ & 9♣ & \text{J}♣ & \text{K}♣ \\
\color{red}{2♦} & \color{red}{4♦} & \color{red}{6♦} & \color{red}{8♦} & \color{red}{10♦} & \color{red}{\text{Q}♦}
\end{array}\right\}
\end{align}These groups were chosen in a particular way: cards from each group can only be played on other cards from the same group. For example, $\color{red}{6♥}$, which is in Group 2, can only be played on $7♠$ or $7♣$, which are also in Group 2. Cards from the two groups never interact with one another. The four aces have been left out because any visible ace (either face-up or in the deck) is always playable. Let’s take it one step at a time.

A 12-card deck, face-up only. Let’s start with a simpler problem. What if the deck only consisted of the top half of Group 1, namely:
\[
\text{Mini-deck}:\quad \left\{
\begin{array}{rrrrrr}
2♠ & 4♠ & 6♠ & 8♠ & 10♠ & \text{Q}♠ \\
\color{red}{3♥} & \color{red}{5♥} & \color{red}{7♥} & \color{red}{9♥} & \color{red}{\text{J}♥} & \color{red}{\text{K}♥}
\end{array}\right\}
\]In this $n$-card deck ($n=12$), how many ways can we choose $k$ face-up cards so that there are no moves available? This is a classic “stars and bars” problem. This is equivalent to counting the subsets of size $k$ such that no two adjacent cards are picked. Since we are choosing $k$ cards, we must exclude $k-1$ buffer cards in between the chosen cards. Therefore, there are $f(n,k) = \binom{n-k+1}{k}$ possible choices.

12-card deck, full version. Using the same mini-deck as above, let’s ask a harder question: How many ways can we choose $k$ face-up cards and $p$ deck cards so that there are no moves available? This is a bit trickier. A card in the deck is playable precisely when it is one less than one of the face-up cards. However, the number of cards that are one less depends on whether we have a face-up $2$ or not (since our deck has no aces). So let’s distinguish two cases:

We have a face-up $2$, which means we can’t use a face-up $3$ either. There are therefore $f(n-2,k-1) = \binom{n-k}{k-1}$ possible choices. There are also $k-1$ cards that are one less than the face-up cards. We must therefore choose our $p$ deck cards from the remaining $n-k-(k-1)$ cards.
We do not have a face-up $2$. There are $f(n-1,k) = \binom{n-k}{k}$ possible choices. There are also $k$ cards that are one less than the face-up cards we chose. We must therefore choose our $p$ deck cards from the remaining $n-2k$ cards.

So in total, there are $\binom{n-k}{k-1}\binom{n-2k+1}{p}+\binom{n-k}{k}\binom{n-2k}{p}$ ways of choosing our $k$ face-up cards and $p$ deck cards in the mini-deck case.

Group 1 deck, full version. Let’s expand our deck to include all the cards from Group 1. Again, we want to pick $k$ face-up cards and $p$ deck cards such that no moves are possible. Let $m$ be how many different card numbers we use (e.g. if we only use 2’s and 6’s, then $m=2$). This is similar to the mini-deck case, except now we’re picking how many different card numbers there will be, and then picking the cards themselves. For example, if we have a face-up $2$, then there are $f(n-2,m-1) = \binom{n-m}{m-1}$ possible choices of for the card numbers. To pick the cards themselves, we must choose $k$ cards from $m$ groups of $2$, with at least one card picked per group. There are $\binom{m}{k-m}$ ways of picking the cards if the cards in each group are indistinguishable, but since they are not, we must also multiply by $2$ for each group that only had one card picked, i.e. $m-(k-m)$. Now for the $p$ deck cards… There were $m$ groups picked (including the groups of two), which means $m-1$ groups are forbidden. They have $2$ cards each, so that’s $2m-2$ cards we can’t use. We started with $2n$ cards and we picked $k$ already. This means we must choose the $p$ deck cards from the remaining $2n-(2m-2)-k$. Putting everything together and including the case with no face-up $2$s, we have:
\begin{multline}
g(n,k,p) = \sum_{m=0}^k \left[ \binom{n-m}{m-1}\binom{2n-2m-k+2}{p}\right.\\
+\left.\binom{n-m}{m}\binom{2n-2m-k}{p} \right] \binom{m}{k-m} 2^{2m-k}
\end{multline}The reason we’re summing over $m$ is because we must account for every possible number of card distinct card number, which naturally can’t exceed $k$. Here, binomial coefficients are being interpreted in the combinatorial sense, so we’re using the convention that $\binom{a}{b} = 0$ if $a\lt 0$, $b\lt 0$, or $b\gt a$.

The full deck. For the full deck, it turns out most of the work has already been done! When combining the cards from Group 1 and Group 2, they don’t ever interact with one another. So ultimately, we just need to decide how many cards from each of the groups we should include in the face-up and deck cards so there are 7 and 8 in total, respectively. The net result is:
\begin{align}
N_\text{nightmare} &= \sum_{i=0}^7 \sum_{j=0}^8 g(12,i,j)\cdot g(12,7-i,8-j) \\
&= 72,099,595,172,416
\end{align}

Taking the ratio $\frac{N_\text{nightmare}}{N_\text{total}}$ and simplifying we obtain our final answer:

$\displaystyle
\mathbb{P}(\text{nightmare game}) = \frac{643746385468}{257479369193475} \approx 0.25\%
$

To get an idea for the size of this number, here is a plot that shows the probability of having had at least one nightmare game given that you’ve played $N$ games in total. In other words, if $p$ is the probability of having a nightmare game, this is a plot of $1-(1-p)^N$.

You would have to play roughly 277 games of solitaire so that the probability of having encountered at least one nightmare game is 50%.

Bonus: alternative rules

If instead we play the variant of Solitaire where you flip only one card at a time, then we can compute the probability of a nightmare game using the same tools as above. The only difference is that we have $24$ deck cards rather than $8$. The probability of a nightmare game using these rules is:
\begin{align}
&\hspace{-1cm}\mathbb{P}(\text{nightmare game, 1-card variant}) \\
&= \frac{ \sum_{i=0}^7 \sum_{j=0}^{24} g(12,i,j)\cdot g(12,7-i,24-j) }{ \binom{52}{7}\binom{52-7}{24} } \\
&= 1.77016\times 10^{-7}
\end{align}The probability is much smaller for this 1-card variant because we see so much more of the deck; a lot more has to “go wrong” to have a nightmare scenario. Here is what the graph looks like for the 1-card variant; it looks similar to the 3-card graph, but shifted far to the right ($N$ is much larger).

To put this in context, when you go from the 3-card variant to the 1-card variant, nightmare games are $14,\!100$ times more unlikely.

Number shuffle

This is a number theory problem from the Riddler. Simple problem, not-so-simple solution!

Imagine taking a number and moving its last digit to the front. For example, 1,234 would become 4,123. What is the smallest positive integer such that when you do this, the result is exactly double the original number?

Here is my solution:
[Show Solution]

Let the digits of the number be $N = d_n d_{n-1} \cdots d_0$, so it’s an $(n+1)$-digit number. Moving the last digit to the front results in the number being doubled. Therefore:
\[
2\cdot (d_n d_{n-1}\cdots d_0) = (d_0 d_n d_{n-1} \cdots d_1)
\]We can write this out mathematically as:
\[
2\cdot(10M + d_0) = 10^n d_0 + M
\]where $M = (d_n d_{n-1}\cdots d_1)$ is an $n$-digit number. Rearranging the equation, we obtain a very telling equation:
\[
19M = (10^n-2)d_0
\]The left-hand side is divisible by $19$, a prime number. Therefore, the right-hand side must also be divisible by $19$. This factor can’t come from $d_0$, which is just a single digit. Therefore, $19$ must divide $10^n-2$.

It turns out the smallest $n$ such that $10^n-2$ is divisible by $19$ is $n=17$. To figure this out easily, we can use modular arithmetic:
\[
10^n \equiv 2 \pmod{19}
\]We can compute powers of $10$ by recursively multiplying by $10$ and subtracting multiples of $19$ until we get a number less than $19$:
\begin{align*}
10^1 &\equiv 10 \pmod{19}\\
10^2 &\equiv 100 \equiv 5 \pmod{19}\\
10^3 &\equiv 50 \equiv 12 \pmod{19}\\
\dots
\end{align*}Of course, the sequence of powers $\{10^0,10^1,10^2,\dots\}\pmod{19}$ must be periodic and there are only $18$ different nonzero integers modulo $19$, so we don’t have to check any more than this before we find or solution (or to conclude that there doesn’t exist one). Here, we find that when $n=17$, then $10^{17}\equiv 2\pmod{19}$ and this doesn’t occur for any smaller $n$. So the set of all possible $n$ is $n=17+18k$ for $k=0,1,\dots$. Since we seek the smallest solution, we’ll work with $n=17$.

Returning to our original equation, $19M=(10^{17}-2)d_0$. Therefore, $M = \tfrac{10^{17}-2}{19}d_0$. Again, we want the smallest $M$ that is $17$-digits long. If we try $d_0=1$, then $M$ is only $16$ digits long. The next possibility is $d_0=2$, and this has the correct number of digits! So the solution is:
\[
N = 10M+d_0 = 20\frac{10^{17}-2}{19}+2=\frac{2\cdot(10^{18}-1)}{19}
\]Calculating this quantity explicitly, we find that the magic number is:

$\displaystyle
N = 105,263,157,894,736,842
$

This is an $18$-digit number. It’s easy to check that when you move the $2$ to the front, you double the original number. This is also the smallest positive number with this property.

The Dodgeball duel

This is a game theory problem from the Riddler. Three dodgeball players, who survives?

Three expert dodgeballers engage in a duel — er, a “truel” — where they all pick up a ball simultaneously and attempt to hit one of the others. Any survivors then immediately start over, attempting to hit each other again. They are equally fast but unequally accurate. Name them Abbott, Bob and Costello. Each has an accuracy of a, b and c, respectively. That is, if Abbott aims at something, he hits it with probability a, Bob with probability b and Costello with probability c. The abilities of each player are known by the others. Let’s say Abbott is a perfect shot: a = 1. Suppose the players follow an optimal strategy, with the goal being survival. Which player, for every possible combination of Bob and Costello’s abilities (b and c), is favored to survive this truel?

Here is my solution:
[Show Solution]

Before I begin, I’d like to thank commenters Guy Moore and Jason Weisman for sharing their own solutions and for pointing out a different way of interpreting the problem. The “Random-ball” variant is due to Guy Moore. Ok, here we go…

What is a solution, anyway?

The problem talks about “optimal strategies”, so it’s worth discussing what this means so we’re all on the same page. An optimal strategy is a Nash equilibrium. It’s a set of strategies for each player such that if any one player changed their strategy (while the others held their strategies fixed), it would result in a worse outcome for that player. Hence, no player has any incentive to change their strategy.

A strategy is a rule that tells you what to do based on what you observe. In this game, an example of a strategy would be “always aim to hit the remaining player with the best accuracy”. This is an example of a pure strategy because each player always behaves the same way no matter what they observe. Not every game is guaranteed to have a Nash equilibrium consisting of pure strategies. In some games, such as rock-paper-scissors, it’s optimal to use a mixed strategy. That is, a probabilistic strategy such as “pick rock paper or scissors randomly and with equal probability”. If you used a pure strategy in rock-paper-scissors, your opponents would counter you and you would lose every time!

It turns out that every finite game has at least one mixed Nash equilibrium. So we need not worry about the case where there is no optimal solution. That being said, it’s entirely possible for there to exist many Nash equilibria! So we shouldn’t be surprised if this turns out to be the case…

Murder-ball vs Coinflip-ball vs Random-ball

There are at least three ways of interpreting the problem. In the first interpretation, if two players target each other and hit, then both players are eliminated. I’ll call this variant “Murder-ball”. In Murder-ball, it’s possible for nobody to win! The second interpretation is that whenever two players hit each other, we should flip a coin and the loser of the coin flip gets eliminated. We also flip a 3-way coin to deal with the case where all three players would be simultaneously eliminated. I’ll call this “Coinflip-ball”. Finally, we could interpret the game as having a randomly chosen shooting order for the players. I’ll call this variant “Random-ball”. In Random-ball, if A hits B and B hits C, but the order is such that A shoots first, then B gets eliminated before shooting C and C survives. All these variants have different solutions!

Two players

Let’s start by considering the case with only two players $P$ and $Q$; a duel! In this case, there are no decisions to make. The players always target each other. Suppose the two players have probabilities of $p$ and $q$ to hit each other, respectively, and we want to figure out the probability that either player will win the duel. In Murder-ball, Player $P$ can only win if he hits $Q$ and $Q$ misses $P$. The probability of this occurring is $p(1-q)$. But if both players miss (probability $(1-p)(1-q)$) then the game repeats. So the chance that $P$ is the ultimate winner is:
\begin{align}
\mathbb{P}_P &= p(1-q)\biggl(1+(1-p)(1-q)+(1-p)^2(1-q)^2+\cdots\biggr) \\
&= \frac{p(1-q)}{1-(1-p)(1-q)}
\end{align}Repeating a similar argument for the other player, we find the probabilities of interest are:
\begin{gather}
\mathbb{P}_P = \frac{p(1-q)}{1-(1-p)(1-q)},
\qquad
\mathbb{P}_Q = \frac{(1-p)q}{1-(1-p)(1-q)}, \\
\qquad
\mathbb{P}_0 = \frac{pq}{1-(1-p)(1-q)}.
\end{gather}Here, $\mathbb{P}_0$ is the probability that the two players simultaneously hit each other, so nobody wins. Naturally, the three probabilities above sum to $1$.

In Coinflip-ball and Random-ball, Player $P$ can also win if both players hit each other but he wins the coin flip. It turns out that in this case, it’s impossible for nobody to win, and $\mathbb{P}_0$ from the solution above gets split evenly between both players.

Three players

I will solve the Murder-ball case in detail. With three players, each has a choice of who to target. We will make no assumptions about the nature of the strategies used, and we will allow for the possibility of using a mixed strategy. An example of a mixed strategy would be “Player $A$ should target $B$ with probability $0.4$ and $C$ with probability $0.6$”. In some games, such as rock-paper-scissors, it’s optimal to use a mixed strategy because if you always did the same thing, your opponents would realize this and you would lose every time! So, let’s define the numbers $x,y,z$ as follows:
\begin{align}
&A\text{ targets }B\text{ with prob }x\text{ and targets }C\text{ with prob }(1-x)\\
&B\text{ targets }C\text{ with prob }y\text{ and targets }A\text{ with prob }(1-y)\\
&C\text{ targets }A\text{ with prob }z\text{ and targets }B\text{ with prob }(1-z)
\end{align}We can compute the probabilities that any player will win by enumerating the possible ways it can happen. I’ll give one example to illustrate. To compute the probability that $A$ wins, it can happen in two main ways:

$B$ and $C$ are eliminated simultaneously and $A$ survives. This can happen in three ways. Either $B$ and $C$ hit each other, or $B$ hits $C$ and $A$ hits $B$, or $C$ hits $B$ and $A$ hits $C$. We can also have everybody survive for some number of rounds first! The total probability is:
\[
\frac{a b (1-c) x y + a (1-b) c (1-x) (1-z) + b c y (1-z)}{1-(1-a)(1-b)(1-c)}
\]
$B$ is eliminated first, and then $A$ wins the duel with $C$ (a case we already solved with $p$ and $q$ above). In any case, $B$ must miss his shot. Either $A$ and $C$ both target $B$ and at least one of them hits, or only one of them targets $B$ and the other misses. The total probability in this case is:
\[
\frac{a(1-c)}{1-(1-a)(1-c)} \frac{(1-b)\left(a (1-c) x + (1-a) c (1-z) + a c x (1-z)\right)}{1-(1-a)(1-b)(1-c)}
\]
$C$ is eliminated first, and then $A$ wins the duel with $B$. This case is similar to the previous one and the total probability is:
\[
\frac{a(1-b)}{1-(1-a)(1-b)} \frac{(1-c)\left(a (1-b) (1-x) + (1-a) b y + a b (1-x) y\right)}{1-(1-a)(1-b)(1-c)}
\]

Summing the three probabilities above, we get $\mathbb{P}_A$, the probability that $A$ wins. We can do a similar computation to get the probability that $B$ wins, that $C$ wins, and that nobody wins (all four probabilities will sum to $1$). By symmetry, the formula for $\mathbb{P}_B$ can be obtained by just cyclically permuting all variables: $a\to b\to c \to a$ and $x \to y \to z \to x$. Finally, the probability that nobody wins is such that all four probabilities sum to one: $\mathbb{P}_0 =1-\mathbb{P}_A-\mathbb{P}_B-\mathbb{P}_C$.

Murder-ball optimal strategies

We now have the probabilities that each player wins, and these are the functions:
\[
\mathbb{P}_A(x,y,z),\quad \mathbb{P}_B(x,y,z),\quad \mathbb{P}_C(x,y,z).
\]Each function is parameterized by $a,b,c$, the accuracy of each player, and is a function of $(x,y,z)$, the (mixed) strategy being used. Our goal is to find a choice of $(x,y,z)$ such that no change in $x$ alone can improve $\mathbb{P}_A$, no change in $y$ alone can improve $\mathbb{P}_B$, and no change in $z$ alone can improve $\mathbb{P}_C$. A key observation that will help us solve the problem is that all three functions are linear in $x$, $y$, and $z$ separately. When optimizing a linear function, the maximum always occurs at a boundary. This implies that there must exist pure Nash equilibria!!! So we can restrict our search to cases where $x$, $y$, and $z$ are each $0$ or $1$. So there are 8 strategies in total.

I computed the Nash equilibria via an exhaustive search. For each value of $(a,b,c)$, I computed the values of $(\mathbb{P}_A,\mathbb{P}_B,\mathbb{P}_C)$ for all 8 strategies, tried changing $(x,y,z)$ for each one to see if it was a Nash equilibrium, and if I found multiple Nash equilibria, I chose one at random. Then, I made a plot illustrating who wins when. When $a=1$, we obtain the following picture:

What a mess! There are many Nash equilibria here, and pretty much anything can happen. The reason is that without a coinflip, the player targeted by Abbott will always lose. So, in fact, anything that player does is optimal! That losing player has a big effect on which remaining player wins, and hence the messy solutions. However, these Nash equilibria are mostly unstable. That is, if we change Abbott’s accuracy to $a=0.99$, the picture changes completely:

Coinflip-ball optimal strategies

I will omit the derivations for Coinflip-ball because the algebra is quite lengthy and tedious to write out, but the idea is similar in spirit to how I derived the probabilities for the Murder-ball variant. As in the Murder-ball case, all probabilities are linear in $(x,y,z)$, so once again, pure Nash equilibria must exist. As above, I used an exhaustive search to plot the probability of winning for each player. Here is what I obtained in the case where $a=1$.

For most of the cases, the strategies are obvious. For example, when $b=0.8$ and $c=0.5$, the optimal strategy is for Abbott and Bob to target each other and for Costello to target Abbott. In this case, it turns out Costello wins most of the time! In the top right corner, you’ll notice that there is a mixture of possible outcomes because there are multiple Nash equilibria there. In that region, all three players are highly accurate and the strategy of ganging up on Abbott is no longer optimal. In this regime, it’s Nash-optimal for the three players to target each other in a chain (A to B to C to A) or (A to C to B to A). This is a result of the rules of the game. In my interpretation of Coinflip-ball, if all three players hit each other simultaneously, the outcome of the game is decided by a coin flip where each player has an equal chance to win.

Random-ball optimal strategies

Again, I omit the derivation. This case yields a solution similar to the other two, where pure Nash equilibria always exist. However, in this case, it’s even nicer: the Nash equilibria are unique! This means there is an unambiguous best strategy for all players. Here is what I obtained in the case where $a=1$.

The uniqueness of the Nash equilibria is reflected in the fact that every region is solid; there is no overlap anywhere.

Inaccurate Abbott

Of course, I had to see what would happen in the case where Abbott is not perfectly accurate. Prepare to have your mind blown…

Here is the case of Coinflip-ball:

You’ll notice that when $a=0$ the optimal solution is just split along the line $b=c$, where the more accurate player wins. This makes sense; Abbott will always lose no matter what he does so it’s up to the remaining two players to duke it out.

Here is the case of Murder-ball:

This time, in the case $a=0$, Bob and Costello are not threatened by Abbott so they target each other. If both Bob and Costello are very accurate, then there is a good chance that they eliminate each other, and in this case Abbott wins!

Finally, here is the case of Random-ball:

Category: The Riddler

The number line game

Computational details

Adding more players

Playing around the clock

Continuous number line

My code

Rug quality control

A coin-flipping game

L-bisector

Smudged secret messages

First problem

Second problem

Summary of solutions

Minimal road networks

Counting coconuts

Detour: modular arithmetic

Back to coconuts!

Nightmare Solitaire

Total number of games

Counting nightmare games

Bonus: alternative rules

Other solutions

Number shuffle

The Dodgeball duel

What is a solution, anyway?

Murder-ball vs Coinflip-ball vs Random-ball

Two players

Three players

Murder-ball optimal strategies

Coinflip-ball optimal strategies

Random-ball optimal strategies

Inaccurate Abbott