The Riddler - Book Proofs

Hanging a picture frame

The following problems appeared in The Riddler. It’s a problem about knots! Or rather, not-knots.

Imagine a framed picture suspended by a cord that’s hanging on two nails. If the picture were hung “normally,” you’d expect the removal of one nail to leave the picture hanging from the other (albeit a bit askew). But how can you hang a picture on two nails so that if you remove either nail the picture will crash to the floor?

What about three nails? What about four nails? What about on two red nails and two blue nails such that the picture falls if both red nails are removed and if both blue nails are removed but remains hanging if one of each color is removed?

Here is my solution for the case of two nails:
[Show Solution]

Here is my solution for the cases of three and four nails:
[Show Solution]

Ostomachion coloring

The following problems appeared in The Riddler. And it features an interesting combination of an ancient game with the four-color theorem.

The famous four-color theorem states, essentially, that you can color in the regions of any map using at most four colors in such a way that no neighboring regions share a color. A computer-based proof of the theorem was offered in 1976.

Some 2,200 years earlier, the legendary Greek mathematician Archimedes described something called an Ostomachion (shown below). It’s a group of pieces, similar to tangrams, that divides a 12-by-12 square into 14 regions. The object is to rearrange the pieces into interesting shapes, such as a Tyrannosaurus rex. It’s often called the oldest known mathematical puzzle.

Your challenge today: Color in the regions of the Ostomachion square with four colors such that each color shades an equal area. (That is, each color needs to shade 36 square units.) The coloring must also satisfy the constraint that no adjacent regions are the same color.

Extra credit: How many solutions to this challenge are there?

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

I’d like to start by pointing out that Hector Pefo also posted a nice solution to this problem. There were also diagrams of solutions posted on Twitter, such as those from @DimEarly and from @chattinthehatt. The solution I’ll describe here is similar to Hector’s, but I’ll explain how to model it as an integer linear program and solve it that way. Of course both solutions produce the same answers (because they’re both correct!) but it’s nice to see different approaches. So without further ado…

Integer linear program

Let’s suppose there are $N$ shapes and we’d like to use $C$ colors. Define:
\[
x_{ij} = \begin{cases}1&\text{if shape }i\text{ is colored using color }j\\0&\text{otherwise}\end{cases}
\]The first constraint is that each shape must be assigned to exactly one color. We can express this algebraically as follows:
\[
\sum_{j=1}^C x_{ij} = 1\qquad\text{for }i=1,\dots,N
\]Now suppose that shape $j$ has area $a_j$. The constraint that each color has an equal share of the area means that the sum of the areas of the shapes of each color must be $A_\text{tot}/C$, where $A_\text{tot}$ is the total area of the Ostomachion. Algebraically, we can write this as:
\[
\sum_{i=1}^N a_i x_{ij} = A_\text{tot}/C\qquad\text{for }j=1,\dots,C
\]Finally, we must deal with the edge constraints. We say that $(p,q)$ is an “edge” if shape $p$ shares an edge with shape $q$. Shapes that share an edge must be different colors. We can encode this algebraically as:
\[
x_{pj} + x_{qj} \le 1\qquad\text{for all edges }(p,q)\text{ and for }j=1,\dots,C
\]And that’s it! We described the feasible set of solutions as the set of matrices $x \in \{0,1\}^{N\times C}$ that satisfy the three sets of linear constraints above. This sort of optimization model is a modified version of a Knapsack problem. More generally, it’s an Integer Linear Program (ILP). Such problems are known to be NP-hard, which roughly means that in the worst-case, there is no efficient way to solve them short of trying all possible colorings. However, modern ILP solvers are quite sophisticated and can usually solve these types of problems very efficiently.

Finding all solutions

When using an ILP model, most commercial solvers are designed to find a single solution. For this problem, we are interested in finding all solutions. One way to get around the limitation is to use Barvinok’s algorithm. One can also use variants of branch-and-cut. Yet another way, which is not as systematic but much easier to explain and implement, is to use a randomized approach.

Since all our variables are binary (0 or 1), the convex hull of the feasible set cannot contain any interior solution points. All solutions will be on the boundary. This means that any solution can be found by specifying the right objective function for the optimization. As stated, our optimization is just a feasibility problem and there is no objective specified. For this problem, we start by letting $r_{ij}$ be random numbers (we can draw them i.i.d. from a standard normal distribution, for example). Then, we simply add the objective function:
\[
\text{Minimize}\qquad \sum_{i=1}^N\sum_{j=1}^C r_{ij} x_{ij}
\]and solve the problem. If we do this repeatedly with different realizations of the $\{r_{ij}\}$, we will eventually enumerate all possible solutions of the optimization problem.

To jump straight to the solution (and pretty pictures!) see below.
[Show Solution]

Inscribed triangles and tetrahedra

The following problems appeared in The Riddler. They involve randomly picking points on a circle or sphere and seeing if the resulting shape contains the center or not.

Problem 1: Choose three points on a circle at random and connect them to form a triangle. What is the probability that the center of the circle is contained in that triangle?

Problem 2: Choose four points at random (independently and uniformly distributed) on the surface of a sphere. What is the probability that the tetrahedron defined by those four points contains the center of the sphere?

Here is my solution to both problems:
[Show Solution]

This problem also appeared as Problem A-6 in the 1992 William Lowell Putnam math competition. After writing this blog post, I also discovered an amazing video about this problem by @3Blue1Brown. The video is exceptionally clear and well-produced; I highly recommend it! The solution I present below is similar to the one in the video, except that I also included a section at the end that provides more mathematical details.

Both the 2D and 3D versions of the problem can be solved in a similar fashion, using the same key observation. I will point out this observation and then prove it mathematically. We’ll start with the first problem because it’s a bit simpler, but the logic is the same for both.

Problem 1: triangle and circle

Instead of picking three points on the circle at random, the symmetry in the problem allows us (without any loss of generality) to fix the first point and then pick the remaining two uniformly at random. Let’s suppose that the first point is fixed to be at the top of the circle. For the two remaining points, each one has a “mirror point” that lies directly opposite it on the other side of the circle. In mathspeak, a point and its mirror point are said to be diametrically opposed.

Since the points on the circle are chosen uniformly at random, each point is as likely to be chosen as its diametrically opposed counterpart. Therefore, instead of picking the remaining two points uniformly at random, we’ll do the following equivalent thing:

Pick two lines through the center of the circle uniformly at random.
For each line, pick one of its two endpoints at random.

For each choice of two diameters ($BB’$ and $CC’$), there are four possible triangles we can make depending on which endpoints of the diameters are chosen: $ABC$, $AB’C$, $ABC’$, and $AB’C’$. Here is a diagram illustrating the choices of triangles.

One of the four triangles contain the center point $O$. This is no accident! No matter which two diameters $BB’$ and $CC’$ we select, exactly one of the four resulting triangles will contain the center point $O$ almost surely. Moreover, each of these four triangles is equally likely because each choice of endpoint ($B$ or $B’$ and $C$ or $C’$) is equally likely. It follows that the probability that the triangle will contain the center point $O$ is $\frac{1}{4}$.

Problem 2: tetrahedron and sphere

For this problem, we can apply the exact same logic as in the 2D case: fix one point to be at the top of the sphere and select the remaining three points by first picking three diameters at random, and then for each diameter choosing one of its endpoints at random. Once again, it turns out that exactly one of the 8 possible tetrahedra will contain the center of the sphere. Each triangle is equally likely, so the probability that the random tetrahedron contains the center of the sphere is $\frac{1}{8}$.

Mathematical proof

The results above rely on the observation that exactly one of the 4 triangles (in the 2D case) or one of the 8 tetrahedra (in the 3D case) contains the center of the circle or sphere. We will now prove this fact more rigorously by using the notion of barycentric coordinates. Suppose the vertices of the tetrahedron are located at $\vec{p}$, $\vec{q}$, $\vec{r}$, $\vec{s}$. Given a point $\vec{x}$ (not necessarily on the surface of the sphere), we can represent it as a linear combination:
\[
\vec{x} = \lambda_1 \vec{p} + \lambda_2 \vec{q} + \lambda_3 \vec{r} + \lambda_4 \vec{s}
\]The quadruple $(\lambda_1,\lambda_2,\lambda_3,\lambda_4)$ are the barycentric coordinates of $\vec{x}$ with respect to the tetrahedron. This representation is not unique, but it becomes unique if we add a normalizing constraint such as $\lambda_1+\lambda_2+\lambda_3+\lambda_4=1$. A key property of barycentric coordinates is that $\vec{x}$ lies inside the tetrahedron if and only if all coordinates have the same sign. The reason is that the interior of the tetrahedron is also the convex hull of its vertices.

We can use the property above to solve our problem. Let $\vec{o}$ be the center of the sphere and suppose it’s located at the origin. This means that the point diametrically opposed to any point $\vec{y}$ is simply $-\vec{y}$. As before, we’ll fix $\vec{p}$. The 8 possible (equally likely) tetrahedra are formed by using the vertices:
\[
\vec{p}
\quad\text{and}\quad
(\vec{q}\text{ or }-\vec{q})
\quad\text{and}\quad
(\vec{r}\text{ or }-\vec{r})
\quad\text{and}\quad
(\vec{s}\text{ or }-\vec{s})
\]We want to test whether $\vec{x}=\vec{o}$ is inside the tetrahedron or not. Therefore, the 8 equations we should solve for the 8 possible tetrahedra are:
\begin{align}
\vec{o} &= \lambda_1 \vec{p}+\lambda_2 \vec{q}+\lambda_3 \vec{r}+\lambda_4 \vec{s}, &
\vec{o} &= \lambda_1 \vec{p}+\lambda_2 \vec{q}+\lambda_3 \vec{r}-\lambda_4 \vec{s}, \\
\vec{o} &= \lambda_1 \vec{p}+\lambda_2 \vec{q}-\lambda_3 \vec{r}+\lambda_4 \vec{s}, &
\vec{o} &= \lambda_1 \vec{p}+\lambda_2 \vec{q}-\lambda_3 \vec{r}-\lambda_4 \vec{s}, \\
\vec{o} &= \lambda_1 \vec{p}-\lambda_2 \vec{q}+\lambda_3 \vec{r}+\lambda_4 \vec{s}, &
\vec{o} &= \lambda_1 \vec{p}-\lambda_2 \vec{q}+\lambda_3 \vec{r}-\lambda_4 \vec{s}, \\
\vec{o} &= \lambda_1 \vec{p}-\lambda_2 \vec{q}-\lambda_3 \vec{r}+\lambda_4 \vec{s}, &
\vec{o} &= \lambda_1 \vec{p}-\lambda_2 \vec{q}-\lambda_3 \vec{r}-\lambda_4 \vec{s}.
\end{align}But these equations have very similar solutions! Indeed, if $(\lambda_1,\lambda_2,\lambda_3,\lambda_4)$ solves the first equation, then the solutions to the equations above are:
\begin{align}
&(\lambda_1,\lambda_2,\lambda_3,\lambda_4), &
&(\lambda_1,\lambda_2,\lambda_3,-\lambda_4), \\
&(\lambda_1,\lambda_2,-\lambda_3,\lambda_4), &
&(\lambda_1,\lambda_2,-\lambda_3,-\lambda_4), \\
&(\lambda_1,-\lambda_2,\lambda_3,\lambda_4), &
&(\lambda_1,-\lambda_2,\lambda_3,-\lambda_4), \\
&(\lambda_1,-\lambda_2,-\lambda_3,\lambda_4), &
&(\lambda_1,-\lambda_2,-\lambda_3,-\lambda_4),
\end{align}respectively. It’s clear that exactly one of these quadruples has all entries with the same sign. In other words, exactly one of the 8 tetrahedra contains the center of the sphere. The argument above also works in the 2D case using a similar notion of 2D barycentric coordinates.

Where will the seven dwarfs sleep tonight?

The following problem appeared in The Riddler. It’s an interesting recursive problem.

Each of the seven dwarfs sleeps in his own bed in a shared dormitory. Every night, they retire to bed one at a time, always in the same sequential order, with the youngest dwarf retiring first and the oldest retiring last. On a particular evening, the youngest dwarf is in a jolly mood. He decides not to go to his own bed but rather to choose one at random from among the other six beds. As each of the other dwarfs retires, he chooses his own bed if it is not occupied, and otherwise chooses another unoccupied bed at random.

What is the probability that the oldest dwarf sleeps in his own bed?
What is the expected number of dwarfs who do not sleep in their own beds?

Here is my solution.
[Show Solution]

We’ll solve the problem in full generality and suppose $n$ is the total number of dwarfs (dwarves?). Let’s begin by numbering the dwarfs and their corresponding beds $1,2,\dots,n$, where dwarf $1$ is the first to go bed and dwarf $n$ is the last. Let’s also define:
\begin{align}
a\to b &= \text{The event that dwarf }a\text{ sleeps in bed }b.\\
\neg k &= \text{The event that dwarf }k\text{ does not sleep in their own bed.} \\
&= \text{The event that bed }k\text{ is occupied when dwarf }k\text{ goes to bed.}
\end{align}Note the two equivalent definitions for $\neg k$, since the dwarfs always prefer to sleep in their own beds. A dwarf does not sleep in their own bed precisely when their bed is occupied at bedtime.

If any dwarf except the first dwarf does not sleep in their own bed, it must be that another dwarf is already sleeping there. Therefore, we have:
\begin{align*}
\mathbb{P}(\neg k) &= \mathbb{P}(1\to k \text{ or } 2\to k \text{ or } \dots \text{ or } k-1\to k) \\
&= \sum_{i=1}^{k-1} \mathbb{P}(i\to k)\qquad\text{for }k=2,\dots,n
\end{align*}The probabilities simply sum together because they represent mutually exclusive events; two dwarfs can’t both be sleeping in the same bed. Next, observe that:
\begin{align*}
\mathbb{P}(a \to b) &= \mathbb{P}( a \to b \,\vert\, \neg a )\, \mathbb{P}( \neg a )\\
&= \frac{1}{n-a+1}\mathbb{P}(\neg a) \qquad\text{for }a=2,\dots,b-1
\end{align*}This follows because when a dwarf doesn’t sleep in their own bed, it’s always because their bed is occupied. The conditional probability evaluates to $\frac{1}{n-a+1}$ because by the time dwarf $a$ goes to bed, there are already $a-1$ dwarfs in bed, so there are only $n-a+1$ beds left to choose from.

It remains to set the initial condition. According to the problem statement, the first dwarf always sleeps in the wrong bed. Therefore, $\mathbb{P}(\neg 1) = 1$ and $\mathbb{P}(1\to b) = \frac{1}{n-1}$ for $b=2,\dots,n$. Substituting into the above, we can write a clean expression for the recursion and its initial condition:
\begin{align}
\mathbb{P}(\neg 1) &= 1 \\
\mathbb{P}(\neg k) &= \frac{1}{n-1} + \sum_{i=2}^{k-1} \frac{1}{n-i+1}\mathbb{P}(\neg i) \qquad\text{for }k=2,\dots,n
\end{align}This isn’t bad, but we can do better! By taking a second difference, we can formulate an equivalent recursion that doesn’t require a sum over all terms. For convenience, let’s define $p(k) = \mathbb{P}(\neg k)$. Substituting the above equations into $p(k+1)-p(k)$ and simplifying, we obtain:
\begin{align}
p(1) &= 1,\quad p(2) = \tfrac{1}{n-1}\\
p(k+1) &= \left(1+\tfrac{1}{n-k+1}\right)p(k)\qquad\text{for }k=2,\dots,n
\end{align}The recurrence is a telescoping product that we can solve explicitly:
\begin{align}
p(1) &= 1\\
p(k) &= \frac{n}{(n-1)(n-k+2)}\qquad\text{for }k=2,\dots,n
\end{align}Now that we have a closed-form expression for $p(k)$, we can answer just about any question about the dwarfs and their sleeping situation.

Problem 1

Back to the problems! The first question was to find the probability that the oldest dwarf sleeps in his own bed. This is simply $1-p(n)$. Therefore, the probability that the oldest dwarf sleeps in his own bed is $\frac{n-2}{2(n-1)}$, or $\frac{5}{12}\approx 41.67\%$ in the case where $n=7$.

This gets interesting if we look at other values of $n$. When $n=1$, the quantity is rightfully undefined. When $n=2$, the probability is zero. This makes sense because with only two dwarfs, the first dwarf always sleeps in the oldest dwarf’s bed, so the oldest dwarf never sleeps in his own bed. As $n\to\infty$, the probability tends to $\frac{1}{2}$. With a bit more algebra, we can deduce that with a large number of dwarfs, the $(n-p)^\text{th}$ dwarf sleeps in his own bed with a probability of $\frac{p+1}{p+2}$. i.e. the second oldest sleeps in his own bed with probability $\frac{2}{3}$, the third oldest with probability $\frac{3}{4}$, and so on.

Problem 2

The second problem asks for the expected number of dwarfs that do not sleep in their own beds. Let’s call this quantity $E_n$. Define
\[
Y_k = \begin{cases}1 & \text{if }\neg k\\0 & \text{otherwise}\end{cases}
\]In other words, $Y_k$ counts whether the $k^\text{th}$ dwarf doesn’t sleep in their own bed. The total number of dwarfs that do not sleep in their own bed is $Y_1+\dots+Y_n$. Therefore, by linearity of expectation, we have:
\begin{align}
E_n &= \mathbb{E}(Y_1+\dots+Y_n) \\
&= \sum_{k=1}^n \mathbb{E}(Y_k) \\
&= \sum_{k=1}^n \mathbb{P}(\neg k) \\
&= 1+\sum_{k=2}^n \frac{n}{(n-1)(n-k+2)} \\
&= 1+\frac{n}{n-1} \left( \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} \right)
\end{align}Therefore, when $n=7$, the expected number of dwarfs that do not sleep in their own beds is $E_7 = \frac{343}{120}\approx 2.8583$.

Looking at extremes once again, when $n=2$, we have $E_2=2$. This makes sense because with two dwarfs, both always sleep in the wrong bed, so the number of dwarfs not sleeping in their own bed is always exactly $2$. As $n\to\infty$, we can obtain lower and upper bounds for $E_n$ by using the logarithmic approximation to the harmonic series:
\[
\tfrac{n}{n-1}\log(n+1)-\tfrac{1}{n-1} < E_n < \tfrac{n}{n-1}\log(n)+1 \]Therefore $E_n$ grows like $\log(n)$ as $n\to\infty$. If we want an asymptotically tight approximation instead, we can write: \[ E_n \approx \log(n)+\gamma \]Where $\gamma \approx 0.5772$ is the Euler–Mascheroni constant.

Cracking the safe

The following problem appeared in The Riddler and it’s about finding the right code sequence to crack open a safe.

A safe has three locks, each of which is unlocked by a card, like a hotel room door. Each lock (call them 1, 2 and 3) and can be opened using one of three key cards (A, B or C). To open the safe, each of the cards must be inserted into a lock slot and then someone must press a button labeled “Attempt To Open.”

The locks function independently. If the correct key card is inserted into a lock when the button is pressed, that lock will change state — going from locked to unlocked or unlocked to locked. If an incorrect key card is inserted in a lock when the attempt button is pressed, nothing happens — that lock will either remain locked or remain unlocked. The safe will open when all three locks are unlocked. Other than the safe opening, there is no way to know whether one, two or all three of the locks are locked.

Your job as master safecracker is to open the locked safe as efficiently as possible. What is the minimum number of button-press attempts that will guarantee that the safe opens, and what sequence of attempts should you use?

Here is my solution.
[Show Solution]

I don’t believe there is an efficient way to solve the problem (read: polynomial time), but there are efficient ways to search the space of solutions and techniques we can use to make an exhaustive search more tractable. This problem sits nicely at the boundary between what is solvable vs unsolvable via brute force. So without further ado…

Encoding the state of the safe

First, we have to specify what it is we’re searching over. There are six possible safes, which correspond to the six permutations of (A,B,C). They are: {ABC,ACB,BAC,BCA,CAB,CBA}. Each permutation indicates which key opens which lock. For example, “BAC” is a safe where lock 1 is opened by key B, lock 2 is opened by key A, and lock 3 is opened by key C. The safe can also be in one of 8 different states, which correspond to whether each lock is currently open or closed. We can write these as binary numbers: {000,001,010,011,100,101,110,111}. For example, “010” is a safe where lock 2 is unlocked and locks 1 and 3 are locked.

Every time we make a move, we choose some assignment of the keys (A,B,C) to the locks (1,2,3). There are six possible moves we can make, which correspond to permutations of (A,B,C) as before: {ABC,ACB,BAC,BCA,CAB,CBA}. Given a hypothetical sequence of moves, we can track what happens by computing the state of the safe for each of its possible starting configurations. A simple way to track is to make a table, which I will illustrate using an example. If our safe is the “ABC” safe, and we apply the sequence of moves: ABC,CBA,BCA. The table looks like:

ABC safe	000	001	010	011	100	101	110	111
ABC (111)	111	110	101	100	011	010	001	000
CBA (010)	101	100	111	110	001	000	011	010
BCA (000)	101	100	111	110	001	000	011	010

First move (ABC): We start with a row that contains every possible state. Applying the move “ABC” will toggle all the locks, since we are working with the safe “ABC” (all keys are correct). This is equivalent to XORing the current state with the bitstring “111”. In effect, every 0 becomes 1 and vice versa, which leads us to the second row. Note that the “000” state became “111”, so the safe is opened! For the other seven initial states, the safe remains locked but is now in a different state.

Second move (CBA): this move corresponds to an XOR with “010” since only the B is in the correct position. So the third row is produced by only toggling the middle bit of the states in the second row. Here, we see that the initial state “010” leads to an open safe after the second move.

Third move (BCA): This move accomplishes nothing since none of the letters are in the correct position (XOR with “000”).

For each of the six possible safes, we can make such a table, track the evolution of each of the 8 states as the sequence of moves is applied, and keep track of which columns eventually achieve a “111” (opened safe). Each safe responds differently because the keys are matched differently to the locks. For example, if we apply the same sequence of moves to the “BAC” safe instead, we obtain:

BAC safe	000	001	010	011	100	101	110	111
ABC (001)	001	000	011	010	101	100	111	110
CBA (000)	001	000	011	010	101	100	111	110
BCA (100)	101	100	111	110	001	000	011	010

So, given a sequence of moves, we can evaluate how it affects each of the 48 possible initial states (6 safes x 8 states per safe) by computing six tables like the ones above, and then counting which columns contain “111” (the safe was opened). We can exclude the safes that start in the “111” position (safe is already open), so we only need to check 42 possible states.

Brute-force search

The next step is to exhaustively check all possible sequences of moves, starting with shorter sequences and progressively making them longer until we find a way to make all 42 initial states eventually contain “111”. Such a search can be computationally difficult because of the “curse of dimensionality”. For example, there are $6^{12} \approx 2.18\times 10^9$ different sequences of length 12. There are several tricks we can use to reduce this burden and make the search more tractable. Here are the tricks I used:

Symmetry: since all possible permutations of labels are present and all possible moves are permitted, we may assume without loss of generality that the first move is “ABC”.
Repetition: there is never a reason for two consecutive moves to be the same, since this will simply undo what the previous move accomplished. So each time we add an extra move to the sequence, we only need to consider 5 of the 6 possible choices.
Give up when there is no hope: we start with 42 possible states, and each time we make a move, some of those states get solved (the safe opens). But there are limits. Each safe starts in one of 7 different states. Each time we make a move, the states remain distinct. This means each move opens at most one state per safe. Moreover, no matter which move we make, two of the safes will be unchanged (e.g. the move “ABC” does not affect safes “BCA” and “CAB” because none of the keys match). Consequently, each move can crack at most 4 of the 42 states. This observation allows us to stop our search early if the first several moves aren’t good enough. For example, if we are testing sequences of length 12 and the first 8 moves crack 25 of the 42 states, then we must crack the remaining 17 states in the 4 moves we have left. This is impossible since we can crack at most 16 states in 4 moves. So these first 8 moves can’t be right and we can move on.

Using the strategies above, the 2 billion possible sequences reduces to a mere 1080, a very manageable quantity. After performing the search, I found a winning sequence of length 12:

{ABC,BCA,CAB,ABC,BCA,ABC,ACB,BAC,ACB,CBA,BAC,ACB}.

The search also reveals that it’s impossible to crack all 42 states in 11 moves, so 12 is the best we can do. Finding such a winning sequence is challenging to do without a computer. Two observations:

It’s easy to shoot yourself in the foot by making a wrong move early. For example, if you start with {ABC,BAC,…} then it’s already impossible to solve the problem in 12 moves!
Greedy strategies don’t work! Looking for maximal moves at every step (crack as many safes as possible all the time) turns out to be suboptimal. While such strategies lead to good initial progress, it is short lived and you end up needing far more than 12 moves to cover all cases.
If we interpret the question to mean that the safe may be initially unlocked (starts in a “111” state) but we have no way of knowing so because we still need to open it somehow and we don’t know which keys to use, then there are now 48 possible safes and 12 moves is no longer sufficient. Using a similar approach again, we find that it can be solved with a sequence of length 13: {ABC,ABC,BCA,CAB,ABC,BCA,ABC,ACB,BAC,ACB,CBA,BAC,ACB}. This sequence is the official solution that was posted on the Riddler blog.

Finding the doctored coin

This Riddler puzzle is about repeatedly flipping coins!

On the table in front of you are two coins. They look and feel identical, but you know one of them has been doctored. The fair coin comes up heads half the time while the doctored coin comes up heads 60 percent of the time. How many flips — you must flip both coins at once, one with each hand — would you need to give yourself a 95 percent chance of correctly identifying the doctored coin?

Extra credit: What if, instead of 60 percent, the doctored coin came up heads some P percent of the time? How does that affect the speed with which you can correctly detect it?

Here is my solution.
[Show Solution]

The first thing to realize about this problem is that the answer depends on how the coin flips turn out. For example, suppose that after $n$ flips, both coins came up heads an equal number of times. This is unlikely, but nonetheless it’s possible. We obviously can’t conclude anything about the coins in such a case. So the answer can’t depend only on $n$.

The coin flips are independent. So if a coin comes up heads with probability $p$ and we flip it $n$ times, the probability that it comes up heads exactly $k$ times is given by a Binomial distribution:
\[
B(n,p,k) = {n \choose k} p^k (1-p)^{n-k}
\]Let’s say the coins are numbered 1 and 2 and their probabilities of coming up heads are $p_1$ and $p_2$ respectively.

Now for the experiment: we flip each coin $n$ times and record how many times they come up heads (but we don’t know which coin is which). Let’s say they come up heads $k_1$ and $k_2$ times for the left and right coin respectively. Let’s call the data we observed $k$. There are two possible scenarios:

Coin 1 was in the left hand (and Coin 2 was in the right hand). We’ll call this scenario $\theta_1$. The likelihood of this scenario occurring is:
\[
\mathbb{P}(k\mid \theta_1) = B(n,p_1,k_1) B(n,p_2,k_2)
\]
Coin 1 was in the right hand (and Coin 2 was in the left hand). We’ll call this scenario $\theta_2$. The likelihood of this scenario occurring is:
\[
\mathbb{P}(k\mid \theta_2) = B(n,p_1,k_2) B(n,p_2,k_1)
\]

These are the only possible scenarios. If we want to be confident with level $\alpha$ about one of the scenarios then the posterior probability must be greater than $1-\alpha$. In other words:

If $\mathbb{P}(\theta_1\mid k) > 1-\alpha$, then we are confident in Scenario 1.
If $\mathbb{P}(\theta_2\mid k) > 1-\alpha$, then we are confident in Scenario 2.

Note that by definition, $\mathbb{P}(\theta_1\mid k)+\mathbb{P}(\theta_2\mid k) = 1$ for all $k$. So the two cases above can’t simultaneously be true when $\alpha\lt\tfrac{1}{2}$. We can compute posterior probability by using Bayes’ rule:
\[
\mathbb{P}(\theta_1\mid k) = \frac{\mathbb{P}(k\mid \theta_1)\mathbb{P}(\theta_1)}{\mathbb{P}(k\mid \theta_1)\mathbb{P}(\theta_1)+\mathbb{P}(k\mid \theta_2)\mathbb{P}(\theta_2)}
\]It is reasonable to assume that scenarios $\theta_1$ and $\theta_2$ have the same prior probability. So $\mathbb{P}(\theta_1)=\mathbb{P}(\theta_2)=\tfrac{1}{2}$. Therefore, our condition for confidence simplifies to:
\[
\frac{\mathbb{P}(k\mid \theta_1)}{\mathbb{P}(k\mid \theta_1)+\mathbb{P}(k\mid \theta_2)} > 1-\alpha
\quad\text{or}\quad
\frac{\mathbb{P}(k\mid \theta_2)}{\mathbb{P}(k\mid \theta_1)+\mathbb{P}(k\mid \theta_2)} > 1-\alpha
\]Rearranging these inequalities, we have:
\[
\frac{\mathbb{P}(k\mid \theta_1)}{\mathbb{P}(k\mid \theta_2)} > \frac{1-\alpha}{\alpha}
\quad\text{or}\quad
\frac{\mathbb{P}(k\mid \theta_2)}{\mathbb{P}(k\mid \theta_1)} > \frac{1-\alpha}{\alpha}
\]If we take logs of both sides, we can combine the expressions into a single inequality involving the difference of log-likelihoods, namely:
\[
\bigl|\, \log \mathbb{P}(k\mid \theta_1)-\log \mathbb{P}(k\mid \theta_2)\, \bigr| > \log\left(\tfrac{1}{\alpha}-1\right)
\]This has a nice interpretation: we can stop flipping coins once the difference between log-likelihoods grows sufficiently large. The smaller we make $\alpha$, the larger the difference in log-likelihoods must be before we can declare that we are confident.

We can simplify the expression considerably by substituting the definitions for the likelihoods $\mathbb{P}(k\mid \theta_1)$ and $\mathbb{P}(k\mid \theta_2)$ in terms of the $B(\cdot)$ functions, and substituting the binomial probability mass functions. Doing this, we obtain the simpler expression:
\[
|k_1-k_2| \left|\, \log \left( \tfrac{1}{p_1}-1 \right)-\log\left(\tfrac{1}{p_2}-1\right) \,\right| > \log\left(\tfrac{1}{\alpha}-1\right)
\]Note that $p_1$, $p_2$, $\alpha$ are parameters of the problem. The only part that change from case to case is $k_1$ and $k_2$. While it is customary to use a normal approximation when dealing with binomial distributions, doing so actually produces a more complicated formula, so we stick with binomials. The dependence on $n$ becomes evident if we express this formula in terms of the empirical probabilities $\hat p_1 := k_1/n$ and $\hat p_2 := k_2/n$. We obtain:

$\displaystyle
n \,>\, \frac{1}{|\hat p_1-\hat p_2|} \frac{\log\left(\frac{1}{\alpha}-1\right)}{\left|\, \log(\tfrac{1}{p_1}-1)-\log(\tfrac{1}{p_2}-1) \,\right|}
$

This is exactly the sort of expression we’re after — a lower bound on the number of samples required. This result agrees with our initial intuition: if $\hat p_1-\hat p_2 \to 0$, then $n\to \infty$. If the proportion of heads for both coins is the same, then we can’t possibly infer anything!

Expected solution. The number of flips required will be different depending on how the flips turn out. One way to get a numerical solution is to assume that the empirical probabilities match the true probabilities. In this case, we can substitute the values $\hat p_1 = p_1=0.5$, $\hat p_2 = p_2=0.6$, and $\alpha=0.05$ into the formula above, and we obtain $n \approx 73$.

We can also simulate: generate random coin flips, compute empirical probabilities, and record how many flips were required to satisfy the 95% criterion. Then repeat many times and plot the distribution of stopping times. Here is what you get when you do this with 10,000 trials.

This distribution is very broad; sometimes only a dozen flips are required, other times over 300 flips are required. But the mean of the distribution (indicated in red) is close to our approximation of 73.

Varying the probability. We can also see what happens to the mean stopping time as we change the probability. Here, I assumed that $\hat p_1 = p_1 = 0.5$ and I plotted the average number of flips required to achieve 95% confidence as a function of $p_2$. Here is what I got:

As $p_2$ gets closer to $0.5$ (which is the value of $p_1$), it takes more and more flips to be able to tell the coins apart.

Sticks in the woods

This Riddler puzzle is about making triangles out of sticks! Here is the problem:

Here are four questions about finding sticks in the woods, breaking them, and making shapes:

If you break a stick in two places at random, forming three pieces, what is the probability of being able to form a triangle with the pieces?
If you select three sticks, each of random length (between 0 and 1), what is the probability of being able to form a triangle with them?
If you break a stick in two places at random, what is the probability of being able to form an acute triangle — where each angle is less than 90 degrees — with the pieces?
If you select three sticks, each of random length (between 0 and 1), what is the probability of being able to form an acute triangle with the sticks?

For the tl;dr, here are the answers:
[Show Solution]

Here are detailed solutions to all four problems (with cool visuals!):
[Show Solution]

Problem 1

Given three lengths $a,b,c$, when can they form a triangle? When they satisfy the triangle inequality! In other words, whenever:
\[
a+b > c
\quad\text{and}\quad
b+c > a
\quad\text{and}\quad
c+a > b
\]This makes sense when you think about it; if one of these inequalities were to be false, then one length would be longer than the sum of the other two, so no triangle would be possible.

Let’s say the stick has length 1, and it is broken at locations $a$ and $b$ (measured from the same side). We’ll assume that “broken at random” means that $a$ and $b$ are uniformly and independently distributed random variables on $[0,1]$. By symmetry, the cases $a\lt b$ and $b \lt a$ occur with equal probability and have the same probability of producing triangles, so let’s assume $a\lt b$. The three sidelengths are $(a, b-a, 1-b)$. Writing out the three triangle inequalities, we have:
\[
b > \tfrac{1}{2}
\quad\text{and}\quad
a < \tfrac{1}{2} \quad\text{and}\quad b-a < \tfrac{1}{2} \]Since $a$ and $b$ are uniform random variables, we can think of each $(a,b)$ as the coordinates of a point in the square $0 \le a \le 1$ and $0 \le b \le 1$. The probability we seek is precisely the area of the points satisfying our constraints. If we plot these points (and include the mirror case where $b \lt a$ as well), here is the figure we obtain:

We can see by inspection that the shaded area is $\tfrac{1}{4}$ of the total area. So the probability of forming a triangle by breaking a stick into three pieces is 25%.

Problem 2

In this version, we’re still trying to make a triangle, so we must enforce the same triangle inequalities as in Problem 1. In this version, however, we choose three sticks of lengths $a,b,c$ and each length is an independent random variable in the interval $[0,1]$. In this case, it is equally likely that $a$, $b$, or $c$ is largest. We’ll assume without loss of generality that $c$ is largest. In this case, we only need to worry about one of the triangle inequalities, so we have:
\[
a < c \quad\text{and}\quad b < c \quad\text{and}\quad c < a+b \] Here is what it looks like when we plot the first two inequalities (in pale yellow) and then the subset of that region that also satisfies the third inequality (in dark yellow).

It’s clear that the dark region has half the volume of the entire region, so the probability that the three pieces will form a triangle is $\tfrac{1}{2}$. We can also fill the rest of the cube by symmetry, and we obtain:

If you stare at this long enough, you realize that it’s just three identical copies of the previous region glued together (so the pale yellow is now the entire cube), so this shape again has half the volume of the entire cube. In summary, the probability of forming a triangle with three randomly chosen lengths is 50%.

Problem 3

Things start to get more complicated here. We’d like to make not just a triangle, but an acute triangle. This means that each interior angle must be less than 90 degrees. If the side lengths are $a,b,c$, we have from the law of cosines that $\cos(C) = \tfrac{a^2+b^2-c^2}{2ab}$ where $C$ is the angle opposite side $c$. If we want $0\le C \le \tfrac{\pi}{2}$, then we should choose $\cos(C)\ge 0$. This holds for all three angles, so we must have:
\[
a^2+b^2 > c^2
\quad\text{and}\quad
b^2+c^2 > a^2
\quad\text{and}\quad
c^2+a^2 > b^2
\]It turns out that these inequalities imply the triangle inequalities. Take the first one for example:
\[
c < \sqrt{a^2+b^2} < \sqrt{a^2+2ab+b^2} = a+b \]So we don't need to include the original triangle inequalities when we use these quadratic inequalities instead. Here is what the figure looks like when we plot all the inequalities and then mirror the image for the case $b\lt a$:

This is a much more complicated shape than what we had before. We’ll compute its area by computing the areas of the complementary pieces, pictured below:

Each of the four blue regions have equal area by symmetry. One of them is given by the inequalities:
\[
(1-b)^2 \ge (b-a)^2 + a^2
\quad\text{and}\quad
0 \le a \le \tfrac{1}{2}
\quad\text{and}\quad
b \ge \tfrac{1}{2}
\]Solving the first inequality for $b$, the boundary is given by: $b=\frac{1-2a^2}{2(1-a)}$. Therefore, we can compute one of the blue areas by evaluating the integral:
\[
A_\text{blue} = \int_{0}^{1/2} \left(\frac{1-2a^2}{2(1-a)}-\frac{1}{2}\right)\,\mathrm{d}a=\frac{3}{8}-\frac{1}{2}\log(2)
\]We can use a similar approach for each of the yellow regions, and we find:
\[
A_\text{yellow} = \int_{1/2}^{1} \frac{2a-1}{2a}\,\mathrm{d}a=\frac{1}{2}-\frac{1}{2}\log(2)
\]Putting everything together, we can calculate the area of the original blue shape, and it’s given by:
\begin{align}
A_\text{acute} &= \frac{1}{2}-4A_\text{blue}-2A_\text{yellow} \\
&= \frac{1}{2}-4\left(\frac{3}{8}-\frac{1}{2}\log(2)\right)-2\left(\frac{1}{2}-\frac{1}{2}\log(2)\right) \\
&= \log(8)-2 \approx 0.07944
\end{align}So the probability of forming an acute triangle by breaking a stick into three pieces is about 7.9%.

Problem 4

We’ll solve this problem the same way we solved Problem 2, but we’ll replace the triangle inequalities with the acute triangle inequalities used in Problem 3. As in Problem 2, we end up with a 3D volume rather than a 2D area. For simplicity again, we’ll assume that $c$ is the largest length, which accounts for one third of all possibilities. Here is the volume we get:

While this looks like a more complicated shape than the one from Problem 2, the curved surface has equation $c^2=a^2+b^2$, which is just the equation of a right circular cone! So we can calculate the volume of the region of interest by subtraction. It’s $1/3$ of the volume of the cube minus $1/4$ of the volume of the cone. The total probability is three times this volume, because we must account for the remaining identical pieces. The final answer is:
\[
P_\text{final}=3\left( \frac{1}{3}-\frac{1}{4}\left( \frac{\pi}{3} \right) \right) =1-\frac{\pi}{4} \approx 0.2146
\]So the probability of forming an acute triangle with three randomly chosen lengths is about 21.5%.

Just for fun, here is what you get when you put all three shapes together!

A tetrahedron puzzle

This post is about a 3D geometry Riddler puzzle involving spheres and tetrahedra! Here is the problem:

We want to create a new gift for fall, and we have a lot of spheres, of radius 1, left over from last year’s fidget sphere craze, and we’d like to sell them in sets of four. We also have a lot of extra tetrahedral packaging from last month’s Pyramid Fest. What’s the smallest tetrahedron into which we can pack four spheres?

Here is my solution:
[Show Solution]

We’ll solve this problem using old school (read: high school) geometry. Rather than starting with four spheres and looking for the smallest tetrahedron that contains them, we’ll solve the equivalent problem of starting with a fixed tetrahedron and looking for the largest spheres we can pack inside. We’ll use a tetrahedron of unit sidelength. Place one vertex at the origin $\vec O(0,0,0)$, one vertex on the $x$-axis $\vec P(1,0,0)$, and one face in the $xy$-plane. This leads to a vertex at $\vec Q(\frac{1}{2},\frac{\sqrt{3}}{2},0)$ because $OPQ$ is an equilateral triangle. To find the final vertex $R$, we know by symmetry that its $x$ and $y$ coordinates are the same as those of the centroid of $OPQ$, so $x=\frac{1}{2}$ and $y=\frac{\sqrt{3}}{6}$ (it’s at one third the altitude!). To find the final coordinate, we look for $z$ such that $x^2+y^2+z^2=1$, since all sides have length $1$. This leads us to the final vertex of the tetrahedron: $\vec R(\frac{1}{2},\frac{\sqrt{3}}{6},\frac{\sqrt{6}}{3})$.

The center of the tetrahedron can be found by looking for a point of the form $\alpha(\vec P+ \vec Q+\vec R)$ (again by symmetry) whose $x$-coordinate is $\frac{1}{2}$. Doing this leads us to the center: $\vec C(\frac{1}{2},\frac{\sqrt{3}}{6},\frac{\sqrt{6}}{12})$. Next, let’s look for the center of the sphere closest to the origin. By symmetry, it must be of the form $\vec C_1 = \beta \vec C$. We want to find $\beta$ such that it’s $x$-distance from the point $x=\frac{1}{2}$ is $r$ (so it just touches the sphere closest to $\vec P$), and we also want its $z$ coordinate to be $r$ (so it’s a distance $r$ from the $xy$ plane, because it’s a tangent point of the sphere). For a reference, see the figure below. I’m saying that $C_1$ (center of the sphere) should be on the line $OC$ and we should have $|C_1M| = |C_1A_1| = r$.

The equations just described are:
\begin{align}
\frac{1}{2} \beta &= \frac{1}{2}-r\\
\frac{\sqrt{6}}{12} \beta &= r
\end{align}
Solving this system of equations yields $\beta=\frac{6-\sqrt{6}}{5}$ and $r=\frac{\sqrt{6}-1}{10}\approx 0.145$. So this is the radius of the largest sphere we can use when the tetrahedron has sidelength $1$. If the radius is instead $1$, then we must scale the tetrahedron accordingly. The resulting sidelength will be:
\[
s = \frac{10}{\sqrt{6}-1} = 2\sqrt{6}+2 \approx 6.89898
\]Here is a scale diagram of the entire pyramid with the four spheres inside:

Is this bathroom occupied?

After a brief hiatus from Riddling, I’m back! This Riddler problem is about probability and bathroom vacancy.

There is a bathroom in your office building that has only one toilet. There is a small sign stuck to the outside of the door that you can slide from “Vacant” to “Occupied” so that no one else will try the door handle (theoretically) when you are inside. Unfortunately, people often forget to slide the sign to “Occupied” when entering, and they often forget to slide it to “Vacant” when exiting.

Assume that 1/3 of bathroom users don’t notice the sign upon entering or exiting. Therefore, whatever the sign reads before their visit, it still reads the same thing during and after their visit. Another 1/3 of the users notice the sign upon entering and make sure that it says “Occupied” as they enter. However, they forget to slide it to “Vacant” when they exit. The remaining 1/3 of the users are very conscientious: They make sure the sign reads “Occupied” when they enter, and then they slide it to “Vacant” when they exit. Finally, assume that the bathroom is occupied exactly half of the time, all day, every day.

Two questions about this workplace situation:

1. If you go to the bathroom and see that the sign on the door reads “Occupied,” what is the probability that the bathroom is actually occupied?
2. If the sign reads “Vacant,” what is the probability that the bathroom actually is vacant?
Extra credit: What happens as the percentage of conscientious bathroom users changes?

Here is how I solved the problem:
[Show Solution]

This problem can be solved using Bayes’ Rule but you can also use Markov chains. I like Markov chains so that’s what we’ll do!

The first step is to define what are states and transition probabilities are. This is the tricky part; we might be tempted to think that because the bathroom can be either occupied or not, and the sign in front can either read “Vacant” or “Occupied”, that there should be four states (one for each possible pair).

However, this is not the case. The reason is because the transition probabilities are not independent of one another. Consider the state “bathroom is occupied and the sign says it’s occupied”. We must distinguish between the cases where the person occupying the bathroom is conscientious (they will definitely slide the sign to “Vacant” when they leave) or not (they will leave the sign as “Occupied” after they leave).

We must therefore add additional states to our Markov chain that correspond to the different ways in which the bathroom can be occupied. To keep things general, let’s assume the fraction of oblivious, forgetful, and conscientious users are $p$, $q$, and $r$, respectively. Therefore $0\le p,q,r \le 1$ and $p+q+r=1$. A diagram of the Markov chain:

If $\{x_k\}$ denotes the probability of being in state $k$ in the diagram, the stationary distribution satisfies the equation:

\[
\begin{bmatrix}
0 & 0 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 \\
p & 0 & 0 & 0 & 0 & 0 \\
r & r & 0 & 0 & 0 & 0 \\
q & q & 0 & 0 & 0 & 0 \\
0 & p & 0 & 0 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6
\end{bmatrix}
=
\begin{bmatrix}
x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6
\end{bmatrix}
\]

Solving these equations, we obtain:

\begin{align}
x_1 &= \frac{r}{2 (q+r)}, & x_2 &= \frac{q}{2 (q+r)}, & x_3 &= \frac{p r}{2 (q+r)}, \\
x_4 &= \frac{r}{2}, & x_5 &= \frac{q}{2}, & x_6 &= \frac{pq}{2 (q+r)}
\end{align}

We can now compute the probabilities we’re after:

\begin{align}
\mathbb{P}(\text{Vacant}\mid \text{says “Vacant”})
&= \frac{x_1}{x_1+x_3} = \frac{1}{1+p}\\
\mathbb{P}(\text{Occupied}\mid \text{says “Occupied”})
&= \frac{x_4+x_5+x_6}{x_2+x_4+x_5+x_6} = \frac{r+q-pr}{r+2q-pr}
\end{align}

When $p=q=r=\frac{1}{3}$ (equal fraction of conscientious, forgetful, and oblivious users), we obtain:
\begin{align}
\mathbb{P}(V\mid V) &= \frac{3}{4}, &
\mathbb{P}(O\mid O) &= \frac{5}{8}
\end{align}

Bonus: different probabilities

We have the analytic expressions above for what happens as a function of $p,q,r$… so now it remains to visualize it somehow. One possibility is to set two of them equal and just make a plot. For example, if we only vary the percentage of conscientious users ($r$) and set the other two to be equal, i.e. $p=q=\frac{1-r}{2}$. We then obtain:
\begin{align}
\mathbb{P}(V\mid V) &= \frac{2}{3-r}, &
\mathbb{P}(O\mid O) &= \frac{r^2+1}{r^2-r+2}
\end{align}We can also plot these probabilities as a function of $r$:

If we want to see what happens as we vary the percentages of $p,q,r$ all at once, we can visualize the result using a ternary density plot. Here, we plot values in a triangle; the fraction of each type of bathroom user is determined by the length of the altitude to the opposite side of the triangle and the color indicates the probability. Here are the plots:

You can read off the appropriate percentages by looking at the tick marks. For example, the lower-left corner corresponds to everybody being conscientious, the bottom (horizontal) side of the triangle corresponds to nobody being oblivious, and as you move from left to right you increase the fraction of forgetful users while simultaneously decreasing the fraction of conscientious users. The center of the triangle corresponds to $p=q=r=\tfrac{1}{3}$, and so on.

One additional comment: you’ll notice the point at the top of the triangle (100% oblivious users) is missing. This is because this probability doesn’t make sense. When all users are oblivious, the sign will never change. So if it starts at “Vacant”, it will stay at “Vacant” forever.

Squaring the square

This Riddler puzzle is about tiling a square using smaller squares.

You are handed a piece of paper containing the 13-by-13 square shown below, and you must divide it into some smaller square pieces. If you are only allowed to cut along the lines, what is the smallest number of squares you can divide this larger square into? (You could, for example, divide it into one 12-by-12 square and 25 one-by-one squares for a total of 26 squares, but you can do much better.)

Here is how I solved the problem:
[Show Solution]

This is a challenging puzzle and there is unfortunately no clever trick one can use to solve it quickly. If we consider the general problem of tiling an $N\times N$ grid using smaller squares, we can make several observations:

The smallest answer we could ever hope for is $4$. If $N=2k$ is even, we can achieve the minimum by splitting the square into four $k\times k$ squares. It’s clear that this solution cannot be improved.
If $N = 3k$ is a multiple of $3$, we can split it into six pieces: one $2k\times 2k$ square and five $k\times k$ squares. I believe this also cannot be improved.
When $N$ has many divisors, it becomes easier to tile it. The most challenging cases are therefore the cases where $N$ is prime. So a larger grid doesn’t necessarily mean a more difficult problem! We’ll see examples of this later.

I’ll solve this problem by converting it into an integer linear program (specifically, a variant of a knapsack problem), which can be solved much more efficiently than by brute-force checking the astronomical number of possible tilings.

I’ll illustrate the approach for the $5\times 5$ case. We’ll represent each possible square as a $5\times 5$ matrix of $0$’s and $1$’s. For example, we can use $25$ different $1\times 1$ tiles:
\[
\scriptsize \begin{bmatrix}{\color{red}{\color{red}1}}&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{bmatrix},
\begin{bmatrix}0&{\color{red}1}&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{bmatrix},
\begin{bmatrix}0&0&{\color{red}1}&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{bmatrix},\,\dots\,,
\begin{bmatrix}0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&{\color{red}1}\end{bmatrix}
\]We can also use $16$ different $2\times 2$ tiles:
\[
\scriptsize \begin{bmatrix}{\color{red}1}&{\color{red}1}&0&0&0\\{\color{red}1}&{\color{red}1}&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{bmatrix},
\begin{bmatrix}0&{\color{red}1}&{\color{red}1}&0&0\\0&{\color{red}1}&{\color{red}1}&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{bmatrix},
\begin{bmatrix}0&0&{\color{red}1}&{\color{red}1}&0\\0&0&{\color{red}1}&{\color{red}1}&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{bmatrix},\,\dots\,,
\begin{bmatrix}0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&{\color{red}1}&{\color{red}1}\\0&0&0&{\color{red}1}&{\color{red}1}\end{bmatrix}
\]Continuing in this fashion, we have $9$ different $3\times 3$ tiles and $4$ different $4\times 4$ tiles. So in total, we have $25+16+9+4=54$ different tiles. The name of the game is to pick the smallest possible subset of these matrices that sums to the matrix of all $1$’s. We can represent this compactly by vectorizing each of the $54$ matrices above into $25\times 1$ columns, and then stacking the columns side by side to form a matrix $A \in \{0,1\}^{25\times 54}$. Our goal is then to solve the problem:
\begin{align}
\underset{x \in \{0,1\}^{54}}{\text{minimize}}\qquad& \sum_{i=1}^{54} x_i \\
\text{subject to:}\qquad & Ax = 1
\end{align}Here, each $x_i$ is a binary variable that selects whether we’ll be using the $i^\text{th}$ column of $A$ or not. It turns out the optimal solution for this $5\times 5$ case uses $8$ squares; or the sum:
\begin{multline}
\scriptsize \begin{bmatrix}0&0&0&0&0\\0&0&0&0&0\\{\color{red}1}&{\color{red}1}&{\color{red}1}&0&0\\{\color{red}1}&{\color{red}1}&{\color{red}1}&0&0\\{\color{red}1}&{\color{red}1}&{\color{red}1}&0&0\end{bmatrix}
+\begin{bmatrix}{\color{red}1}&{\color{red}1}&0&0&0\\{\color{red}1}&{\color{red}1}&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{bmatrix}
+\begin{bmatrix}0&0&0&{\color{red}1}&{\color{red}1}\\0&0&0&{\color{red}1}&{\color{red}1}\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{bmatrix}
+\begin{bmatrix}0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&{\color{red}1}&{\color{red}1}\\0&0&0&{\color{red}1}&{\color{red}1}\end{bmatrix}\\
\scriptsize+\begin{bmatrix}0&0&{\color{red}1}&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{bmatrix}
+\begin{bmatrix}0&0&0&0&0\\0&0&{\color{red}1}&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{bmatrix}
+\begin{bmatrix}0&0&0&0&0\\0&0&0&0&0\\0&0&0&{\color{red}1}&0\\0&0&0&0&0\\0&0&0&0&0\end{bmatrix}
+\begin{bmatrix}0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&{\color{red}1}\\0&0&0&0&0\\0&0&0&0&0\end{bmatrix}
\end{multline}This general strategy of enumerating choices and then selecting among them doesn’t scale all that well because as $N$ gets large $A$ grows pretty quickly. In fact, $A$ will be $N^2 \times \tfrac{1}{6}(N-1)(2N^2+5N+6)$. However, in these cases we can use a heuristic such as column generation to quickly obtain approximate answers that can be iteratively and efficiently refined.