Voluminous rectangular prisms

There are several rectangular prisms with integer edge lengths that have an internal diagonal of length $2024.$ What is the greatest volume among these prisms?

Let's say we have a retangular prism with length $\ell,$ width $w,$ and height $h.$ The volume is $V = \ell w h$ while the length of the internal diagonal is $L = \sqrt{\ell^2 + w^2 + h^2}.$ In this case, we then need to looks for all Pythagorean quadruples $a^2 + b^2 + c^2 = d^2$ that have $d=2024.$ While we certainly could use primitive Pythagorean quadruples for the odd divisors of $2024$ (namely, $11$, $23,$ and $253$), we might as well just brute force the entire thing and do a dumb search: In a series of nested loops, we can loop through $a = 1, \dots, 2024,$ $b = a, a+1, \dots, 2024,$ and $c = b, b+1, \dots, 2024$ and print out the triple $(a, b, c)$ any time that $a^2 +b^2 + c^2 = 2024^2.$ This yields the following forty-one quadruples:

$$\begin{align*} 24^2 + 640^2 + 1920^2 &= 2024^2 \\ 24^2 + 1152^2 + 1664^2 &= 2024^2 \\ 64^2 + 168^2 + 2016^2 &= 2024^2 \\ 64^2 + 1344^2 + 1512^2 &= 2024^2 \\ 96^2 + 152^2 + 2016^2 &= 2024^2 \\ 96^2 + 872^2 + 1824^2 &= 2024^2 \\ 96^2 + 936^2 + 1792^2 &= 2024^2 \\ 96^2 + 1088^2 + 1704^2 &= 2024^2 \\ 152^2 + 864^2 + 1824^2 &= 2024^2 \\ 168^2 + 1344^2 + 1504^2 &= 2024^2 \\ 192^2 + 856^2 + 1824^2 &= 2024^2 \\ 192^2 + 1304^2 + 1536^2 &= 2024^2 \\ 224^2 + 600^2 + 1920^2 &= 2024^2 \\ 224^2 + 672^2 + 1896^2 &= 2024^2 \\ 224^2 + 1176^2 + 1632^2 &= 2024^2 \\ 264^2 + 528^2 + 1936^2 &= 2024^2 \\ 264^2 + 1232^2 + 1584^2 &= 2024^2 \\ 280^2 + 576^2 + 1920^2 &= 2024^2 \\ 360^2 + 800^2 + 1824^2 &= 2024^2 \\ 360^2 + 1376^2 + 1440^2 &= 2024^2 \\ 368^2 + 1104^2 + 1656^2 &= 2024^2 \\ 424^2 + 480^2 + 1920^2 &= 2024^2 \\ 424^2 + 768^2 + 1824^2 &= 2024^2 \\ 424^2 + 1248^2 + 1536^2 &= 2024^2 \\ 480^2 + 576^2 + 1880^2 &= 2024^2 \\ 528^2 + 1144^2 + 1584^2 &= 2024^2 \\ 576^2 + 744^2 + 1792^2 &= 2024^2 \\ 576^2 + 928^2 + 1704^2 &= 2024^2 \\ 576^2 + 1216^2 + 1512^2 &= 2024^2 \\ 576^2 + 1368^2 + 1376^2 &= 2024^2 \\ 600^2 + 640^2 + 1824^2 &= 2024^2 \\ 672^2 + 936^2 + 1664^2 &= 2024^2 \\ 672^2 + 1176^2 + 1504^2 &= 2024^2 \\ 744^2 + 1088^2 + 1536^2 &= 2024^2 \\ 768^2 + 1304^2 + 1344^2 &= 2024^2 \\ 768^2 + 1304^2 + 1344^2 &= 2024^2 \\ 856^2 + 1248^2 + 1344^2 &= 2024^2 \\ 864^2 + 1216^2 + 1368^2 &= 2024^2 \\ 928^2 + 936^2 + 1536^2 &= 2024^2 \\ 936^2 + 1152^2 + 1376^2 &= 2024^2 \\ 1104^2 + 1104^2 + 1288^2 &= 2024^2 \end{align*}$$

The rectangular prism with integral edge lengths internal diagonal length of $2024$ with the largest volume is $1104 \times 1014 \times 1288$ which has volume $1,569,835,008.$ Note that this is not necessarily that far from the overall, non-integral solution of a cube with side length $2024 / \sqrt{3}$ which has volume $1,595,694,111.621353...$, which is only about $1.6\%$ larger than the volume of the integral rectangular prism, so not too shabby.

You've got be flipping kidding me!

Kyle and Julien are playing a game in which they each toss their own fair coins. On each turn of the game, both players flip their own coin once. If, at any point, Kyle’s most recent three flips are Tails, Tails, and Heads (i.e., TTH), then he wins. If, at any point, Julien’s most recent three flips are Tails, Tails, and Tails (i.e, TTT), then he wins.

However, both players can’t win at the same time. If Kyle gets TTH at the same time Julien gets TTT, then no one wins, and they continue flipping. They don’t start over completely or erase their history, mind you—they merely continue flipping, so that one of them could conceivably win in the next flip or two.

What is the probability that Kyle wins this game?

This game, like many coin flipping problems of its ilk, can be modeled as a Markov chain. There are two absorbing states, let's call them, $\textsf{WinJ}$ and $\textsf{WinK}$, and nine transient states, call them, $(i, j)$ where $i, j \in \{0, T, TT\},$ represent the state where Julien is in state $i$ and Kyle is in state $j.$ State $(0,0),$ which represents both the starting space and the case that both Julien and Kyle just flipped H and that Kyle's last three flips were not TTH, can transition to $(T,0)$, $(0,T)$, $(T,T)$ or itself, each with equal probability. On the other hand, we see that due to the tie breaker procedures, state $(TT, TT)$ can transition to $(0,0)$, $\textsf{WinJ}$, $\textsf{WinK}$ and $(TT,0),$ each with equal probability. We can similarly build up all of the other transitions Let's represent the probabilistic state of the system as $\pi = (p_\textsf{WinJ}, p_\textsf{WinK}, p_{(0,0)}, p_{(0,T)}, p_{(0,TT)}, p_{(T,0)}, p_{(T,T)}, p_{(T,TT)}, p_{(TT,0)}, p_{(TT,T)}, p_{(TT,TT)} ) \in [0,1]^{11},$ then the probability transition matrix can be represented as $$P = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0.25 & 0.25 & 0 & 0.25 & 0.25 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0.25 & 0 & 0.25 & 0.25 & 0 & 0.25 & 0 & 0 & 0 \\ 0 & 0.5 & 0.25 & 0 & 0 & 0.25 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0.25 & 0.25 & 0 & 0 & 0 & 0 & 0.25 & 0.25 & 0 \\ 0 & 0 & 0.25 & 0 & 0.25 & 0 & 0 & 0 & 0.25 & 0 & 0.25 \\ 0 & 0.5 & 0.25 & 0 & 0 & 0 & 0 & 0 & 0.25 & 0 & 0 \\ 0.5 & 0 & 0.25 & 0.25 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0.5 & 0 & 0.25 & 0 & 0.25 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0.25 & 0.25 & 0.25 & 0 & 0 & 0 & 0 & 0 & 0.25 & 0 & 0 \end{pmatrix}.$$ We can subdivide the transition matrix into the resolving states, $$R = \begin{pmatrix} 0 & 0 \\ 0 & 0 \\ 0 & 0.5 \\ 0 & 0 \\ 0 & 0 \\ 0 & 0.5 \\ 0.5 & 0 \\ 0.5 & 0 \\ 0.25 & 0.25 \end{pmatrix}$$ and the transitory states $$T = \begin{pmatrix} 0.25 & 0.25 & 0 & 0.25 & 0.25 & 0 & 0 & 0 & 0 \\ 0.25 & 0 & 0.25 & 0.25 & 0 & 0.25 & 0 & 0 & 0 \\ 0.25 & 0 & 0 & 0.25 & 0 & 0 & 0 & 0 & 0 \\ 0.25 & 0.25 & 0 & 0 & 0 & 0 & 0.25 & 0.25 & 0 \\ 0.25 & 0 & 0.25 & 0 & 0 & 0 & 0.25 & 0 & 0.25 \\ 0.25 & 0 & 0 & 0 & 0 & 0 & 0.25 & 0 & 0 \\ 0.25 & 0.25 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0.25 & 0 & 0.25 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0.25 & 0 & 0 & 0 & 0 & 0 & 0.25 & 0 & 0 \end{pmatrix}$$ such that we can represent the transition matrix $P$ in block form as $P = \begin{pmatrix} I & 0 \\ R & T \end{pmatrix}.$ If we start at particular state, say $\pi_0,$ then by the $n$th step, our probabilistic state is $$\pi_n = \pi_0 P^n = \pi_0 \begin{pmatrix} I & 0 \\ (I + T + T^2 + \dots + T^{n-1}) R & T^n \end{pmatrix}.$$ If we let $n \to \infty,$ then since $T^n \to 0$ and $I + T + T^2 + \dots + T^{n-1} \to (I - T)^{-1},$ we have that the ultimate transition matrix is $$\pi_\infty = \pi_0 \begin{pmatrix} I & 0 \\ (I - T)^{-1} R & 0 \end{pmatrix}.$$

Here, the probability that Kyle wins is given by the $p_\textsf{WinK}$ (2nd) entry in $\pi_\infty.$ Since we are starting at $\pi_0 = (0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0),$ and we are only concerned with $p_\textsf{WinK}$ we can instead of solving the entire matrix inverse of $I - T$ rather just solve the system of equations $$(I - T) x = R \begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0.5 \\ 0 \\ 0 \\ 0.5 \\ 0 \\ 0 \\ 0.25 \end{pmatrix}$$ and then taking the first coordinate. Choosing your favorite matrix alegbra software, programming language or, due to certain foibles with which you are burdened, a bunch of loose leaf paper and loads of patience, you get to the probability that Kyle will win as $$p_\textsf{WinK} = \frac{36367}{74368} = 48.9014....\%$$

It's polygon pull weather

Your goal is to squeeze two non-overlapping quadrilaterals within a unit circle (i.e., a circle with radius 1). The quadrilaterals can share common edges, parts of edges, or vertices, but their interiors may not overlap. Their vertices may also lie on the circle’s circumference.

What is the greatest combined area these quadrilaterals can have?

When it comes to fitting shapes inside a circle, the best guess for largest possible area will be a regular polygon. So let's see what configurations we can come up with for two smushed together quadrilaterals. If we have two quadrilaterals that don't share any edges whatsoever, then we're not trying very hard since we could just expand one or the other quadrilateral until they do have a nonempty intersection and in turn get a larger total area. Similarly, if we have quadrilaterals that only intersect in a portion of an edge, then we can enlarge one or the other of the quadrilaterals until the entire edge is shared and get a larger total area. If the quadrilaterals only intersect in a single vertex then either one or the other can be orthogonally rotated such that the resulting quadrilaterals are all

OK, so now that we've covered that we should share entire edges, let's cover two cases: If we have two quadrilaterals that share two sides, then at most there could only be $4$ vertices along the circle. This configuration would have a maximum area obtained by a square inscribed in the circle, which has an area of $2.$ If instead, we have two quadrilaterals that share exactly one side, then at most there could be $6$ vertices along the circle. The area of a regular hexagon inscribed in a unit circle is $\frac{3\sqrt{3}}{2} = 2.59807...$ which is the largest total area of two non-overlapping quadrilaterals within a unit circle.

But what if we wanted to stick to only four vertices along the circle and define $Z$ as the following sum: the area of the (convex) quadrilateral formed by all four of these points plus the area of the largest triangle (by area) formed by any three of these points. Given that the four distinct points can be anywhere on the unit circle, what is the greatest possible value of $Z$?

Let's assume that the four vertices are numbered in say clockwise order, $z_1$, $z_2$, $z_3$, and $z_4$. Let the measure of the angle between the radii connecting $z_i$ and $z_{i+1}$ be $\alpha_i,$ for $i = 1, 2,$ and $3.$ For completeness, let the measure of the angle between the radii connecting $z_4$ and $z_1$ is $\alpha_4 = 2\pi - \alpha_1 - \alpha_2 - \alpha_3.$ In this case, the area of the quadrilateral is given by $$A_\square = \frac{1}{2} \sum_{i=1}^4 \sin \alpha_i.$$ Similarly, the area of the triangle formed by $z_1,$ $z_2$ and $z_3$ is $$A_\triangle = \frac{1}{2} \sin \alpha_1 + \frac{1}{2} \sin \alpha_2 - \frac{1}{2} \sin (\alpha_1 + \alpha_2).$$ Extending this to all of the triangles gives us the formula for $$\begin{align*}Z = Z(\alpha_1, \alpha_2, \alpha_3, \alpha_4) &= \frac{1}{2} \sum_{i=1}^4 \sin \alpha_i + \frac{1}{2} \max \left\{ \sin \alpha_1 + \sin \alpha_2 - \sin ( \alpha_1 + \alpha_2 ) ,\right.\\ &\quad\quad\quad \sin \alpha_2 + \sin \alpha_3 - \sin ( \alpha_2 + \alpha_3 ),\\ &\quad\quad\quad \sin \alpha_3 + \sin \alpha_4 - \sin ( \alpha_3 + \alpha_4 ),\\ &\quad\quad\quad \left.\sin \alpha_4 + \sin \alpha_1 - \sin ( \alpha_4 + \alpha_1 ) \right\}.\end{align*}$$ Then all we need to do is optimize subject to $\alpha_1 + \alpha_2 + \alpha_3 + \alpha_4 = 2\pi.$ Without loss of generality, let's assume that the triangle between $z_1,$ $z_2$ and $z_3$ is (one of) the largest of the triangles, so that in some region of the optimal values of $\alpha_1, \alpha_2, \alpha_3, \alpha_4$ we have $$\tilde{Z} = \sin \alpha_1 + \sin \alpha_2 + \frac{1}{2} \sin \alpha_3 + \frac{1}{2} \sin \alpha_4 - \frac{1}{2} \sin ( \alpha_1 + \alpha_2 ).$$ In this case, we would have expect from the method of Lagrange multipliers that there is some $\lambda \in \mathbb{R}$ such that the following system of equations holds $$\begin{align*} \cos \alpha_1 - \frac{1}{2} \cos (\alpha_1 + \alpha_2) + \lambda &= 0 \\ \cos \alpha_2 - \frac{1}{2} \cos (\alpha_1 + \alpha_2) + \lambda &= 0\\ \frac{1}{2} \cos \alpha_3 + \lambda &= 0 \\ \frac{1}{2} \cos \alpha_4 + \lambda &= 0\end{align*}$$

From the last two equations, we can conclude that $\cos \alpha_3 = \cos \alpha_4,$ so since $\alpha_i \in [0,\pi],$ for $i = 1, 2, 3, 4$ we conclude that $\alpha_3 = \alpha_4.$ Similarly, from the first two equations, we can conclude that $\cos \alpha_1 = \cos \alpha_2,$ and that $\alpha_1 = \alpha_2.$ Therefore, we can reduce the Lagrange multiplier equations above, by setting $\eta = \alpha_1 = \alpha_2$ and $\eta = \alpha_3 = \alpha_4.$ In this case we have the following equations $$\begin{align*} \cos \zeta - \frac{1}{2} \cos 2\zeta + \lambda &= 0 \\ \frac{1}{2} \cos \eta + \lambda &= 0 \\ \zeta + \eta &= \pi\end{align*}$$ Further reducing to a single variable we see that from the last equation $\eta = \pi - \zeta,$ and the second equation reveals $$\lambda = -\frac{1}{2} \cos \eta = - \frac{1}{2} \cos (\pi - \zeta) = \frac{1}{2} \cos \zeta,$$ so we a single equation $$\frac{3}{2} \cos \zeta - \frac{1}{2} \cos 2\zeta = \frac{3}{2} \cos \zeta - \cos^2 \zeta + \frac{1}{2} = 0.$$ Solving this quadratic we get $\cos \zeta = \frac{3 - \sqrt{17}}{4},$ since the other root would be greater than $1,$ which in turn leads to $$\zeta = \cos^{-1} \frac{3 - \sqrt{17}}{4} \approx 1.85539928817...$$ From here, since $$\sin \zeta = \sqrt{ 1 - \cos^2 \zeta } = \sqrt{ \frac{3 \sqrt{17} - 5}{8} }$$ we get an optimal $Z$ of $$\begin{align*}\hat{Z} = Z( \zeta, \zeta, \pi - \zeta, \pi - \zeta ) &= 2\sin \zeta + \sin (\pi - \zeta) - \frac{1}{2} \sin 2\zeta \\&= 3 \sin \zeta - \sin \zeta \cos \zeta \\ &= (3 - \cos \zeta) \sin \zeta \\&= \left( 3 - \frac{3 - \sqrt{17}}{4} \right) \sqrt{ \frac{3 \sqrt{17} - 5}{8} } \\&= \frac{\sqrt{214 + 102 \sqrt{17}} }{8} \approx 3.14880129428....\end{align*}$$

Enumeration of triambuses? Rhombangles?

Earlier this month, I watched La Vuelta, one of the three grand tours of cycling (a trio that includes the Tour de France). I noticed the peloton—the main group of riders—took on an aerodynamic profile that sometimes looked like a triangle, sometimes looked like a rhombus, and sometimes looked somewhere in between.

For example, the figure below shows the four possible formations between a triangle and a rhombus when the peloton’s maximum width is four riders:

For certain numbers of riders, multiple formations like these are possible. In particular, there are two formations with 15 riders: a triangle that’s five riders wide at the base and an almost-rhombus that’s four riders wide in the middle, but missing the bottommost rider, as shown below.

After 15, what is the next smallest number of riders that similarly has two distinct formations between a triangle and a rhombus?

Taking a hint from the formations for $N=15$ riders, let's try to find the formula for all number of riders that have two formations between a triangle and a rhombus where one formation is a triangle and the other has one more row. Let's denote these numbers as $N_k^{(1)}.$ Let's start with a triangle with $n$ rows, then we could get one triangle of $n+k$ rows, and another formation by adding $k+1$ rows of descending length, from $n-1$ through $n-k-1.$ In this case, in the first formation, there are $\sum_{i=1}^k (n+i) = kn + \frac{k(k+1)}{2}$ riders added beyond the initial triangle. In the second formation, there are $\sum_{i=1}^{k+1} (n-i) = (k+1)n - \frac{(k+1)(k+2)}{2}$ additional riders. In this case we can then solve for $n$ in terms of $k$ to see that $$kn + \frac{k(k+1)}{2} = (k+1)n - \frac{(k+1)(k+2)}{2} \Rightarrow n = \frac{k(k+1)}{2} + \frac{(k+1)(k+2)}{2} = (k+1)^2.$$ Thus, for any $k \in \mathbb{N},$ $N_k^{(1)}$ is number of riders in a triangle with $(k+1)^2 + k$ rows, that is $$N_k^{(1)} = \frac{(k+1)(k+2)(k^2+3k+1)}{2}.$$

We can continue to define more configurations, e.g., let's say all number of riders that have two formations between a triangle and a rhombus where one formation is a triangle and the other has $\ell$ more rows, that is, $N^{(\ell)}_k.$ For the case of $\ell = 2,$ we would have $$\sum_{i=1}^k (n+i) = kn+\frac{k(k+1)}{2} = (k+2)n - \frac{(k+2)(k+3)}{2} = \sum_{i=1}^{k+2} (n-i),$$ which would imply that $$2n = \frac{k(k+1)}{2} + \frac{(k+2)(k+3)}{2} = k^2 + 3k + 3 = (k+1) (k+2) + 1;$$ however, since $(k+1)(k+2)$ is even, $(k+1) (k+2) + 1$ is always odd for all k, so there can be no solutions and there are no $k$ for which $N^{(2)}_k$ is defined. Luckily, all is not lost since as soon as we reach $\ell = 3,$ things start getting somewhat better. For $\ell = 3$, we have $$\sum_{i=1}^k (n+i) = kn+\frac{k(k+1)}{2} = (k+3)n - \frac{(k+3)(k+4)}{2} = \sum_{i=1}^{k+3} (n-i),$$ which would imply that $$3n = \frac{k(k+1)}{2} + \frac{(k+3)(k+4)}{2} = k^2 + 4k + 6 = (k+3)(k+1) + 3,$$ that is, $$n = \frac{(k+1)(k+3)}{3} + 1, \,\,\,\text{for $k \equiv 0, 2 \!\! \mod 3.$}$$ So since the total number of riders is the same as a triangle of $n+k$ rows, we have $$N^{(3)}_k = \frac{(k+1)(k+6)(k^2+7k+9)}{18},$$ whenever $k \equiv 0, 2 \mod \!\! 3.$ Similarly, we can find $$N_k^{(4)} = \frac{(k+2)(k+7)(k^2+9k+10)}{32},$$ whenever $k \equiv 1,2 \mod \!\! 4$ and $k \gt 2$ and $$N_k^{(5)} = \frac{(k^2+11k+15)(k^2+11k+20)}{100},$$ whenever $k \equiv 0, 4 \mod\!\!5$ and $k \gt 3.$

Though it is certainly possible that there might be others, I am somewhat confident that the next smallest number of riders with two or more formations is $N_2^{(3)} = 36.$ I am less confident, but will put it out there regardless, that $1275$ is the smallest number of riders that has three different formations, since we have both $N_9^{(3)} = N_{10}^{(4)} = 1275.$ In particular, the three formations for $1275$ riders are (a) a triangle of $50$ rows; (b) a triangle with $40$ rows, followed by $14$ rows of descending length; or (c) a triangle of $41$ rows, followed by $13$ rows of descending length.

For completeness, my working version of the sequence for number of riders that can form multiple triambuses or rhombangles or whatever we want to call them is: $$15, 36, 60, 66, 78, 95, 190, 210, 253, 325, 390, 406, 435, 518, 861, 903, 946, 1275, 1351, 1540, 1661, 2346, 2556, 2775, 3081, 3452, 3486, 4005, 4064, ....$$ However, more accurately, we can just throw on the working conditions, that it is the sequence of all numbers of riders that can form multiple triambuses where the overall number of rows in the different triambus formations differs by less than the index where I gave up, er, I mean less than $6$.

Bobbin' and weavin'

A weaving loom set comes with a square with equally spaced hooks along each of its sides, as well as elastic bands that can be attached to the hooks.

Suppose a particular weaving loom has $N$ hooks on each side, evenly spaced from one corner to another (i.e., there are two hooks on the two corners and $N−2$ hooks between them). Let’s label the hooks along one side $A_1$ through $A_N$, the hooks on the next clockwise side $B_1$ through $B_N$ (with $A_N$ and $B_1$ denoting the same hook), the hooks on the third clockwise side $C_1$ through $C_N$, and the hooks on the final side $D_1$ through $D_N$.

Next, let’s use a whole bunch of elastic bands to connect hooks $A_1$ and $B_1$, $A_2$ and $B_2$, $A_3$ and $B_3$, and so on, up to $A_N$ and $B_N$. When $N = 100$, here’s what the loom looks like:

As $N$ increases, what is the shape of the curve formed by the edges of the bands?

Let's set up the framework, by assuming that the weaving loom, no matter the value of $N$, is the unit square $[0,1] \times [0,1].$ So that for instance $A_i = (0, \frac{N-i}{N-1})$ and $B_i = (\frac{i-1}{N-1}, 0),$ for $i = 1, \dots, N.$ The band connecting $A_i$ to $B_i$ can be represented by the line $$y = \frac{N-i}{N-1} \left(1 - \frac{N-1}{i-1} x\right) = \frac{N-i}{N-1} - \frac{N-i}{i-1} x.$$ Since we are primarily worried about the aggregate curve that is traced out by all of these lines, we really want to have $$f_N(x) = \max_{i = 2, \dots, N} \left\{ \frac{N-i}{N-1} - \frac{N-i}{i-1}x \right\}$$ which will eventually form a continuously differentiable function $f(x) = \lim_{N\to \infty} f_N(x).$

The interval on why the line from $A_i$ to $B_i$ will be maximal is $\left[ \frac{(i-1)(i-2)}{(N-1)^2}, \frac{i(i-1)}{(N-1)^2} \right]$ and the midpoint of this interval is $x_i = \left(\frac{i-1}{N-1}\right)^2.$ If we can find some convex $f$ such that $f_N(x_i) = f(x_i)$ for each $i = 2, \dots, N$ and $$\frac{d}{dx} f(x_i) = -\frac{N-i}{i-1},$$ for each $i = 2, \dots, N,$ then $f(x) = \lim_{N \to \infty} f_N(x)$ for all $x \in [0,1],$ since convex functions are the pointwise supremum of all affine minorants, up to and including their subdifferentials. So in particular, we see that $$-\frac{N-i}{i-1} = -\frac{N-1 - (i-1)}{i-1} = 1 - \frac{1}{\sqrt{x_i}},$$ for each $i = 2, \dots, N.$ Therefore, our best guess would be $$f(x) = f(0) + \int_0^x (1 - \frac{1}{\sqrt{t}}) dt = f(0) + x - 2\sqrt{x}.$$ Since the first band from $A_1$ to $B_1$ is along the $y$-axis, we should define $f(0) = 1,$ so that the weaver's loom always traces out a lower approximation of the convex function $$f(x) = 1 -2\sqrt{x} + x = (\sqrt{x} - 1)^2.$$ In particular, we can verify that $$f_N(x_i) = \frac{N-i}{N-1} - \frac{N-i}{i-1} x_i = \left( \frac{N-i}{i-1} \right)^2 = \left( \frac{i-1}{N-1} - 1\right)^2 = f(x_i),$$ and since $\frac{d}{dx}f(x_i) = -\frac{N-i}{i-1}$ for each $i = 2, \dots, N,$ by design, so we have confirmed that $f(x) \geq f_N(x)$ for all $N$ and $x \in [0,1]$ and the $f_N(x) \uparrow f(x)$ for all $x \in [0,1].$

Let's now go further and quadruple the number of bands placed on the weaving loom. In addition to the band connecting each $A_i$ and $B_i,$ you also place bands connecting $B_1$ and $C_1$, $C_1$ and $D_1$, and $D_1$ and $A_1$. You do this for all the sets of hooks from $1$ through $N,$ so that a total of $4N$ bands have been placed. When $N =100$, here is what the loom looks like:

As N increases, what fraction of the loom’s area lies between the four sets of bands? In other words, what fraction of the square above does the central white region make up?

We can skip to the end with our limiting curve of $f(x) = (\sqrt{x}-1)^2$ from the first portion of the problem, and then by symmetry take the area below the line $y = \frac{1}{2}$ and above $f(x)$ so long as $0 \leq x \leq \frac{1}{2}.$ This should give us one fourth of the answer. In particular, we see that the curve $y=f(x)$ intersects the line $y = \frac{1}{2}$ at $x = \left( 1 \pm \frac{\sqrt{2}}{2} \right)^2 = \frac{3}{2} \pm \sqrt{2}$ where only the negative sign gives a feasible answer less than $x = \frac{1}{2}$. Since we've defined the entire loom to have unit area, the fraction of loom made up by the white area as $N \to \infty$ is given by $$A = 4 \int_{\frac{3}{2}-\sqrt{2}}^\frac{1}{2} \left( \frac{1}{2} - (\sqrt{x} - 1)^2 \right) \,dx = \left[ \frac{16}{3}x^{3/2} -2x^2 -2x \right]_{\frac{3}{2} - \sqrt{2}}^\frac{1}{2} = \frac{8\sqrt{2}-10}{3} = 0.43790...$$

Fiddle Eagles, Fiddle!

You’re betting on the final two football games of the season for your home team, the Fiddle-delphia Eagles. Thanks to the wonders of time travel, you happen to know that the Eagles will win one game and lose the other. Unfortunately, you can’t remember in which order they do so. Maybe the Eagles win the first game and lose the second, or maybe they lose the first and win the second.

You have $\$100$, of which you can bet any amount (including fractions of pennies) that the Eagles will win. So if you bet $x$ dollars on the first game and the Eagles win, you’ll have $100+x$ dollars to bet on the second game. But if the Eagles lose that first game, you’re left with $100−x$ dollars to bet on the second game.

You want to implement a betting strategy that guarantees you’ll have as much money as possible after both games. If you did so, then after the two games how much money would you be guaranteed to have?

In this case, where you know there are only two outcomes for the final two games (WL or LW), then you know with perfect clarity what the outcome of the final game is once you observe the outcome of the first game. Now here's where we get into some semantics, what exactly does "you're betting ... for your home team" mean? If you are just betting for either the Figgles as they are affectionately known or their opponents, then you can end up with a guaranteed $\$200$ by betting nothing on the first game, then doubling up on the second game with the sure lock. However, that wouldn't be a very fun answer, so let's instead assume that we can only bet on the Figgles to win and that the question involves deciding how much to optimally bet for the first game and the second game.

Assume that we bet $x \in [0,100]$ on the first game, observe outcome $o \in \{W, L\}$ and then bet $y \in [0, U(x,o)]$ where $$U(x,o) = \begin{cases} 100+x, &\text{if $o = W$;}\\ 100-x, &\text{if $o = L$}\end{cases}$$ on the second game. Since we know that if $o = W,$ then the Figgles will lose the second game and vice versa, we see that the final money balance will be $$V(x, y, o) = \begin{cases} 100 + x - y, & \text{if $o = W$;}\\ 100 - x + y & \text{if $o = L$}\end{cases}$$ then the problem becomes $$\max_{x, y} \min \{ V(x,y, W), V(x,y, L) \}.$$ Since this is multistage, we should first optimize the choice of $y$ in each case. In particular $\hat{y}(W) = 0,$ since if the Figgles won the first game they will lose the second and $\hat{y}(L) = 100 -x,$ since you might as well double up everything on the sure win knowing that the Figgles lost the first game.

So we can reduce the problem by introducing $$\hat{V}(x,o) = V(x, \hat{y}(o), o) = \begin{cases} 100 + x, &\text{if $o = W$;}\\ 2 ( 100 - x ), &\text{if $o = L$}\end{cases}$$ and then solving for the optimal strategy we get an ending money balance of $$\max_{x \in [0,100]} \min \{ \hat{V}(x, W), \hat{V}(x, L) \} = \max_{x \in [100]} \min \{ 100 -x, 200 - 2x \} = 133.\bar{3}$$ when originally wagering $\hat{x} = 33.\bar{3}$ on the first game.

Seeing the forest for the cylinders

You find yourself amidst what appears to be an infinite grid of trees. For the purposes of this puzzle, let’s suppose each tree is a perfect cylinder. You are at the point $(0, 0),$ but there’s a tree with a radius of $r_1 = 0.25$ units (and diameter $0.5$ units) centered at every other point in the plane with integer coordinates.

Of course, you can’t actually see infinitely many trees. Most of them are obscured by the trees immediately around you. As you look around in all directions, how many distinct trees are you able to see?

Let's set up the generic problem, with some unknown radius $r \gt 0,$ then we can try to solve each of the pieces of this fiddle, er, riddle.

Assume that I am sitting at the origin and I look along the line $y=m x.$ If we assume for the time being that each of these perfectly cylindrical trees were see through, then I could see a tree centered at $(a,b) \in \mathbb{Z}^2$ if and only if the set $$\{ (x,y) \mid y = mx, (x-a)^2 + (y-b)^2 = r^2 \} \ne \emptyset.$$ Simplifying a bit, I could see any tree centered at $(a,b)$ provided that $$(x-a)^2 + (mx - b)^2 -r^2 = (1+m^2) x^2 -2( a + bm) x + (a^2 + b^2 - r^2) = 0$$ has a solution, that is, if and only if the discriminant $$\begin{align*}0 \leq \Delta( m \mid a, b, r ) &= 4(a + bm)^2 - 4(1 + m^2) (a^2 + b^2 - r^2) \\ &= 4 ( -(b^2 - r^2) + 2 ab m - (a^2 - r^2) m^2 ).\end{align*}$$ Rearranging a bit, and solving for $m$ we see that these translucent trees would be visible if and only if $$\frac{ab - r \sqrt{(a+b)^2 - r^2}}{a^2 - r^2} \leq m \leq \frac{ab + r \sqrt{(a+b)^2 - r^2}}{a^2 - r^2}.$$ However, since we don't have translucent cylindrcal trees, if we are looking along $y = mx$ then we could only see the two trees in $$(\hat{a}(m), \hat{b}(m)) \in \arg\min \left\{ |a| + |b| \left|\right. \frac{ab - r \sqrt{(a+b)^2 - r^2}}{a^2 - r^2} \leq m \leq \frac{ab + r \sqrt{(a+b)^2 - r^2}}{a^2 - r^2} \right\}.$$ Due to all of the symmetry of this problem, only method is to allow $m$ to slowly increase from $m = 0$ to $m = 1,$ and then rely on symmetry (since there is nothing uniquely special about the trees in the lower half of the first quadrant) and inclusion/exclusion (since some of the trees will be double counted) to answer either the question of how many tress do we see or which trees is furthest away.

So in particular, we see that for $m \in [0, \frac{r}{\sqrt{1-r^2}}],$ I would be looking at the tree at $(1,0).$ Similarly, for any $m \in [\frac{1-r\sqrt{2-r^2}}{1-r^2}, 1],$ I would be looking at the tree centered at $(1,1).$ So in particular for $r = 0.25,$ we have filled in the set $$m \in [0, \frac{\sqrt{15}}{15}] \sqcup [\frac{16-\sqrt{31}}{15}, 1]$$ covered by $(1,0)$ and $(1,1).$ The next smallest tree (based on the $1$-norm) is centered at $(2,1),$ which can be seen for any $m \in [ \frac{32-\sqrt{79}}{63}, \frac{32 + \sqrt{79}}{63} ].$ At this point we still have only filled a disjoint union of intervals with $(1,0),$ $(1,1)$ and $(2,1),$ so filling in the remaining gaps, in the translucent tree problem we would be able to see the tree centered at $(3,1)$ for any $m \in [\frac{48-\sqrt{159}}{143}, \frac{48+\sqrt{159}}{143} ],$ but since $\frac{48 + \sqrt{159}}{143} \gt \frac{32 - \sqrt{79}}{63} \gt \frac{\sqrt{15}}{15} \gt \frac{48-\sqrt{159}}{143}$, I can only see the tree $(3,1)$ for $m \in (\frac{\sqrt{15}}{15}, \frac{32 - \sqrt{79}}{63}).$ Similarly, I can see $(3,2)$ for any $m \in (\frac{48 + \sqrt{159}}{143}, \frac{16-\sqrt{31}}{15}),$ so in totality there are 8 trees in the lower half of the first quadrant that can be seen, that is, $$T(m) = \begin{cases} (1,0), & m \in [0, \frac{\sqrt{15}}{15}]; \\ (3, 1), & m \in ( \frac{\sqrt{15}}{15}, \frac{48 - \sqrt{159}}{143}); \\ (2, 1), & m \in [ \frac{48 - \sqrt{159}}{143}, \frac{48 + \sqrt{159}}{143} ];\\ (3,2), & m \in (\frac{48 + \sqrt{159}}{143}, \frac{16-\sqrt{31}}{15}); \\ (1,1), & m \in [\frac{16 - \sqrt{31}}{15}, 1].\end{cases}$$

So since there are 5 in the lower half of the first quadrant, we should multiply by 8 to get to 40 trees in the whole plane. However, this would double count the eight points $(\pm 1, 0),$ $(0, \pm 1),$ $(\pm 1, \pm 1),$ so we need to subtract 8 from the total, leaving $32$ trees of diameter $r=0.25$ can be seen from the origin.

Order of Operations

You are writing an expression using the whole numbers $1, 2, 3, 4, 5, \dots, 4N + 1,$ for some nonnegative integer $N$ and the operations of addition, subtraction, multiplication, and division. Importantly, you must use each number exactly once and each operation exactly $N$ times. Also, you can use as many parentheses as you would like. No concatenation of the digits is allowed (i.e., you can’t combine $2$ and $3$ to make the number $23$). What is the largest value you can generate, using the nine digits and eight operations?

The largest number generated using integers numbers $1, \dots, 4N+1$ and the four operations provided that each operation is used $N$ times is $$m(N) = (4N+1) (6N+1)^N.$$

To prove this we will need to argue first that $m(N)$ is equivalent to the number $\hat{m}(N),$ which is the largest number that can be constructed using only $N$ multiplications and $N$ additions using the number $2N+1, 2N+2, \dots, 4N, 4N+1.$ Certainly, any arithmetic expression using only $N$ multiplications and $N$ additions and the numbers $2N+1, \dots, 4N+1$ each once, say $x = f(2N+1, \dots, 4N+1),$ can be made into an aritchmetic expression using each of the integers $1, \dots, 4N+1$ once and each operation exactly $N$ times, by simply letting $$x = g(1, \dots, 4N+1) = \frac{f(2N+1, \dots, 4N+1)}{ (2N - (2N-1)) \cdot \cdots \cdot (2 - 1) }.$$ Therefore, we must have $m(N) \geq \hat{m}(N).$ We can reasonably hand-wave that it cannot be the case that $m(N) \gt \hat{m}(N),$ since that would imply that the largest possible outcome either consists of dividing by some non-unit divisor or subtracting some integer from a larger arithmetic expression. Both of which yield contradictions.

OK, so we have reasonably almost halved the problem and can now focus on only a problem of $N$ multiplications, $N$ additions and the integers $2N+1, \dots, 4N+1.$ Similar to the hand-wavey arguments above, it is straightforward that $\hat{m}(N)$ has the form $$x_1 \cdot (x_2 + x_3) \cdot \cdots \cdot (x_{2N} + x_{2N+1})$$ for some choice of $x = (x_1, \dots, x_{2N+1}) \in \mathfrak{X}$ where $$\mathfrak{X} := \{ (x_1, \dots, x_{2N+1}) \in \{2N+1, \dots, 4N+1\}^{(2N+1)} \mid x_i \ne x_j, \forall i \ne j \}.$$ With all of that hand-waving done, the only thing that is left to do is decipher the appropriate, maximal assignment of the variables $x = (x_1, \dots, x_{2N+1}) \in \mathfrak{X}.$

The AM-GM inequality states the arithmetic mean of nonnegative numbers is always greater than or equal to the geometric mean of those same numbers, that is, for any positive integer $k$ and any real numbers $y_1, \dots, y_k \geq 0,$ $$\frac{y_1 + \cdots + y_k}{k} \geq \sqrt[k]{y_1 \cdot \cdots \cdot y_k}.$$ So with the help of said AM-GM inequality, for any choice of variable assignments $x = (x_1, \dots, x_{2N+1}) \in \mathfrak{X},$ $$\begin{align*} x_1 \cdot (x_2 + x_3) \cdot \cdots \cdot (x_{2N} + x_{2N+1}) &= x_1 \prod_{i=1}^N (x_{2i} + x_{2i+1})\\ &\leq x_1 \left( \frac{ \sum_{i=1}^N (x_{2i} + x_{2i+1}) }{ N } \right)^{N} \\ &= x_1 \left( \frac{ \sum_{i=2}^{2N+1} x_i }{N} \right)^N\\ &= x_1 \left( \frac{(2N+1)(3N+1) - x_1}{N} \right)^N,\end{align*}$$ where the last equality comes from the fact that $\sum_{i=2N+1}^{4N+1} i = (2N+1)(3N+1).$ Since the derivative of the right-hand side of the inequality is positive whenever $x_1 \lt \frac{(2N+1)(3N+1)}{N},$ and $\frac{(2N+1)(3N+1)}{N} \gt 4N+1$ for all nonnegative integers $N,$ if we want to maximize the right-hand side of the inequality for the choice of $x_1 \in \{2N+1, \dots, 4N+1\},$ we obtain the upper bound for $$\begin{align*}\hat{m}(N) &\leq (4N+1) \left( \frac{(2N+1)(3N+1) - (4N+1)}{N} \right)^N\\ &= (4N+1) \left( \frac{6N^2 + 5N + 1 - (4N+1)}{N} \right)^N\\ &= (4N+1) (6N+1)^N.\end{align*}$$ On the flip side, this upper bound is actually achieved by $\hat{x} \in \mathfrak{X}$ such that $$\begin{align*} \hat{x}_1 &=4N+1, \\ \hat{x}_2 &= 2N+1,\\ \hat{x}_3 &= 4N, \\ \hat{x}_4 &= 2N+2, \\ \hat{x}_5 &= 4N-1,\\ &\dots, \\ \hat{x}_{2i} &= 2N+i,\\ \hat{x}_{2i+1} &= 4N-i+1,\\ &\dots, \\ \hat{x}_{2N} &= 3N, \\ \hat{x}_{2N+1} &= 3N+1\end{align*}$$ so we have "proven" (via some hand waving) that $$m(N) = \hat{m}(N) = (4N+1) (6N+1)^N.$$ In particular, the first few values of $m(N)$ are given by 35, 1,521, 89,167, 6,640,625, and 601,212,171 for $N= 1, 2, 3, 4,$ and $5,$ respectively. I smell a new OEIS entry coming on ...

New Riddle Service .... Who Dis?

N.B.Given the new iteration of the Riddler, there are those who might surmise that I would change the name of my Riddler answer blog from on of the aliases of the Batman villain to some fiddling pun, like, I'm just spitballing here, I dunno... Stradi's Various Answers Shop, but I am lazy, so Ed Nigma lives on!

Suppose I start with a strip of paper that’s 10 inches long and 1 inch wide. I twist it once and attach the two 1-inch edges together, forming a Möbius strip. Finally, I draw a dot somewhere in the center of the strip—that is, the dot is half an inch away from both edges.

Naturally, the distance between any two points on my strip is the shortest path between them, as the ant crawls. By that, I mean that such paths can go over an edge to the other “side” of the strip (“side” in quotes because it’s all really the same side, after all), just as an ant would crawl around the edge of the paper. There is a unique point on the strip that is the farthest distance from my dot. What is this distance?

We can represent the strip of paper as a $10" \times 1"$ rectangle that has two (2) $10" \times 0.5"$ rectangles stacked immediately above and immediately below it. The two smaller rectangles represent the ``other side'' of the strip. Since this is a M\"{o}bius strip, the orientation of the left and right sides of the rectangles are reversed, so for instance lower left and upper right corners of the 10" \times 1" rectangle are the same point and same with the upper left and lower right. Meanwhile, the upper edge of the upper smaller rectangle and lower edge of the lower smaller rectangle are the same. Additionally, the midpoint of left side of the $10" \times 1"$ rectangle is simultaneous the upper right corner of the upper smaller rectangle and the lower right corner of the lower smaller rectangle, and vice versa with the midpoint of the right side of the larger rectangle. That was confusing enough, so let's set up a frame of reference and see if we can measure something, eh?

Assume the larger rectangle is given by $\{ (x,y) \mid 0 \leq x \leq 10, |y| \leq 0.5 \},$ with the upper and lower smaller rectangles given by $\{ (x,y) \mid 0 \leq x \leq 10, 0.5 \leq \pm y \leq 1 \},$ respectively. Finally, without loss of generality, assume that your mark is made at the origin. Then since the points $(0,0)$, $(10,1)$ and $(10,-1)$ are synonymous, the ``as the ant crawls'' metric is given by $$d(x,y) = \min \{ \sqrt{x^2+y^2}, \sqrt{ (x-10)^2 + (y-1)^2 }, \sqrt{ (x-10)^2 + (y+1)^2 } \}.$$ Maximizing this metric over the set $\{ (x,y) \mid 0 \leq x \leq 10, |y| \leq 1 \}$ gives the maximum possible distance away of $$d^* = \max_{ 0\leq x \leq 10, |y| \leq 1 } d(x,y) = 5.05,$$ which is obtained at the point $(x^*, y^*) = (5.05, 0)$ which is synonymous with the points $(4.95, \pm 1).$

Middle Square Madness

This week, let’s look at the middle-square method for generating pseudorandom four-digit numbers. First, we start with a four-digit number, such as $9,876.$ If we square it, we get the eight-digit number $97,535,376.$ Our next pseudorandom number is taken from the middle four digits of that square: $5,353.$ And to get the next pseudorandom number, we can square $5,353,$ which gives us $28,654,609,$ the middle four digits of which are $6,546.$

Of course, many four-digit numbers have a square that’s seven digits rather than eight. And in a sequence of middle-square numbers, you also might encounter smaller numbers whose squares have six or fewer digits. In these cases, you can append zeros to the beginning of the square until you have eight total digits, and once again take the middle four digits.

No matter what initial four-digit number you pick, your sequence of pseudorandom numbers will eventually repeat itself in a loop. If you want the longest sequence of such numbers before any repetition occurs, what starting number should you pick? And how many unique numbers are in the sequence?

Mathematically, the middle square pseduorandom operation can be written as the following recurrence $$x_{n+1} = ( x_n \mod 1000000 ) // 100, \, \forall n \geq 1.$$ That is, first take the remainder when dividing by a million then use the integer divisor when dividing by $100.$ The assertion (which makes sense since there are only no more than $100,000$ possible values to take) is that eventually there will be some $n$ such that $$x_{n+1} \in \{ x_1, \dots, x_n \}.$$ This means that for any initial value of $x_1,$ we can generate the sequence of successive iterations of the middle square recurrence, each time checking the stopping criterion above. While there may certainly have been more elegeant techniques, I brute forced my way through to a solution of using $6,239$ as an inital value, which results in sequence of $111$ unique numbers before any repetitions.

Interestingly, though perhaps owing to a benevalent question-crafter more than anything else, there is only one such initial value that yields a sequence of $111$ unique numbers before repetitions, and all other positive integers $n \lt 111$ have at least $3$ initial values that lead to a sequence of $n$ unique values before repetitions. For instance, there are three fixed points of the middle square recurrence, namely $2,500$, $3,792$ and $7,600,$ where each exhibits $$x_2 = (x_1 \mod 1000000) // 100 = x_1.$$ Similarly, there are $3$ initial values that lead to a sequence of $110$ unique values before repetitions, namely $3,416$, $4,655$, and $9,251.$

Laissez le bon temps rouler, or have a flipping good time!

Starting a competition with the flip of a coin (say, to determine possession of a ball) is so boring! Instead, let’s give the captain of one team a fair coin and the captain of the other team a fair die. The captain with the coin will flip it at the same time the other captain rolls the die. They continue doing this until the coin is the same (whether heads or tails) for three consecutive flips or the number that comes face-up on the die is the same for two consecutive rolls.

On average, how many coin flips will it take to get three in a row? And how many die rolls will it take to get two in a row?

Extra credit: While the numbers of flips and rolls may often be the same, which team — the team with the coin or the team with the die — is more likely to win the toss/roll? (That is, which is more likely to happen sooner?)

Let's tackle the expectation case first. Let's say that $R$ is the randome number of rolls to get two in a row on a fair die and $F$ is the random number of flips to get three in a row. Let's denote the outcome of the $k$th roll as $r_k$ and similarly the outcome of the $k$th flip as $f_k.$

Assume without loss of generality that the roller's first roll is some $i \in \{1, 2, 3, 4, 5, 6\}.$ Then the second roll will either be $i$, with probability $1/6,$ or some $j \ne i,$ with probability $5/6.$ So we have $$\mathbb{E}[R \mid r_1 = i] = \frac{1}{6} \mathbb{E}[ R \mid r_1 = r_2 = i ] + \frac{5}{6} \mathbb{E}[ R \mid r_1 = i \ne j = r_2 ].$$ In the former case, $R \equiv 2$ if $r_1 = r_2 = i$; alternatively, in the latter case, $R \mid r_1 = i \ne j = r_2$ is equivalent to $1 + R \mid r_1 = j.$ Due to the arbitrariness of the choice of initial roll realization, $\mathbb{E} [ R \mid r_1 = i ] = \mathbb{E} [ R \mid r_1 = j ],$ for all $i, j \in \{ 1, 2, 3, 4, 5, 6 \}$ we have $$\mathbb{E}[ R \mid r_1 = i ] = \frac{1}{6} 2 + \frac{5}{6} ( 1 + \mathbb{E} [ R \mid r_1 = i ] )$$ or equivalently, $$\mathbb{E} [ R \mid r_1 = i ] = 7.$$ So therefore, the expected number of rolls is $$\mathbb{E} [ R ] = \sum_{i=1}^6 \frac{1}{6} \mathbb{E} [ R \mid r_1 = i ] = 7,$$ again due to the arbitrariness of the initial roll realization.

Literally and figuratively on the flip side .... Let's assume without loss of generality that the first flip is $H$. The second flip is either again a $H$ or it will be a $T$, each with $1/2$ probability. So by the law of total expectation we have $$\mathbb{E} [F \mid f_1 = H] = \frac{1}{2} \mathbb{E} [ F \mid f_1 = f_2 = H ] + \frac{1}{2} \mathbb{E} [ F \mid f_1 = H, f_2 = T].$$ As before, we see that $\mathbb{E} [F \mid f_1 = H] = \mathbb{E} [F \mid f_1 = T],$ so we have $\mathbb{E} [ F \mid f_1 = H, f_2 = T ] = 1 + \mathbb{E} [ F \mid f_1 = H ].$ Going one step further if $f_1 = f_2 = H,$ then either $f_3 = H$ and we are done (with $F = 3$), or $f_3 = T,$ where we have $$\mathbb{E} [ F \mid f_1 = f_2 = H, f_3 = T ] = 2 + \mathbb{E}[F \mid f_1 = H].$$ So we have $$\mathbb{E} [F \mid f_1 = H] = \frac{1}{2} \left( \frac{1}{2} 3 + \frac{1}{2} (2 + \mathbb{E} [ F \mid f_1 = H ]) \right) + \frac{1}{2} ( 1 + \mathbb{E} [F \mid f_1 = H ] ),$$ or equivalently, $$\mathbb{E}[ F \mid f_1 = H ] = 7.$$ Once again, since the outcome of the choice of first flip was arbitrary, the expected number of flips is $$\mathbb{E}[F] = \frac{1}{2} \mathbb{E}[ F \mid f_1 = H ] + \frac{1}{2} \mathbb{E} [F \mid f_1 = T] = 7,$$ so the expectation is the same number of rolls and flips are the same.

So it is all well and good that the expected number of flips is the same, but will one side or the other be advantaged by the new method for determining the initial possession? Yes, the flipper will end up with a better odds of winning. Here I will give some hand-wavy justifications, but spinning up some simulations will additionally bear this out. The roller will always consistently have a $5/6$ probability of not winning on each roll. However, the flipper has a more volatile distribution not winning: if she just switched from $H$ to $T$ or vice versa, then the probability of not winning on the next roll is $100%,$ but if there are two in a row it drops to an even $50%$ of winning/not-winning. So as long as the flipper doesn't constantly go into streaks of alternating between H and T one after another, the flipper will have a lower probability of not-losing, or conversely probability of winning in the next round.

The emperor's new integer solutions

Find all pairs of integers $a$ and $b$ that are solutions to the following equation: $$a\cdot(a+1)\cdot(a+2) = b^2+4.$$

That’s it. That’s the riddle.

First, since $a$, $a+1$ and $a+2$ are three consecutive integers, one of them must be divisible by $3,$ so therefore their product $a \cdot (a+1) \cdot (a+2)$ is divisible by three. So regardless of the value of $a \in \mathbb{Z}$, the lefthand side of the equation is divisible by $3$.

Secondly, we can show that the righthand side of the equation cannot be divisible by three. If $3 \mid b,$ say with $b = 3\ell$, then clearly $$b^2+4 = 9 \ell^2 + 4 = 3(3 \ell^2 + 1) + 1 \equiv 1 \!\!\!\!\mod 3,$$ so if $3 \mid b$ then $3\not\mid b^2 + 4.$ On the other hand $3 \not\mid b,$ then Fermat's little theorem states that $$b^2 \equiv 1 \!\!\!\!\mod 3,$$ so for instance, if $3 \not\mid b$ then there is some $m \in \mathbb{Z}$ with $$b^2 = 3m + 1, so b^2 + 4 = 3m + 5 = 3(m+1) + 2 \equiv 2 \!\!\!\!\mod 3.$$ Thus, regardless of the value of $b \in \mathbb{Z}$, the righthand side of the equation is not divisble by $3.$

Therefore, since for any $a \in \mathbb{Z}$ the lefthand side is divisible by $3$, but for any $b \in \mathbb{Z}$ the righthand side cannot be divisible by $3,$ then there are no integer solutions to $$a\cdot(a+1)\cdot(a+2) = b^2 + 4.$$

While Fermat shuts the party down for $\mathbb{Z}^2,$ if we invite Gauss in, there are solutions over the Gaussian integers, e.g., $(-2, \pm 2i),$ $(-1, \pm 2i),$ and $(0, \pm 2i).$ But this might be a bridge too far for this particular riddle.

How many bottles of beer is it again?

You and your friends are singing the traditional song, “99 Bottles of Beer.” With each verse, you count down the number of bottles. The first verse contains the lyrics “99 bottles of beer,” the second verse contains the lyrics “98 bottles of beer,” and so on. The last verse contains the lyrics “1 bottle of beer.”

There’s just one problem. When completing any given verse, your group of friends has a tendency to forget which verse they’re on. When this happens, you finish the verse you are currently singing and then go back to the beginning of the song (with 99 bottles) on the next verse.

For each verse, suppose you have a 1 percent chance of forgetting which verse you are currently singing. On average, how many total verses will you sing in the song?

Extra credit: Instead of “99 Bottles of Beer,” suppose you and your friends are singing “$N$ Bottles of Beer,” where $N$ is some very, very large number. And suppose your collective probability of forgetting where you are in the song is $1/N$ for each verse. If it takes you an average of $K$ verses to finish the song, what value does the ratio of $K/N$ approach?

Let's define some variables. Let's say that $B_n$ is the number of bottles of beer on the wall in the $n$th verse and let's say that you start with $B_1 = N$ bottles of beer. Then the transition from $B_n$ to $B_{n+1}$ is given by $$B_{n+1} = \begin{cases} B_n - 1, &\text{with probability $1-p$}\\ N, &\text{with probability $p$}\end{cases}$$ which holds even if $B_n = 1.$ That is, the last verse is "1 bottle of beer on the wall, 1 bottle of beer, take 1 down pass it around, no bottles of beer on the wall," but somehow perhaps having ingested a few too many of the bottles of beer, your crew could still end up singing "1 bottle of beer on the wall, 1 bottle of beer, take 1 down pass it around, $N$ bottles of beer on the wall" and you'd have to make your way all the way back down. So in this setup, we need to also state that the transition with $B_{n+1} = 0$ if $B_n = 0,$ $\forall n.$ Finally, let's define the expected number of verses as $V_n = \mathbb{E}\left[ \min \{ k : B_k = 0 \} \mid B_1 = n\right],$ for any $n = 1, \dots, N.$

Now since there are only two possibilities at the end of each verse, we have $$\begin{align}V_n &= \mathbb{E} \left[ \min \{k : B_k = 0\} \mid B_2 = n-1, B_1 = n \right] \mathbb{P} \{ B_2 = n-1 \mid B_1 = n \}\\ &\quad\quad + \mathbb{E} \left[ \min \{k : B_k=0\} \mid B_2 = N, B_1 = n \right] \mathbb{P} \left\{ B_2 = N \mid B_1 = n \right\} \\ &= (1 + V_{N-1}) (1-p) + (1 + V_N) p\\ &= (1-p) V_{n-1} + pV_N + 1,\end{align}$$ for all $n = 1, \dots, N,$ with $V_0 = 0.$

So in particular, we have $$V_N = (pV_N + 1) + (1-p) V_{N-1}.$$ We can use this as the base case to prove that $$V_N = (pV_N+1) \sum_{i=0}^{k-1} (1-p)^i + (1-p)^k V_{N-k}$$ for all $k = 1, \dots, N.$ In particular, assume that for some $k > 1,$ then substituting in the recurrence relationship for $V_{N-k}$ we get $$\begin{align*} V_N &= (pV_N+1) \sum_{i=0}^{k-1} (1-p)^i + (1-p)^k ( (1-p) V_{N-k-1} + pV_N + 1) \\ &= (pV_N+1) \sum_{i=0}^k (1-p)^i + (1-p)^{k+1} V_{N-k-1},\end{align*}$$ that is, the formula is also true for $k+1.$ So, by induction, the formula must hold for all $k = 1, \dots, N,$ including for instance $k=N,$ so that $$\begin{align*}V_N &= (pV_N+1) \sum_{i=0}^{N-1} (1-p)^i + (1-p)^N V_0 = (pV_N+1) \sum_{i=0}^{N-1} (1-p)^i \\ &= (pV_N+1) \frac{1 - (1-p)^N}{p}.\end{align*}$$

Solving for $V_N$ we get $$V_N = \frac{1 - (1-p)^N}{p(1-p)^N}.$$ So in particular if $N = 99$ and $p = 0.01,$ then we get an average of $$\frac{1-(0.99)^{99}}{0.01 * (0.99)^{99}} \approx 170.467$$ verses. However, if we set $p = 1/N,$ then we get $$K=V_N = N\frac{1-(1-1/N)^N}{(1-1/N)^N},$$ so the fraction $$K/N = \frac{1 - (1-1/N)^N}{(1-1/N)^N} = (1-1/N)^{-N} - 1 \to e-1$$ as $N\to \infty.$

Drone Deliveries

A restaurant at the center of Riddler City is testing an airborne drone delivery service against their existing fleet of scooters. The restaurant is at the center of a large Manhattan-like array of square city blocks, which the scooter must follow.

Both vehicles travel at the same speed, which means drones can make more deliveries per unit time. Assume that (1) Riddler City is circular in shape, as you may recall (2) deliveries are made to random locations throughout the city and (3) the city is much, much larger than its individual blocks.

In a given amount of time, what is the expected ratio between the number of deliveries a drone can make to the number of deliveries a scooter can make?

Given the setup, we can assume that the restaurant is at the origin of a unit circle and that the orders come in randomly at any point in the unit disk, that is, $Z = (x,y)$ with $x^2 + y^2 \leq 1.$ The distance traveled by the drone from the restaurant to the point $Z$ is $\|Z\|_2 = \sqrt{x^2 + y^2}$ while the distance traveled by the scooter is $\|Z\|_1 = |x|+|y|.$ Let's also assume that both the drone and the scooter only make one delivery at a time. Then the expected number of deliveries per unit time is proportional to the inverse of the distance traveled per delivery, the expected ratio of number of deliveries by drone versus scooter is roughly equal to the inverse of the ratios of expected distances traveled, that is, $$k= \frac{\mathbb{E} \|Z\|_1}{\mathbb{E} \|Z\|_2}.$$

In polar coordinates the scooter distance can be rewritten as $\|Z\|_1 = r(|\cos \theta | + |\sin \theta|),$ where the absolute values can be dropped in the first quadrant. So, due to symmetry, the numerator of $k$ is given by $$\mathbb{E} \|Z\|_1 = \frac{4}{\pi} \int_0^{\pi/2} \int_0^1 r (\cos \theta + \sin \theta) r dr\, d\theta = \frac{8}{3\pi}.$$

In polar coordinates, $\|Z\|_2 = r,$ so the denominator of $k$ is $$\mathbb{E}\|Z\|_2 = \frac{1}{\pi} \int_0^{2\pi} \int_0^1 r^2 dr\,d\theta = \frac{2}{3}.$$ So, the drone is expected to make $$k= \frac{\frac{8}{3\pi}}{\frac{2}{3}} = \frac{4}{\pi}$$ times as many deliveries per unit time as the scooter.

Extra credit: In addition to traveling parallel to the city blocks, suppose scooters can also move diagonally from one corner of a block to the opposite corner of the block. Now, what is the new expected ratio between the number of deliveries a drone can make and the number of deliveries a scooter can make?

If the scooters are also allowed to move diagonally across blocks, then the equivalent if we think about having to move from the origin to a point that is say $m$ blocks east and $n$ blocks north of the origin, the fastest delivery route would be to go diagonally northeast for $\min \{m,n\}$ blocks then either proceed the remaining $|m-n|$ blocks due east if $m \lt n$ or due north otherwise. In this case the distance traveled is $(\sqrt{2}-1) \min\{m,n\} + \max\{m,n\}$ blocks. In general, zooming back out to our unit circle representation, the distance traveled to any generic point $Z$ in the unit circle is $$\hat{d}(Z) = (\sqrt{2}-1)\min \{|x|,|y|\} + \max\{|x|,|y|\}.$$ The calculation for the expected ratio of number of deliveries per unit time can still proceed analogously, with $$\hat{k} = \frac{ \mathbb{E} \hat{d}(Z) }{ \mathbb{E} \|Z\|_2} = \frac{3}{2} \mathbb{E} \hat{d}(Z).$$

If we focus on the first quadrant where additionally we have $y\leq x$, then $\hat{d}(Z) = x + (\sqrt{2}-1) y$ or in polar coordinates this would be $$\hat{d}(Z) = r\left( \cos \theta + (\sqrt{2}-1) \sin \theta\right),$$ where $0\leq \theta \leq \frac{\pi}{4}.$ By symmetry, we have $$\mathbb{E} \hat{d} (Z) = \frac{8}{\pi} \int_0^{\pi/4} \int_0^1 r\left( \cos \theta + (\sqrt{2}-1) \sin\theta\right) rdr\,d\theta = \frac{16(\sqrt{2}-1)}{3\pi}.$$ So, if scooters can go diagonally across blocks, then the drone is expected to make only $$\hat{k} = \frac{8(\sqrt{2}-1)}{\pi}$$ times as many deliveries per unit time than as the scooter.