The Fiddler – Book Proofs

The weaving loom problem

This week’s Fiddler is a classic problem.

A weaving loom consists of equally spaced hooks along the x and y axes. A string connects the farthest hook on the x-axis to the nearest hook on the y-axis, and continues back and forth between the axes, always taking up the next available hook. This leads to a picture that looks like this:

As the number of hooks goes to infinity, what does the shape trace out?

Extra credit: If four looms are rotated and superimposed as shown below, what is the area of the white region in the middle?

My solution:
[Show Solution]

Suppose the weaving loom has size $1\times 1$. If a given string starts a fraction $\alpha$ away from the origin along the $y$-axis, so at the point $(0,\alpha)$, it will connect to the point $(1-\alpha,0)$ along the $x$-axis. Therefore, the set of all lines have equations:
\[
y = \alpha-\frac{\alpha}{1-\alpha}x
\]Suppose the limiting shape has equation $y = f(x)$. For a given $x$, $f(x)$ is the largest value of $y$ achievable for one of the lines above at that given $x$. This is illustrated in the diagram below:

In other words, we have:
\[
f(x) = \max_{0\leq\alpha\leq 1} \left( \alpha-\frac{\alpha}{1-\alpha}x \right)
\]It’s clear that the maximum will not occur at a boundary point ($\alpha=0$ or $\alpha=1$), so it must occur at a point where the derivative with respect to $\alpha$ is zero. In other words,
\[
\frac{\mathrm{d}}{\mathrm{d}\alpha}\left( \alpha-\frac{\alpha}{1-\alpha}x \right)
= 1-\frac{x}{(1-\alpha)^2} = 0
\]The optimal choice is $\alpha_\star = 1-\sqrt{x}$, and this leads to
\begin{align}
f(x) &= 1-\sqrt{x}-\frac{1-\sqrt{x}}{\sqrt{x}}x \\
&=1-2\sqrt{x}+x \\
&= (1-\sqrt{x})^2
\end{align}A more symmetric way to express this function is to write it implicitly. If $y=f(x)$, the set of points $(x,y)$ that satisfy the equation above are precisely the points that satisfy the equation

$\displaystyle
\sqrt{x} + \sqrt{y} = 1
$

Let’s dig a little deeper and see if we can learn more about the shape of this curve. Squaring both sides, rearranging, and squaring again, we obtain:
\[
x^2+y^2-2xy-2x-2y+1 = 0
\]This is a quadratic expression in $x$ and $y$, which means it is a conic section! So either a circle, ellipse, hyperbola, or parabola. But which one? The easiest way to check is to examine the eigenvalues of the quadratic part (there will be two eigenvalues). Here is a handy table for reference:
\[
\begin{array}{l|l}
\textbf{eigenvalue property} & \textbf{conic section} \\ \hline
\text{equal eigenvalues} & \text{circle} \\
\text{same sign and nonzero} & \text{ellipse} \\
\text{different sign and nonzero} & \text{hyperbola} \\
\text{one zero eigenvalue} & \text{parabola}
\end{array}
\]
In our case, the quadratic terms are:
\[
x^2+y^2-2xy = \begin{bmatrix}x\\y\end{bmatrix}^\mathsf{T}
\begin{bmatrix}1 & -1 \\ -1 & 1\end{bmatrix}
\begin{bmatrix}x\\y\end{bmatrix}
\]This matrix is singular (determinant is zero), so there is a zero eigenvalue, and the conic section must be a parabola! To make this more evident, we can rearrange the equation a bit more to obtain
\[
\left(\frac{x+y}{\sqrt{2}}\right) = \frac{1}{\sqrt{2}}\left(\frac{x-y}{\sqrt{2}}\right)^2 + \frac{1}{2\sqrt{2}}
\]If we imagine rotating our curve by $45$ degrees counterclockwise, this would correspond to the transformation $(x,y)\mapsto\left(\tfrac{x-y}{\sqrt{2}}, \tfrac{x+y}{\sqrt{2}} \right)$, so the equation above in rotated coordinates $(\hat x, \hat y)$ is simply
\[
\hat y = \frac{1}{\sqrt{2}}\hat x^2 + \frac{1}{2\sqrt{2}},
\]which is clearly a parabola.

Tangency. Based on the animation above, it looks like the line that crosses $(x,f(x))$ is also tangent to the curve at that point. To verify this, we can compute the derivative directly and compare it to the slope of the line:
\[
f'(x) = \frac{\mathrm{d}}{\mathrm{d}x}(1-\sqrt{x})^2 = 1-\frac{1}{\sqrt{x}}
\]But the $\alpha_\star$ we found for a point $x$ produces:
\[
\text{(slope of line)} = \frac{-\alpha_\star}{1-\alpha_\star} = \frac{-(1-\sqrt{x})}{1-(1-\sqrt{x})} = 1-\frac{1}{\sqrt{x}},
\]which is a perfect match!

Extra credit

To find the area of the central region, we can break our shape into pieces as shown below.

The point $x_0$ corresponds to the $x$-value of our curve where $y=\frac{1}{2}$. This is given by:
\[
x_0 = \left(1-\sqrt{\frac{1}{2}}\right)^2 = \frac{3}{2}-\sqrt{2} \approx 0.0858
\]The area of the central part is the total area of the square ($1$) minus four times the shaded area, which leads us to the integral:
\begin{align}
A &= 1-4\left( \frac{1}{2}x_0 + \int_{x_0}^{\frac{1}{2}} (1-\sqrt{x})^2\,\mathrm{d}x \right) \\
&= \frac{2}{3}\left(4\sqrt{2}-5\right) \\[2mm]
&\approx 0.4379
\end{align}I decided to spare you the details of the integration because they’re not particularly interesting. So the white area in the middle occupies approximately $43.8\%$ of the area of the square.

Betting on football with future knowledge

This week’s Fiddler is a football-themed puzzle with a twist: you can see the future! Sort of.

You know ahead of time that your football team will win 8 of their 12 remaining games, but you don’t know which ones. You can place bets on every game, placing bets either for or against your team. You can bet any amount up to how much you currently have. You want to implement a betting strategy that guarantees you’ll have as much money as possible after the 12 games are complete. If you did so, then after the 12 games how much money would you be guaranteed to have if you started with $100?

My solution:
[Show Solution]

Define our quantity of interest:
\[
a_{n,m} = \left\{\begin{array}{l}
\text{Maximum guaranteed winnings assuming there}\\
\text{are $n$ games remaining, we know our team}\\
\text{will win exactly $m$ of them, and we start with \$1.}
\end{array}\right\}
\]Also let $k_{n,m}$ be the fraction of our money we should bet that achieves the maximum guaranteed winnings. We use negative bets to indicate that we are betting for the other team to win. To illustrate, if we currently have $x$ dollars, we can bet any fraction $-1 \leq k \leq 1$, and the possible cases are:

If our team wins, we gain $k x$, so we now have $(1+k)x$.
If our team loses, we lose $k x$, so we now have $(1-k)x$.

Due to the homogeneous nature of the problem, if we were to start with $x$ dollars instead, then our winnings would just be $x \cdot a_{n,m}$.

Let’s start by looking at some edge cases.

If $m=0$ and $n=0$, we have the trivial case where the season is over, so we can say $a_{0,0} = 1$. In other words, we keep all our money.
If $m=n$, we know with certainty that our team will win all its remaining games. Therefore, we can safely bet all our money on them: $k_{n,n} = 1$ and $a_{n,n} = 2a_{n-1,n-1}$ (we will double our money).
If $m=0$, we know with certainty that our team will lose all its remaining games. Therefore, we can safely bet all our money against them: $k_{n,0}=-1$ and $a_{n,0} = 2a_{n-1,0}$.

In the general case, $0\lt m \lt n$, and we must think a bit more carefully. If we bet $k_{n,m}$, the two possible outcomes are:

If our team wins, we now have $a_{n,m} = (1+k_{n,m})a_{n-1,m-1}$. This is because after a win, there are only $m-1$ wins remaining.
If our team loses, we now have $a_{n,m} = (1-k_{n,m})a_{n-1,m}$. This is because after a loss, we must still win $m$ more times.

We should pick $k_{n,m}$ to maximize the minimum winnings of both possible outcomes, because we are looking at the worst-case. In other words, we want:
\[
a_{n,m} = \max_k\, \min\bigl\{ (1+k)a_{n-1,m-1}, (1-k)a_{n-1,m} \bigr\}
\]As functions of $k$, these are two linear functions; one with positive slope and one with negative slope. The optimal $k$ occurs when the lines cross, that is, when $(1+k)a_{n-1,m-1}=(1-k)a_{n-1,m}$. Solving this equation, we obtain:
\begin{align}
k_{n,m} &= \frac{a_{n-1,m}-a_{n-1,m-1}}{a_{n-1,m}+a_{n-1,m-1}}, &
a_{n,m} &= \frac{2a_{n-1,m}\cdot a_{n-1,m-1}}{a_{n-1,m}+a_{n-1,m-1}}
\end{align}Combining our recursion for $a_{n,m}$ with the edge cases derived earlier:
\begin{align}
a_{0,0}&=1 \\
a_{n,0}&=2a_{n-1,0} && \text{for }n=1,2,\dots \\
a_{n,n}&=2a_{n-1,n-1} && \text{for }n=1,2,\dots \\
a_{n,m} &= \frac{2a_{n-1,m}\cdot a_{n-1,m-1}}{a_{n-1,m}+a_{n-1,m-1}} &&\text{for }0\lt m \lt n
\end{align}There is a neat trick we can use to solve this recursion. Express everything in terms of the inverse of the minimum winnings. The equations then become linear!
\begin{align}
a_{0,0}^{-1}&=1 \\
a_{n,0}^{-1}&=\frac{1}{2} a_{n-1,0}^{-1} && \text{for }n=1,2,\dots \\
a_{n,n}^{-1}&=\frac{1}{2} a_{n-1,n-1}^{-1} && \text{for }n=1,2,\dots \\
a_{n,m}^{-1}&=\frac{1}{2}\left( a_{n-1,m}^{-1} + a_{n-1,m-1}^{-1} \right) &&\text{for }0\lt m \lt n
\end{align}Solving for the first few terms and arranging them in a pyramid where each row is a different value of $n$, we obtain:
\begin{gather}
a_{0,0}^{-1}=\frac{1}{2^0}\\[2mm]
a_{1,0}^{-1}=\frac{1}{2^1} \qquad a_{1,1}^{-1}=\frac{1}{2^1} \\[2mm]
a_{2,0}^{-1}=\frac{1}{2^2} \qquad a_{2,1}^{-1}=\frac{2}{2^2} \qquad a_{2,2}^{-1}=\frac{1}{2^2} \\[2mm]
a_{3,0}^{-1}=\frac{1}{2^3} \qquad a_{3,1}^{-1}=\frac{3}{2^3} \qquad a_{3,2}^{-1}=\frac{3}{2^3} \qquad a_{3,3}^{-1}=\frac{1}{2^3}\\[2mm]
a_{4,0}^{-1}=\frac{1}{2^4} \qquad a_{4,1}^{-1}=\frac{4}{2^4} \qquad a_{4,2}^{-1}=\frac{6}{2^4} \qquad a_{4,3}^{-1}=\frac{4}{2^4} \qquad a_{4,4}^{-1}=\frac{1}{2^4}
\end{gather}The denominators in each row are increasing powers of two, and the numerators are the sums of the two numerators above! In other words, it’s a scaled Pascal’s triangle! This leads us to the formula:
\[
a_{n,m}^{-1} = \frac{1}{2^{n}} \binom{n}{m},\quad\text{or:}\quad
a_{n,m} = \frac{2^{n}}{\binom{n}{m}}
\]What should our optimal policy be? We can use the formula for $k_{n,m}$ derived earlier and substitute the formula we just found for $a_{n,m}$:
\begin{align}
k_{n,m} &= \frac{a_{n-1,m}-a_{n-1,m-1}}{a_{n-1,m}+a_{n-1,m-1}}
= \frac{2m}{n}-1
\end{align}

Therefore, we have the following minimax-optimal strategy:

$\displaystyle
\begin{array}{l}
\text{If there are $n$ games left to play and our team will} \\
\text{win exactly $m$ of the remaining games, we should}\\
\text{bet a fraction $\frac{2m}{n}-1$ of our money, and we will}\\
\text{multiply our money by at least $\frac{2^n}{\binom{n}{m}}$ by the end.}
\end{array}
$

We can check the edge cases: If $m=0$, we should bet $k_{n,0}=-1$ (bet it all against our team), and we will win $2^n$ (double our money for every remaining game). Similarly, if $m=n$, we should bet $k_{n,n}=1$ (bet it all for our team), and we will again win $2^n$.

To address the original question, if there are $n=12$ games remaining and we will win exactly $m=8$ of them, then starting with $\$100$ and using the optimal betting strategy, we are guaranteed to finish the season with at least $100 \cdot 2^{12} / \binom{12}{8} =\frac{100\cdot 4096}{495} \approx \$827.48$.

We can say something even stronger. This optimal betting strategy will always win exactly $\$827.48$! To understand why, we need to dig a little deeper…

Deeper down the rabbit hole

When using the “optimal” strategy derived earlier, something curious happens. Not only are we guaranteed to win at least $2^n/\binom{n}{m}$ by the end of the season, we are guaranteed to win exactly this much! No matter how the wins and losses are arranged, we will always win the same amount after all games have been played!

We will prove this surprising result in two parts. First, we will show that every arrangement wins the same amount under the optimal betting strategy. Second, we will show that this amount is equal to $2^n/\binom{n}{m}$, the same as the previously derived “lower bound”.

To prove all arrangements win the same amount, imagine two arrangements of wins and losses that only differ by swapping one adjacent win-loss pair. For example, if $n=12$ and $m=8$, we could have:
\begin{gather}
\begin{bmatrix}
W & L & W & \textcolor{blue}{W} & \textcolor{red}{L} & W & L & W & W & W & L & W
\end{bmatrix}\\[2mm]
\begin{bmatrix}
W & L & W & \textcolor{red}{L} & \textcolor{blue}{W} & W & L & W & W & W & L & W
\end{bmatrix}
\end{gather}Suppose that right before the swap occurs, we have $x$ dollars, and there are $n_0$ games remaining, and $m_0$ wins remaining.

In the first case, we bet $\frac{2m_0}{n_0}-1$ and we win. There are now $n_0-1$ games remaining and $m_0-1$ wins remaining. We bet $\frac{2(m_0-1)}{n_0-1}-1$, but this time we lose. So our net winnings after the win and loss are:
\[
\small
\left( 1-\left(\frac{2(m_0-1)}{n_0-1}-1\right)\right)\left(1+\left(\frac{2m_0}{n_0}-1\right)\right)x
=\frac{4m_0 (n_0-m_0)}{n_0(n_0-1)}x
\]
In the second case, we bet $\frac{2m_0}{n_0}-1$ and we lose. There are now $n_0-1$ games remaining and $m_0$ wins remaining. We bet $\frac{2m_0}{n_0-1}-1$, and this time we win. So our net winnings after the loss and win are:
\[
\small
\left( 1+\left(\frac{2m_0}{n_0-1}-1\right)\right)\left(1-\left(\frac{2m_0}{n_0}-1\right)\right)x
=\frac{4m_0 (n_0-m_0)}{n_0(n_0-1)}x
\]

Since swapping an adjacent win-loss pair does not change how much we win, and we can get from any arrangement of $m$ wins and $n-m$ losses to any other arrangement via a suitable sequence of adjacent win-loss swaps, this shows that every arrangement obtains the exact same result!

In particular, we might as well assume we win our first $m$ games, and lose the rest. Let’s calculate how much we win in this simple scenario.

For the first $m$ games, we win every time, so our winnings are:
\[
\frac{2m}{n} \cdot \frac{2(m-1)}{(n-1)} \cdot \frac{2(m-2)}{(n-2)} \cdots \frac{2(1)}{(n-m+1)}
=\frac{2^m m!(n-m)!}{n!}
\]
For the remaining $n-m$ games, we are in an edge case. Our team will lose all remaining games, so we bet against them every time and double our money. This multiplies our money by $2^{n-m}$.

Therefore, our total winnings are:
\[
\frac{2^m m!(n-m)!}{n!} \cdot 2^{n-m} = \frac{2^n}{\binom{n}{m}}
\]This is the same result as the lower bound we found in the first part of the solution! Therefore, we can conclude that using the optimal betting strategy yields exactly the same outcome no matter how the wins and losses are ordered, and this amount is $2^n/\binom{n}{m}$.

A more elegant alternative solution, due in large part to a clever observation by Vince Vatter.
[Show Solution]

The key observation is that we can think of betting strategies as bets on outcomes rather than bets on individual games. For example, if $n=2$, there are four possible outcomes (ignore for now the fact that we have future knowledge about the win-loss record):
\[
LL,LW,WL,WW
\]If I bet all my money on $LW$ and I’m right, then I will double my money twice. If I’m wrong, then I lose everything.

In general, if there are $n$ games, there will be $2^n$ possible outcomes. I don’t have to bet everything on one outcome; I can distribute my $x$ dollars however I like. But only one of these outcomes will come true. The money I bet on that outcome will get multiplied by $2^n$ and all my other bets will be lost.

In the worst case, the outcome with the smallest bet will come true. So if we want a strategy that maximizes the worst-case losses, I should bet an equal amount on each possible outcome.

Now we can use our advance knowledge that our team will win exactly $m$ of the $n$ games. Therefore, only $\binom{n}{m}$ of the $2^n$ outcomes are possible. So the optimal strategy is to distribute our bets equally among all $\binom{n}{m}$ possible outcomes. With this strategy, no matter which outcome comes true, we will always multiply our initial dollar amount by exactly $2^n/\binom{n}{m}$.

I skipped some details here; I didn’t explain why every strategy can be decomposed as a combination of pure strategies, but this post is already quite long so I won’t write out the details. As a partial explanation, the result uses the fact that the earnings are a linear function of the bets. For example, if $n=1$, our strategy consists of the single bet $k$, and the outcome is:
\[
(k) : \begin{cases}
(1+k)x & \text{if W} \\
(1-k)x & \text{if L}
\end{cases}
\]There are also two pure strategies:
\[
(1) : \begin{cases}
0 & \text{if W} \\
2x & \text{if L}
\end{cases}
\qquad\text{and}\qquad
(-1): \begin{cases}
2x & \text{if W} \\
0 & \text{if L}
\end{cases}
\]We can decompose $k$ as a combination of $+1$ and $-1$, which yields:
\[
(k) = \left(\frac{1-k}{2}\right)(1) + \left(\frac{1-k}{2}\right)(-1)
\]In other words, using the bet $k$ is the same as betting $\left(\frac{1-k}{2}\right)x$ of our money on a loss and betting the remaining $\left(\frac{1+k}{2}\right)x$ on a win. Exactly one of those two outcomes will come true, so the amount we bet correctly gets doubled and the amount we bet incorrectly is lost.

Optimal baseball lineup

This week’s Fiddler is a problem about how to set the optimal baseball lineup.

Eight of your nine batters are “pure contact” hitters. One-third of the time, each of them gets a single, advancing any runners already on base by exactly one base. (The only way to score is with a single with a runner on 3rd). The other two-thirds of the time, they record an out, and no runners advance to the next base. Your ninth batter is the slugger. One-tenth of the time, he hits a home run. But the remaining nine-tenths of the time, he strikes out. Your goal is to score as many runs as possible, on average, in the first inning. Where in your lineup (first, second, third, etc.) should you place your home run slugger?

Extra Credit: Instead of scoring as many runs as possible in the first inning, you now want to score as many runs as possible over the course of nine innings. What’s more, instead of just having one home run slugger, you now have two sluggers in your lineup. The other seven batters remain pure contact hitters. Where in the lineup should you place your two sluggers to maximize the average number of runs scored over nine innings?

My solution:
[Show Solution]

We will attack this problem using dynamic programming. Rather than solving for the average number of runs for a particular configuration (of outs, runners on base, current batter, etc.), we will solve for all possible configurations! To this effect define the following:
\[
V(o,r,b,i) = \left\{
\begin{array}{l}
\text{Expected number of runs at end of}\\
\text{game given that we are currently in}\\
\text{the $i^\text{th}$ inning with $o$ outs, $r$ runners}\\
\text{on base, and the $b^\text{th}$ batter is up.}
\end{array}\right\}
\]Each index can only take on certain values. Define the sets:
\begin{align}
O &= \{0,1,2,3\} && \text{(number of outs)} \\
R &= \{0,1,2,3\} && \text{(runners on base)} \\
B &= \{1,2,\dots,9\} && \text{(batter currently up)} \\
I &= \{1,2,\dots,9\} && \text{(current inning)}
\end{align}Therefore there are $4\times 4\times 9\times 9 = 1296$ possible configurations we must solve for. Finally, some subset of the batters are the sluggers. Let this subset be $S \subseteq B$. The remaining batters are the pure contact hitters, which we denote $\bar S$. Therefore $S\cap \bar S = \emptyset$ and $S \cup \bar S = B$.

Finally, define $p$ to be the on-base average for pure contact hitters, and $q$ to be the slugging percentage for the sluggers. In the problem statement, we have $p=\frac{1}{3}$ and $q=\frac{1}{10}$.

We can now write equations that determine how the various configuration are related to each other:

When we have 3 outs, clear bases and advance to next inning, or end the game if we are in the 9th inning.\begin{align}
V(3,r,b,i) &= V(0,0,b,i+1) && \forall r\in R, b\in B, i\in\{1,\dots,8\}\\
V(3,r,b,9) &= 0 && \forall r\in R, b\in B
\end{align}This is a total of $4\times 9\times 9 = 324$ equations.
When a pure contact hitter is up to bat, they either advance runners (and possibly score if bases are loaded), or they strike out.
\begin{align}
V(o,r,b,i) &= p V(o,r+1,b+1,i) + (1-p) V(o+1,r,b+1,i) && \forall o\in \{0,1,2\}, r\in \{0,1,2\}, b\in \bar S, i\in I \\
V(o,3,b,i) &= p (1+V(o,3,b+1,i)) + (1-p) V(o+1,3,b+1,i) && \forall o\in \{0,1,2\}, b\in \bar S, i \in I
\end{align}This is a total of $3\times 4\times 9\times |\bar S| = 108|\bar S|$ equations.
When a slugger is up to bat, they either hit a home run (and clear the bases), or they strike out.
\begin{align}
V(o,r,b,i) &= q (r+1+V(o,0,b+1,i)) + (1-q) V(o+1,r,b+1,i) && \forall o\in\{0,1,2\}, r\in R, b\in S, i\in I
\end{align}This is a total of $3\times 4\times 9\times |S| = 108|S|$ equations.

In all the equations above, when we write “$b+1$”, we mean that if we get to the end of the order, we should cycle back to the top of the order.
This adds up to a total of $324+108|\bar S|+108|S| = 1296$ equations. We have the same number of equations as variables, which tells us that we accounted for everything!

I used Mathematica to input all the equations programmatically and solve them, and here is what I found.

First part: one inning, one slugger

When looking at a single inning with a single slugger, we pick $I = \{1\}$, and we can choose $S = \{9\}$ for example, and then ask, which batter should bat first to maximize score? this amounts to see which of
\[
V(0,0,b,1),\qquad b=1,2,\dots,9
\]is largest. Using the hitting percentages from the problem ($p=\frac{1}{3}$ and $q=\frac{1}{10}$), we obtain the following bar chart:

So it is best to put the slugger fourth in the batting order. This leads to an expected score of $\frac{3051922249868633}{12708748019768805} \approx 0.240143$ runs scored in the first inning. This is only narrowly better than putting the slugger third, which leads to an average of $0.23937$ runs scored. Overall, here is what we find:
\[
\begin{array}{r|ccccccccc}
\text{slugger position} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline
\text{expected runs} & 0.184128 & 0.210732 & 0.23937 & 0.240143 & 0.202726 & 0.156235 & 0.168336 & 0.174246 & 0.176961
\end{array}
\]

By changing $p$ and $q$, we get different solutions. For example, if we make the pure contact hitters better, say $p=\frac{2}{3}$, but we keep the slugging at $q=\frac{1}{10}$, we obtain:

So in this case, the slugger is best placed last, presumably because they get out so much more frequently than the pure contact hitters.

Second part: nine innings, two sluggers

With nine innings and two sluggers, I iterated through all possible two-element subsets $S \subseteq B$, and then computed $V(0,0,1,1)$ for each case. This led to the following picture:

This plot shows the expected number of runs after 9 innings as a function of the two sluggers’ positions in the batting order. The best outcome occurs when the sluggers are 3rd and 4th in the batting order. This is the yellow bar in the (3,4) coordinate, which corresponds to an average of 1.99771 runs per game. Note that the y-axis has a relatively small range; it only ranges from 1.85 to 2.0. This goes to show that over the course of 9 innings, the batting order does not make that much difference. Here is a table showing all the results:

Code

To solve this problem analytically, I used Mathematica to specify each of the equations above, and then called the “Solve” function on that system of equations. Each of the equations can be collected into a list using the “Table” function, which makes it easy to enumerate the equations without having to write each one down manually. You can view my Mathematica code here, or in the window below.

Braille puzzle

This week’s Fiddler is a counting problem about the Braille system.

Braille characters are formed by raised dots arranged in a braille cell, a three-by-two array. With six locations for dots, each of which is raised or unraised, there are 26, or 64, potential braille characters.

Each of the 26 letters of the basic Latin alphabet (shown below) has its own distinct arrangement of dots in the braille cell. What’s more, while some arrangements of raised dots are rotations or reflections of each other (e.g., E and I, R and W, etc.), no two letters are translations of each other. For example, only one letter (A) consists of a single dot – if there were a second such letter, A and this letter would be translations of each other.

Of the 64 total potential braille characters, how many are in the largest set such that no two characters consist of raised dot patterns that are translations of each other?

Extra Credit In addition to six-dot braille, there’s also an eight-dot version. But what if there were even more dots? Let’s quadruple the challenge by doubling the size of the cell in each dimension. Consider a six-by-four array, where a raised dot could appear at each location in the array. Of the 224 total potential characters, how many are in the largest set such that no two characters are translations of each other?

My solution:
[Show Solution]

We will solve a general version of this problem, where the Braille characters are $m\times n$. That is, there are $m$ rows and $n$ columns.

When two characters are translations of one another, we will say they are equivalent. The equivalence class of a character is the set of all characters equivalent to that particular one. For example, in the $3\times 2$ case, a single dot has six equivalents, and two vertically stacked dots have 4 equivalents. In the figure below, each row shows equivalent characters.

The size of an equivalence class is determined by the footprint of its characters. That is, the smallest rectangle that contains all the dots. For example, in the $6\times 4$ case below, the character shown has a $4\times 4$ footprint (the red outline):

If we translate this character, we see that it can occupy $3$ different vertical locations and $2$ different horizontal locations, for a total of $3\times 2 = 6$ equivalent characters. In general, if the footprint of a character is $i\times j$, then its equivalence class contains $(m-i+1)(n-j+1)$ elements.
Let us define:

$f(m,n)$: The size of the largest set of $m\times n$ characters such that no two characters are translations of one another. In other words, the number of different equivalence classes.
$g(i,j)$: The number of different characters that have a footprint $i\times j$.

The problem is asking us to calculate $f(m,n)$, but based on the discussion above, it is clear that:
\[
f(m,n) = \sum_{i=1}^m\sum_{j=1}^n g(i,j)
\]Computing $g(i,j)$ is fundamentally a (tedious) counting problem: Given a $i\times j$ rectangle, how many dot patterns can we make that fit snugly in that rectangle? The size of the footprint is determined by the dots on the border, so we separate the corners, edges, and middle section of the footprint:

Depending on which corners are filled in, this determines what the edges can look like so that the character fit snugly in the $i\times j$ rectangle. In particular, we have the following five cases:

No corners filled in. There must therefore be at least one dot on each edge. The vertical and horizontal edges contain $i-2$ and $j-2$ slots, respectively. Since we want to exclude the “empty” edge, we can fill in the edges in $\bigl(2^{i-2}-1\bigr)^2\bigl(2^{j-2}-1\bigr)^2$ ways.
One corner filled in. The adjacent edges can be filled in arbitrarily, while the two opposite edges must each contain a dot. Thus we can fill the edges in $\bigl(2^{i-2}-1\bigr)2^{i-2}\bigl(2^{j-2}-1\bigr)2^{j-2}$ ways. This can happen in 4 different ways (depending on which corner is filled).
Two bottom (or top) corners filled in. The three adjacent edges can be filled in arbitrarily, while the opposite vertical edge must contain a dot. Thus we can fill the edges in $\bigl(2^{i-2}\bigr)^2\bigl(2^{j-2}-1\bigr)2^{j-2}$ ways. This can happen in 2 different ways (we can pick the bottom or top corners).
Two left (or right) corners filled in. The three adjacent edges can be filled in arbitrarily, while the opposite horizontal edge must contain a dot. Thus we can fill the edges in $\bigl(2^{i-2}-1\bigr)2^{i-2}\bigl(2^{j-2}\bigr)^2$ ways. This can happen in 2 different ways (we can pick the left or right corners).
Two opposite corners filled in (or more). In this case, all four edges can be filled in arbitrarily since opposite corners completely determine the footprint. We therefore count $\bigl(2^{i-2}\bigr)^2\bigl(2^{j-2}\bigr)^2$ ways. This can happen in 7 different ways, since we can have only the opposite corners (2 ways), any three corners (4 ways), or all four corners (1 way).

For each of these cases, we can fill in the central $(i-2)\times(j-2)$ portion of the character arbitrarily, which means we should add all the above cases together, and multiply the total by $2^{(i-2)(j-2)}$.

Putting all of this together, we get our final tally:
\begin{multline}
g(i,j) = 2^{(i-2)(j-2)}\biggl(\bigl(2^{i-2}-1\bigr)^2\bigl(2^{j-2}-1\bigr)^2 \\
+ 4 \cdot \bigl(2^{i-2}-1\bigr)2^{i-2}\bigl(2^{j-2}-1\bigr)2^{j-2}
+ 2 \cdot \bigl(2^{i-2}\bigr)^2\bigl(2^{j-2}-1\bigr)2^{j-2} \\
+ 2 \cdot \bigl(2^{i-2}-1\bigr)2^{i-2}\bigl(2^{j-2}\bigr)^2
+ 7 \cdot \bigl(2^{i-2}\bigr)^2\bigl(2^{j-2}\bigr)^2 \biggr)
\end{multline}One final wrinkle: The above formula only makes sense if $i\geq 2$ and $j\geq 2$. Otherwise, our footprint will be a degenerate rectangle (it will not have four corners). Accounting for this, we obtain the complete version of $g(i,j)$:
\[
g(i,j) = \begin{cases}
\text{(formula above)} & i\geq 2\text{ and }j\geq 2 \\
2^{i-2} & i\geq 2\text{ and }j=1\\
2^{j-2} & i=1\text{ and }j\geq 2\\
1 & i=j=1
\end{cases}
\]To verify that the formula is correct, we can count the total number of characters by separating by footprint:
\begin{align}
& \text{(total $m\times n$ characters)} \\
&= \sum_{i=1}^m\sum_{j=1}^n \text{(characters with an $i\times j$ footprint)}\cdot \text{(size of $i\times j$ equiv. class)}\\
&= \sum_{i=1}^m\sum_{j=1}^n g(i,j) \cdot (m-i+1)(n-j+1) \\
&= 2^{mn}-1
\end{align}The last line was evaluated with Mathematica, and it actually worked! The reason for the “$-1$” is that we are excluding the “all-empty” character in our count.

Now that we have verified our formula for $g(i,j)$, we can substitute it in to the formula for $f(m,n)$ we derived earlier:
\[
f(m,n) = \sum_{i=1}^m\sum_{j=1}^n g(i,j)
\]Again, I relied on Mathematica to derive the analytic expression for this sum, and I obtained the following formula:

$\displaystyle
f(m,n) = \bigl(2^{m-1}-1\bigr) \bigl(2^{n-1}-1\bigr) 2^{(m-1) (n-1)}+2^{m n-1}
$

Given the relative simplicity of this final answer, I’m expecting there to be a much more elegant way to solve this problem than the approach I used. Let me know in the comments!

Solutions to special cases

Now that we have a general formula, we need only substitute the appropriate values for $m$ and $n$ to solve the problem. For the first problem, we find:
\[
f(3,2) = 44
\]Here is a picture that shows all $44$ characters. For each equivalence class, I chose the representative in the lower-left corner of the grid. I also indicated in red the number of elements in each equivalence class. As expected, if you sum all the red numbers you obtain $63 = 2^{6}-1$, which is the total number of non-empty characters.

For the extra credit problem, we find:
\[
f(6,4) = 15,\!499,\!264
\]

Making something out of nothing

This week’s Fiddler is a problem about composing functions. Here it goes:

Consider $f(n) = 2n+1$ and $g(n) = 4n$. It’s possible to produce different whole numbers by applying combinations of $f$ and $g$ to $0$. How many whole numbers between $1$ and $1024$ (including $1$ and $1024$) can you produce by applying some combination of $f$’s and $g$’s to the number $0$?

Extra Credit: Now consider the functions $g(n) = 4n$ and $h(n) = 1−2n$. How many integers between $-1024$ and $1024$ (including $-1024$ and $1024$) can you produce by applying some combination of $g$’s and $h$’s to the number $0$?

My solution:
[Show Solution]

Initially, we must start by applying $f$, otherwise we would just stay at zero. So for all intents and purposes, we can assume we start at $1$. At this point, it helps to write numbers out in binary (base two).

Applying $f(n)=2n+1$ has the net effect of tacking on a “1” to the end of the number in binary form, For example, if we start at $12$ (which is $1100$ in binary), then $f(12)=25$, which is $11001$ in binary.
Applying $g(n)=4n$ has the net effect of tacking on a “00” to the end of the number in binary form, so for example, if we start at $3$ (which is $11$ in binary), then $g(3)=12$, which is $1100$ in binary.

Now back to the original problem. Our goal is to count how many numbers between $1$ and $1024$ we can reach using compositions of $f$ and $g$. Since $1024=2^{10}$, let’s consider the more general problem of asking how many numbers between $1$ and $2^n$ we can reach. Let’s call this number $a_n$. Let’s look at the reachable numbers that have $k$ digits, and organize them in a table (in base 2):
\[
\begin{array}{c|l}
\text{digits} & \text{reachable numbers} \\ \hline
1 & 1 \\
2 & 11 \\
3 & 111, 100\\
4 & 1111, 1001, 1100\\
5 & 11111, 10011, 11001, 11100, 10000\\
\end{array}
\]The number of entries in row $k$ is simply $F_k$, the $k^\text{th}$ Fibonacci number. To see why, observe that to get to row $k$, we can start with the entries from row $k-1$ and apply $f$ (add a “$1$” to the end), or we can start with the entries from row $k-2$ and apply $g$ (add a “$00$” to the end). Since the first two rows each have one entry, we get the standard Fibonacci sequence (1,1,2,3,5,8,13,…).

Counting the reachable numbers up to $2^n-1$ means including all numbers with up to $n$ digits, so summing $F_1+F_2+\cdots+F_{n}$. However, we also want to include $2^n$. It’s clear from the pattern that this number is reachable whenever $n$ is even. Therefore, the reachable numbers $a_n$ is given by:
\[
a_n = F_1+\cdots+F_{n} + \begin{cases}
1 & n\text{ is even} \\
0 & n\text{ is odd}
\end{cases}
\]We can simplify this sum further. To see how, write:
\begin{align}
F_n &= F_{n+2}-F_{n+1}\\
F_{n-1} &= F_{n+1}-F_n \\
F_{n-2} &= F_n-F_{n-1} \\
\vdots\,\, &= \,\,\vdots\\
F_2 &= F_4-F_3\\
F_1 &= F_3-F_2
\end{align}Summing both sides, we get cancelations on the right-hand side:
\[
F_1+\cdots+F_{n} = F_{n+2}-F_2 = F_{n+2}-1
\]Therefore, we can simplify our formula and write:
\[
a_n = F_{n+2}-1+\frac{1}{2}\left( (-1)^n+1 \right)
\]Further simplification gets us our final answer:

$\displaystyle
a_n = F_{n+2}+\frac{1}{2}\left( (-1)^n-1 \right)
$

We can also find a closed-form expression if we use Binet’s formula:

$\displaystyle
a_n = \frac{\phi^{n+2}-\psi^{n+2}}{\sqrt{5}}+\frac{(-1)^n-1}{2}
$

where $\phi=\frac{1+\sqrt{5}}{2}$ and $\psi=\frac{1-\sqrt{5}}{2}$ are the golden ratio and its conjugate, respectively. The first several values of $a_n$ are:
\[
\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c}
n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
a_n & 1 & 1 & 3 & 4 & 8 & 12 & 21 & 33 & 55 & 88 & 144 \\
\end{array}
\]

The original problem asked about numbers up to $1024 = 2^{10}$, so we have:
\[
a_{10} = F_{12} = 144
\]

Extra credit

This problem is similar to the first part, but we have to take a bit more care with edge cases. In particular, the first part had the nice feature that applying $f$ always added one digit, and applying $g$ always added two digits (in base 2). This is (almost) still true. Applying $g$ still adds two digits, but applying $h$ does the following:

If the number is negative, it adds a one and flips the sign. For example: $h(-10)=21$ i.e., $-1010\mapsto 10101$.
If the number is positive, it adds a zero, flips the sign, then subtracts $1$. For example: $h(6)=-11$, i.e., $110\mapsto -1011$.

It can happen that applying $h$ will not increase the number of digits. For example, $h(4)=-7$, i.e., $100\mapsto -111$. Nevertheless, we can still make a table similar to how we did before, except we will not arrange numbers by digits. Instead, arrange them in such a way that the Fibonacci pattern remains true, like this:
\[
\begin{array}{c|l}
\text{row} & \text{reachable numbers} \\ \hline
0 & 1 \\
1 & -1 \\
2 & 11, 100 \\
3 & -101, -111, -100 \\
4 & 1011, 1111, 1001, 1100, 10000 \\
5 & -10101, -11101, -10001, -11001, -11111, -10100, -11100, -10000 \\
\end{array}
\]Note that the rows alternate positive and negative numbers. Also, row $k$ for $k\geq 1$ contains numbers with $k$ binary digits, except the even rows, which also contain the number $2^{k}$, which has $k+1$ digits. The reason for this discrepancy is so that we maintain the Fibonacci pattern. Now, we can see that row $k$ is formed by applying $h$ to row $k-1$, or applying $g$ to row $k-2$. Therefore, row $k$ contains $F_{k+1}$ numbers.

Now, we can see that summing rows $0$ through $k$ will give us reachable numbers between $-(2^{k}-1)$ and $2^{k}$. To make sure we include $-2^{k}$, we should also add one whenever $k$ is even. So far, we counted positive and negative reachable numbers, but what about zero? Since $g(0)=0$, zero is also reachable, so we should add one more to include it. Therefore, we find that:
\[
b_n = F_1+\cdots+F_{n+1} + 1 + \begin{cases}
1 & n\text{ is even} \\
0 & n\text{ is odd}
\end{cases}
\]Similarly to the previous case, we obtain the solution:

$\displaystyle
b_n = F_{n+3}+\frac{1}{2}\left( (-1)^n+1 \right)
$

or, using Binet’s formula,

$\displaystyle
b_n = \frac{\phi^{n+3}-\psi^{n+3}}{\sqrt{5}}+\frac{(-1)^n+1}{2}
$

The first several values of $b_n$ are:
\[
\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c}
n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
b_n & 3 & 3 & 6 & 8 & 14 & 21 & 35 & 55 & 90 & 144 & 234 \\
\end{array}
\]The original problem asked about numbers between $-1024$ and $1024$, so since $1024=2^{10}$, we have:
\[
b_{10} = F_{13}+1 = 234
\]

Möbius prism

This week’s Fiddler is a problem about a multi-sided Möbius prism:

Consider an three-dimensional prism whose bases are regular N-gons. I twist it and stretch it into a loop, before finally connecting the two bases. Suppose that my twist is by a random angle, such that the two bases are aligned when they are coonected. Among all whole number values of N less than or equal to 1,000, for which value of N will a randomly twisted regular N-gon prism have the most distinct faces, on average?

My solution:
[Show Solution]

Label the faces $\{1,2\dots,N\}$, and suppose we apply a twist of $k/N$ before connecting the bases together. We only need to consider $k\in\{1,\dots,N\}$ since adding any multiple of $N$ just adds a full rotation and changes nothing. In other words, rotating by $N$ is the same as not rotating at all.

To count the number of faces in the final shape, we can start from any face and follow that face around until we end up back where we started. Call this an “orbit”. All the numbered faces we cross along the way in a given orbit are in fact the same face, so the total number of faces is just the total number of orbits. By symmetry, each orbit has the same length, so we have:
\[
\text{#(faces)} = \text{#(orbits)} = \frac{N}{\text{(orbit length)}}
\]To find the orbit length, we can write a repeating list of all the faces, and then jump in steps of length $k$ until we end up at a multiple of $N$, which means we have returned to our starting point. In the example below, we have $N=6$ and $k=4$.
\[
\begin{array}{|cccccc|cccccc|cccc}
1 & 2 & 3 & \fbox{4} & 5 & 6 & 1 & \fbox{2} & 3 & 4 & 5 & \fbox{6} & 1 & 2 & 3 & \cdots \\
\end{array}
\]Therefore, as we orbit, we pass through $4 \to 2 \to 6 \to 4 \to \cdots$. This means that the faces $\{2,4,6\}$ in the original prism all belong to the same face in the Möbius prism. This orbit has length $3$, and by symmetry, all other orbits have length 3. Indeed, there is one other orbit: $\{1,3,5\}$. So two total orbits, and therefore two total faces. Based on the illustration above, it’s clear that the least common multiple (lcm) of $N$ and $k$ gives us the point where we return to the face labeled $N$. We can divide this by $k$ to find the length of the orbit:
\[
\text{(orbit length)} = \frac{\text{lcm}(N,k)}{k}
\]Substituting this into our previous equation, we have:
\[
\text{#(faces)} = \frac{N}{\text{(orbit length)}}
= \frac{N \cdot k}{\text{lcm}(N,k)}
= \text{gcd}(N,k)
\]where gcd is the greatest common divisor. In the last line, we used the fact that $\text{lcm}(m,n)\cdot\text{gcd}(m,n) = m \cdot n$. For the example above with $N=6$ and $k=4$, we have $\text{gcd}(6,4) = 2$, and indeed there are two orbits (and therefore, two faces).

The problem asks to find the average number of faces assuming the twist is random. Let’s call this quantity $f(N)$. Based on what we found so far, we have:
\[
f(N) = \frac{1}{N}\sum_{k=1}^{N} \text{gcd}(N,k)
\]The sum of gcd’s of a number is known as Pillai’s arithmetical function (OEIS A018804), and there are alternative formulas for it. One such formula is found by writing $N = p_1^{a_1}\cdots p_m^{a_m}$ (prime factorization), and then it turns out that:
\[
f(N) = \frac{1}{N}\prod_{i=1}^m\left( (a_i+1)p_i^{a_i}-a_i p_i^{a_i-1} \right)
\]This is still a complicated function, so we turn to a computer to evaluate it for $1 \leq N \leq 1000$ and figure out its maximum. Here is a plot of $f(N)$:

The maximum occurs when $N=840$, and in this case $f(840) = \frac{195}{14} \approx 13.93$.

Asymptotic growth

If we investigate this function for very large $N$, we observe the following.

The lower bound on the plot is easy; it corresponds to the case when $N=p$ is a prime. In this case, we can apply the formula and immediately obtain $f(p) = 2-\frac{1}{p}$, which explains why it tends to $f(p)=2$ in the limit.

The upper bound (maximum value of $f(N)$) is not as clear. To investigate, I looked at several of the top-performing $N$ values to see if their prime factorizations were special in any way (the red points in the plot above). Here is what I found:
\begin{align}
N &= p_1^{a_1} \cdots p_m^{a_m} \\
12 &= 2^2 \cdot 3 \\
60 &= 2^2 \cdot 3 \cdot 5 \\
120 &= 2^3 \cdot 3 \cdot 5 \\
840 &= 2^3 \cdot 3 \cdot 5 \cdot 7 \\
2520 &= 2^3 \cdot 3^2 \cdot 5 \cdot 7 \\
5040 &= 2^4 \cdot 3^2 \cdot 5 \cdot 7 \\
27720 &= 2^3 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \\
55440 &= 2^4 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \\
360360 &= 2^3 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \\
720720 &= 2^4 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \\
\end{align}It appears that the top performing $N$ values are made up of small consecutive primes. I don’t have a complete explanation for this phenomenon, but here are some observations that may be relevant.

A small prime raised to a large power is better than a large prime raised to a smaller power. Suppose $N = p^a$ is a power of a prime. Based on our formula, we have:
\[
f(p^a) = \frac{1}{p^a}\left( (a+1)p^a-ap^{a-1} \right) = 1+a\left(1-\frac{1}{p}\right)
\]So for a given $N$, we will get a larger value of $f(N)$ if it’s a small prime raised to a large power; so small primes are good!
A products of different primes is better than powers of the same prime. Suppose $p_1,\dots,p_m$ are distinct primes that are close together, so $p_i\approx p_j \approx p$. Note that:
\[
f(p_1 \cdots p_m) = \frac{(2p_1+1)\cdots (2p_m+1)}{p_1\cdots p_m} \approx \left(2+\frac{1}{p}\right)^m \sim 2^m
\]However, a power of the same prime yields something much smaller:
\[
f(p^m) = 1+m \left(1-\frac{1}{p}\right) \sim m
\]

So we should strive to use many distinct primes rather than repeating the same prime too many times.

This isn’t a complete explanation, but I think it illustrates the inherent trade-off present in maximizing $f(N)$.