Monday, July 6, 2026

Retsy Boss VIII's Star Fitting Homage

After 250 years, the nation has commissioned Retsy Boss VIII to design a new flag with one star for each of the nation’s current $58$ states. As an homage to the original flag design, Retsy wants to select $58$ stars from the square grid that are all at most some distance $R$ from a point on the plane. What is the minimum distance $R$ that Retsy can use?

Thankfully for Retsy Boss VIII, her namesake left her the Python code to run the optimization to find the number of stars given $h,$ $k$ and $R.$ Also, fortunately for Retsy Boss VIII she knew to look at OEIS to look up the integer sequence A000328, which captures the case of $h=k=0$ and $R \in \mathbb{N},$ to give her a decent idea of where to start. In particular, we see that $N(0,0,4) = 49$ and $N(0,0,5)=81,$ so let's start looking for $R \in [4,5].$ In particular, she wants to find $$R^* = \inf \left\{ R \in [4,5] \mid N^*(R) = \sup_{(h,k) \in [0,1]^2} N(h,k,R) \geq 58 \right\}.$$

Retsy didn't want to exhaustively search the entire phase space, so first she went about implementing a secant method update to arrive at some point $R$ for which $N^*(R) = 58.$ In particular, let's let $R_0 = 4,$ $R_1 = 5$ and $$R_{n+1} = \frac{R_{n-1} N^*(R_n) - R_n N^*(R_{n-1}) + 58 (R_n - R_{n-1})}{N^*(R_n) - N^*(R_{n-1})}.$$ Note that relatively quickly we arrive at some value with $N^*(R) = 58,$ that is,

$n$ $R_n$ $N^*(R_n)$
$0$ $4$ $49$
$1$ $5$ $81$
$2$ $4.20689655\dots$ $59$
$3$ $4.17084639\dots$ $58$

That is all well and good, but Retsy VIII wants the minimal such value of $R$ such that $N^*(R) = 58.$ Now she turns to a binary search of the interval $[a_0,b_0] = [4, 4.17084639],$ to within a tolerance of $\varepsilon = 10^{-6}.$ For each $n,$ she defines $c_n = \frac{a_n+b_n}{2}.$ If $N^*(c_n) \lt 58,$ then she defines $a_{n+1} = c_n$ and $b_{n+1} = b_n;$ however if $N^*(c_n) = 58,$ then she defines $a_{n+1} = a_n$ and $b_{n+1} = c_n.$ We can stop as soon as

$n$ $a_n$ $b_n$ $c_n$ $N^*(c_n)$
$0$ $4$ $4.17084639$ $4.08542320$ $56$
$1$ $4.08542320$ $4.17084639$ $4.12813480$ $57$
$2$ $4.12813480$ $4.17084639$ $4.14949060$ $57$
$3$ $4.14949060$ $4.17084639$ $4.16016850$ $58$
$4$ $4.14949060$ $4.16016850$ $4.15482955$ $57$
$5$ $4.15482955$ $4.16016850$ $4.15749902$ $58$
$6$ $4.15482955$ $4.15749902$ $4.15616428$ $58$
$7$ $4.15482955$ $4.15616428$ $4.15549691$ $58$
$8$ $4.15482955$ $4.15549691$ $4.15516323$ $57$
$9$ $4.15516323$ $4.15549691$ $4.15533007$ $58$
$10$ $4.15516323$ $4.15533007$ $4.15524665$ $58$
$11$ $4.15516323$ $4.15524665$ $4.15520494$ $58$
$12$ $4.15516323$ $4.15520494$ $4.15518409$ $57$
$13$ $4.15518409$ $4.15520494$ $4.15519451$ $58$
$14$ $4.15518409$ $4.15519451$ $4.15518930$ $57$
$15$ $4.15518930$ $4.15519451$ $4.15519191$ $57$
$16$ $4.15519191$ $4.15519451$ $4.15519321$ $58$
$17$ $4.15519191$ $4.15519321$ $4.15519256$ $58$

So we see that the optimal value of $R^*$ is about $4.15519256$ to within a tolerance of $\varepsilon = 10^{-6}.$ At this point, we can use map a contour plot, shown below, similar to what we did for the Classic problem. It is hard to discern, but the only place that the maximum is attained (up to the various symmetries of the $N$ function) when $R = 4.15519256$ is in a small neighborhood of the point $(h,k) = (1/2, 1/8)$ (seem familiar ... wink, wink?). If we were to graph the circle of radius $R = 4.15519256$ centered at $(1/2, 1/8),$ we see that it ever so slightly includes the lattice points $(-1,4),$ $(2,4),$ $(0,-4)$ and $(1,-4).$ In particular, since we see that the distance from $(1/2, 1/8)$ to any of these four lattices points is exactly the same, we can reduce the value of $R$ to precise that distance and maintain a value of $N^*(R) = 58,$ and hence the minimum distance that Retsy Boss VIII can use to honor her forebear's design is exactly $$R^* = \sqrt{0.5^2 + 4.125^2} = \sqrt{1.5^2 + 3.875^2} = \frac{\sqrt{1105}}{8} \approx 4.155192534648665\dots.$$

Posted by at No comments:

Move Over Ed McMahon, It's Retsy Boss's Star Search

When designing her new nation’s flag, Retsy Boss wanted to compactly arrange some stars. These stars were positioned along a square grid, but she only wanted to include stars whose centers were at most two units away from some point on the plane.

For example, if she had centered the circle on a star itself, then she could have placed a total of 13 stars on the flag, as shown below:

What is the greatest number of stars Retsy could have placed on the flag?

Let's define the function $N(h,k,R)$ to be the number of integer lattice points within distance $R$ of the point $(h,k) \in \mathbb{R}^2,$ in particular, we have $$N(h,k,R) = \# \left\{ (m,n) \in \mathbb{Z}^2 \mid (m-h)^2 + (n-k)^2 \leq R^2 \right\}.$$ If we have a fixed value of $k,$ let's say, then we see will have $$\eta_n(h,k,R) = \left\lfloor \sqrt{R^2 - (n-k)^2} + h \right\rfloor + \left\lfloor \sqrt{R^2 - (n-k)^2} - h \right\rfloor + 1,$$ where for clarity $\lfloor x \rfloor = \max \{ n \in \mathbb{Z} \mid n \leq x \}$ and in particular $\lfloor x \rfloor = -1$ for $x \in [-1,0).$ So in particular, we have $$N(h,k,R) = \sum_{n=-\lfloor R - k \rfloor}^{\lfloor R + k \rfloor} \eta_n (h,k,R).$$ We see for instance, that when $h=k=0$ and $R=2,$ that we indeed recover $\eta_{-2}(0,0,2) = \eta_2(0,0,2) = 1, \eta_{-1}(0,0,2) = \eta_1(0,0,2) = 3,$ and $\eta_0 (0,0,2)= 5,$ so we have $$N(0,0,2) = \sum_{n=-2}^2 \eta_n(0,0,2) = 1 + 3 + 5 + 3 + 1 = 13.$$

Now, since we also see that everything is periodic and symmetric, in order to solve Retsy's problem we only need to find $$N^* = \max \left\{ N(h,k,2) \mid 0 \leq k \leq h \leq \frac{1}{2} \right\},$$ since everything else in the unit square will can be recovered from this region and everything else in the plane is periodic so $N(h,k,2) = N([h], [k],2),$ for all $(h,k) \in \mathbb{R}^2,$ where $[x] = x - \lfloor x \rfloor$ is the fractional part function.

We can code this up in the following Python code to explore the phase space and empirically determine $N^*$:

Using this Python code, we can plot the following contour plot, which shows that anywhere in the dark blue region produces the the largest possible number of stars that Retsy could place on the flag is $N^*=14.$ In particular, we can take the point $(h,k) = (0.5, 0.125)$ for foreshadowing purposes and explicitly compute that \begin{align*} \eta_{-1}(0.5,0.125,2) &= \lfloor \sqrt{ 4 - (-1-0.125)^2 } + 0.5 \rfloor + \lfloor \sqrt{ 4 - (-1-0.125)^2 } - 0.5 \rfloor + 1 \\ &\quad = \lfloor 1.654\dots + 0.5 \rfloor + \lfloor 1.654\dots - 0.5 \rfloor + 1 = 4\\ \eta_{0}(0.5,0.125,2) &= \lfloor \sqrt{ 4 - (-0.125)^2 } + 0.5 \rfloor + \lfloor \sqrt{ 4 - (-0.125)^2 } - 0.5 \rfloor + 1\\ &\quad =\lfloor 1.996\dots + 0.5 \rfloor + \lfloor 1.996\dots - 0.5 \rfloor + 1 = 4\\ \eta_{1}(0.5,0.125,2) &= \lfloor \sqrt{ 4 - (1-0.125)^2 } + 0.5 \rfloor + \lfloor \sqrt{ 4 - (1-0.125)^2 } - 0.5 \rfloor + 1\\ &\quad =\lfloor 1.798\dots + 0.5 \rfloor + \lfloor 1.798\dots - 0.5 \rfloor + 1 = 4\\ \eta_{2}(0.5,0.125,2) &= \lfloor \sqrt{ 4 - (2-0.125)^2 } + 0.5 \rfloor + \lfloor \sqrt{ 4 - (2-0.125)^2 } - 0.5 \rfloor + 1\\ &\quad =\lfloor 0.696\dots + 0.5 \rfloor + \lfloor 0.696\dots - 0.5 \rfloor + 1 = 2\end{align*} so that $$N(0.5,0.125,2)=N^*=4+4+4+2=14.$$

Posted by at No comments:

Sunday, June 21, 2026

A less than half-full tank

Frustrated with my old calculator, I toss it in the trash and buy a new one. But now I’m concerned this second calculator is also “tanked.” As before, every value of $A$ between $0$ and $1$ is equally likely, at first.

I ask my friend to generate one random number using this second calculator. My friend does so, and smirks. “I won’t tell you what the number is,” my friend says, “but it’s somewhere between $0$ and $0.5.$” On average, what can I expect the value of $A$ (for this second calculator) to be?

Similar to the classic problem, we will define terms with $A \sim U(0,1)$ at first and $X|A=a \sim U(0,a).$ In this case, we want to get the distribution of $A$ conditional on $0 \leq X \leq \frac{1}{2},$ that is, $$f_{A\mid 0 \leq X \leq 1/2} (a) = \lim_{da \downarrow 0} \frac{\frac{1}{da} \mathbb{P} \left\{ a -\frac{da}{2} \leq A \leq a + \frac{da}{2}, 0 \leq X \leq \frac{1}{2} \right\}}{ \mathbb{P} \{ 0 \leq X \leq \frac{1}{2} \} }.$$

Let's take the denominator first, like last time to see that \begin{align*}\mathbb{P} \{ 0 \leq X \leq \frac{1}{2} \} &= \int_0^1 \int_0^{1/2} \frac{1}{t} \chi_{[0,t]}(x) \,dx \,dt \\ &= \int_0^{1/2} \int_0^1 \frac{1}{t} \chi_{[0,t]}(x) \,dt \,dx \\ &= \int_0^{1/2} \left(\int_0^x 0 \,dt + \int_x^1 \frac{dt}{t} \right) \,dx \\ &= \int_0^{1/2} -\ln x \,dx \\ &= \frac{1}{2} - \frac{1}{2} \ln \frac{1}{2} = \frac{1}{2} \left( 1 + \ln 2 \right).\end{align*}

Let's assume that $a \gt \frac{1}{2},$ in which case, for small values of $da$ we have $\frac{1}{2} \leq a - \frac{da}{2},$ so we have $\chi_{[0,t]}(x) = 1$ for all $0 \leq x \leq 1/2$ and $t \in (a-da/2, a+da/2).$ Therefore, if $a \gt \frac{1}{2},$ then we have the numerator equal to \begin{align*}\frac{1}{da} \mathbb{P} \{ a - da/2 \leq A \leq a + da/2, 0 \leq X \leq 1/2 \} &= \frac{1}{da}\int_{a-da/2}^{a+da/2} \int_0^{1/2} \frac{1}{t} \chi_{[0,t]}(x) \,dx \, dt \\ &= \frac{1}{da} \int_{a-da/2}^{a+da/2} \frac{dt}{2t} = \frac{1}{2da} \left( \frac{a + \frac{da}{2}}{a - \frac{da}{2}} \right) \\&= \frac{1}{2} \left. \frac{d}{dt} \ln t \right|_{t=a} + O(da) = \frac{1}{2a} + O(da).\end{align*} On the other hand, if $a \lt \frac{1}{2},$ then if $da$ is small enough, then for every $t \in (a - da/2, a+da/2),$ we have $t \lt 1/2,$ so we have the denominator as \begin{align*}\frac{1}{da} \mathbb{P} \{ a - da/2 \leq A \leq a + da/2, 0 \leq X \leq 1/2 \} &= \frac{1}{da} \int_{a-da/2}^{a+da/2} \int_0^{1/2} \frac{1}{t} \chi_{[0,t]}(x) \,dx \,dt \\ &= \frac{1}{da} \int_{a-da/2}^{a+da/2} \left( \int_0^t \frac{1}{t}\, dx + \int_t^{1/2} 0 \,dx \right) \,dt \\ &= \frac{1}{da} \int_{a-da/2}^{a+da/2} 1 \,dt = 1\end{align*} Therefore, we see that as $da \downarrow 0,$ the numerator becomes the piecewise function $n(a) = \min \{ 1, \frac{1}{2a} \},$ so putting everything together, we see that $$f_{A\mid 0 \leq X \leq \frac{1}{2}} (a) = \frac{ n(a) }{ \frac{1}{2} (1 + \ln 2) } = \min \left\{ \frac{2}{1 + \ln 2}, \frac{1}{a(1 + \ln 2)} \right\}.$$

Therefore, if all we have is the knowledge that the draw from the tanked calculator is in the lower half of the interval, then the expected value of the tank parameter is \begin{align*}\mathbb{E} \left[ A \mid 0 \leq X \leq \frac{1}{2} \right] &= \int_0^{1/2} a \cdot \frac{2}{1 + \ln 2} \,da + \int_{1/2}^1 a \cdot \frac{1}{a(1 + \ln 2)} \,da \\ &= \left.\frac{2}{ 1 + \ln 2} \frac{a^2}{2} \right|_{a=0}^{a=1/2} + \frac{1}{1 + \ln 2} \cdot \frac{1}{2} \\ &= \frac{3}{4(1 + \ln 2)} \approx 0.442962081862\dots\end{align*}

Posted by at No comments:

A half-full tank

I think the random number generator on my calculator might be malfunctioning. Oh no!

Under normal conditions, it should generate random numbers between $0$ and $1.$ But my suspicion is that the calculator is “tanked,” meaning it only generates random numbers between $0$ and some value $0 \lt A \lt 1.$ Beyond that, I have no knowledge regarding the value of $A.$ At the moment, it’s equally likely to be any value from $0$ to $1$.

As an experiment, I ask the calculator to generate one random number. It produces a value of exactly $0.5.$ (While this is, admittedly, infinitely unlikely, let’s roll with it!) Based on this result, what can I expect the value of $A$ to be, on average?

Let's first define some terms. Let's assume that the tank paramater $A \sim U(0,1),$ and since the calculator is tanked that random draws are all independently and identically distributed as $X \sim U(0,A),$ that is, $$f_{X|A=a}(x) = \lim_{dx \downarrow 0} \frac{1}{dx} \mathbb{P} \{ x - \frac{dx}{2} \leq X \leq x + \frac{dx}{2} \mid A = a\} = \frac{1}{a} \chi_{[0,a]}(x).$$ Using Bayesian theorem, we see that \begin{align*}f_{A|X=x} (a) &= \lim_{da \downarrow 0} \frac{1}{da} \mathbb{P} \{ a - \frac{da}{2} \leq A \leq a + \frac{da}{2} \mid X = x \} \\ &= \lim_{da \downarrow 0} \frac{ \mathbb{P} \{ a - \frac{da}{2} \leq A \leq a + \frac{da}{2}, X = x \} }{ da \mathbb{P} \{ X = x \} } \\ &= \lim_{da \downarrow 0} \frac{ \frac{1}{da} \int_{a - da/2}^{a+da/2} \frac{1}{t} \chi_{[0,t]}(x) \,dt }{ \int_0^1 \frac{1}{t} \chi_{[0,t]}(x) \,dt }.\end{align*} In particular, the denominator can be calculated as $$\int_0^1 \frac{1}{t} \chi_{[0,t]}(x) \,dt = \int_0^x \frac{1}{t} \chi_{[0,t]}(x) \,dt + \int_x^1 \frac{1}{t} \chi_{[0,t]}(x) \,dt = \int_0^x 0 \,dt + \int_x^1 \frac{dt}{t} = -\ln x.$$ The numerator meanwhile is equivalent to $\frac{1}{a} \chi_{[0,a)} (x),$ since if $x \lt a,$ then there is some $\alpha \lt 2(a-x)$ for which for any $0 \lt da \lt \alpha,$ $\chi_{[0,t]}(x) = 1$ for all $t \in (a-\frac{da}{2}, a + \frac{da}{2}),$ so that $$\frac{1}{da} \int_{a - da/2}^{a+da/2} \frac{1}{t} \chi_{[0,t]}(x) \,dt = \frac{1}{da} \int_{a-da/2}^{a+da/2} \frac{dt}{t} = \frac{ \ln \left( \frac{a + \frac{da}{2}}{a - \frac{da}{2}} \right) }{da} = \left.\frac{d}{dt} \ln t \right|_{t=a} + O(da) = \frac{1}{a} + O(da).$$ Similarly, if $x \gt a,$ then there is some $\alpha^\prime \lt 2(x-a)$ for which for any $0 \lt da \lt \alpha^\prime,$ then $\chi_{[0,t]}(x) = 0$ for all $t \in (a - \frac{da}{2}, a + \frac{da}{2} ),$ so that $$\frac{1}{da} \int_{a-da/2}^{a+da/2} \frac{1}{t} \chi_{[0,t]}(x) \,dt = 0.$$ Putting this all together, we see that $$f_{A\mid X=x}(a) = \begin{cases} -\frac{1}{a \ln x}, &\text{if $x \lt a \leq 1$;}\\ 0, &\text{if $0 \leq a \lt x.$}\end{cases}$$

Therefore, in particular, since we observed that $X = \frac{1}{2},$ we have the expected value of the tank parameter $A$ as \begin{align*}E[A \mid X = \frac{1}{2}] &= \int_0^1 a f_{A \mid X=\frac{1}{2}} (a) \,da \\ &= \int_0^{1/2} a \cdot 0 \,da + \int_{1/2}^1 a \cdot \left(- \frac{1}{a \ln \frac{1}{2}}\right) \,da \\ &= \int_{1/2}^1 \frac{da}{ln 2} \\& = \frac{1}{2\ln 2} \approx 0.72134752044\dots\end{align*}

Posted by at No comments:

Sunday, June 14, 2026

The average wave

Another wave is approaching the island, but no one knows which direction it’s coming from—for the moment, all directions are equally likely. On average, what is the length of the stretch of land directly under the wave halfway between when the wave first and last makes contact with the island?

Using our function $$\ell (\theta) = \min \left\{ \sqrt{(3 - \cos \theta) (1 + \cos \theta)}, \frac{ \tan \theta (1- \cos \theta) + \sqrt{(3-\cos \theta) (1 + \cos \theta)}}{2} \right\}$$ from the Classic answer along with the symmetry arguments that we made there to come to the conclusion that the average length of the stretch of land is \begin{align*}\bar{\ell} &= \int_0^{\pi/2} \ell(\theta) \frac{ 2d\theta }{ \pi } = \frac{2}{\pi} \int_0^{\cos^{-1} 1/3} \frac{ \tan \theta ( 1- \cos \theta) + \sqrt{(3 - \cos \theta) (1 + \cos \theta) }}{2} \,d\theta \\ &\quad\quad\quad\quad\quad\quad\quad\quad\quad + \frac{2}{\pi} \int_{\cos^{-1} 1/3}^{\pi/2} \sqrt{ (3 - \cos \theta) (1 + \cos \theta) } \,d\theta \end{align*}

Well that is certainly a mouthful, but we can break it into some pieces and come up with an analytical solution. First we see that if we rewrite the portion under the radical as $$\frac{\sqrt{(3 - \cos \theta)( 1 + \cos \theta) }}{2} = \sqrt{ 1- \left(\frac{1-\cos \theta}{2} \right)^2}$$ that we can do some trigonometrical simplifications and substitutions. So in particular we see that since $\sin \frac{\theta}{2} = \sqrt{ \frac{1-cos \theta}{2} }$ when $\theta \in (0, \frac{\pi}{2}),$ then we get \begin{align*}\int \sqrt{ 1- \left( \frac{ 1 - \cos \theta }{2} \right)^2 } \,d\theta &= \int \sqrt{ 1 - \sin^4 \frac{\theta}{2} } \,d\theta \\&= \int \sqrt{ \left( 1 - \sin^2 \frac{\theta}{2} \right) \left( 1 + \sin^2 \frac{\theta}{2} \right) } \,d\theta \\ &= \int \cos \frac{\theta}{2} \sqrt{ 1 + \sin^2 \frac{\theta}{2} } \,d\theta \\ &= 2\int \sqrt{1 + u^2} \,du,\end{align*} where the last equation involves the substitution of $u = \sin \frac{\theta}{2}.$ Using integration by parts, we get $$\int \sqrt{1+u^2} \,du = u \sqrt{1 + u^2} - \int \frac{u^2 \,du}{\sqrt{1+u^2}} = u \sqrt{1+u^2} + \int \frac{du}{\sqrt{1+u^2}} - \int \sqrt{ 1 + u^2 } \,du,$$ so that we get $$\int \sqrt{1+u^2} \,du = \frac{1}{2} \left( u \sqrt{1 + u^2} + \int \frac{du}{\sqrt{1+u^2}} \right) = \frac{1}{2} \left( u \sqrt{1+ u^2} + \sinh^{-1} u\right) + C.$$ Therefore we see that \begin{align*}\int \frac{ \sqrt{ (3-\cos \theta) (1 + \cos \theta) } }{2} \,d\theta &= \int \sqrt{ 1 - \left( \frac{1 - \cos \theta}{2} \right)^2 } \,d\theta \\ &= \sin \frac{\theta}{2} \sqrt{ 1 + \sin^2 \frac{\theta}{2} } + \sinh^{-1} \left(\sin \frac{\theta}{2}\right) + C.\end{align*} Similarly, but with a lot less fuss, we can get $$\int \frac{\tan \theta (1 - \cos \theta)}{2} \,d\theta = -\frac{1}{2} \ln | \cos \theta | + \frac{\cos \theta}{2} + C.$$

Therefore the the first integral \begin{align*}I_1 &= \frac{2}{\pi} \int_0^{\cos^{-1} 1/3} \frac{ \tan \theta (1 - \cos \theta) }{2} + \sqrt{ 1 - \left( \frac{1-\cos \theta}{2} \right)^2 } \,d\theta \\ &= \frac{2}{\pi}\left[ -\frac{1}{2} \ln | \cos \theta | - \frac{\cos \theta}{2} + \sin \frac{\theta}{2} \sqrt{ 1 + \sin^2 \frac{\theta}{2} } + \sinh^{-1} \left( \sin \frac{\theta}{2} \right) \right]^{\theta = \cos^{-1} 1/3}_{\theta = 0} \\ &= \frac{2}{\pi}\left( -\frac{1}{2} \ln \frac{1}{3} + \frac{1}{6} + \sqrt{ \frac{ 1 - \frac{1}{3}}{2}} \sqrt{ 1 + \left(\sqrt{ \frac{ 1 - \frac{1}{3} }{2} }\right)^2 } + \sinh^{-1} \sqrt{ \frac{1 - \frac{1}{3}}{2} } \right) \\ &\quad\quad\quad\quad\quad - \frac{2}{\pi}(0 + \frac{1}{2} + 0 + 0) \\ &= \frac{2}{\pi} \left(\frac{1}{2} \ln 3 + \frac{1}{3} + \sinh^{-1} \sqrt{\frac{1}{3}} \right) \\ &= \frac{2}{\pi}\ln 3 + \frac{2}{3\pi}, \end{align*} since $\sinh^{-1} t = \ln ( t + \sqrt{ 1 + t^2} ),$ so $$\sinh^{-1} \sqrt{\frac{1}{3}} = \ln \left( \sqrt{\frac{1}{3}} + \sqrt{1 + \frac{1}{3}} \right) = \ln \left( \sqrt{\frac{1}{3}} + \sqrt{ \frac{4}{3}} \right) = \ln \left( 3 \sqrt{\frac{1}{3}} \right) = \ln \sqrt{3} = \frac{1}{2} \ln 3.$$ The second integral is \begin{align*}I_2 &= \frac{4}{\pi} \int_{\cos^{-1} 1/3}^{\pi/2} \sqrt{ 1 - \left( \frac{1 - \cos \theta}{2} \right)^2 } \,d\theta \\ &= \frac{4}{\pi} \left[ \sin \frac{\theta}{2} \sqrt{ 1 + \sin^2 \frac{\theta}{2} } + \sinh^{-1} ( \sin \frac{\theta}{2} ) \right]_{\theta=\cos^{-1} 1/3}^{\theta=\pi/2} \\ &= \frac{4}{\pi} \left( \frac{1}{\sqrt{2}} \cdot \sqrt{1+\frac{1}{2}} + \sinh^{-1}\frac{1}{ \sqrt{2}} \right) \\ &\quad\quad\quad - \frac{4}{\pi} \left( \sqrt{ \frac{ 1 - \frac{1}{3}}{2}} \sqrt{ 1 + \left(\sqrt{ \frac{ 1 - \frac{1}{3} }{2} }\right)^2 } + \sinh^{-1} \sqrt{ \frac{1 - \frac{1}{3}}{2} } \right) \\ &= \frac{4}{\pi} \left( \frac{\sqrt{3}}{2} + \sinh^{-1} \frac{1}{\sqrt{2}} - \frac{2}{3} - \frac{1}{2} \ln 3 \right)\end{align*} Putting this all together and taking advantage of some beneficial cancelling, we get that the average length of the stretch of land covered by the wave at 10:05 a.m. if all directions for it to approach Semicircle Island are equally likely is $$\bar{\ell} = I_1 + I_2 = \frac{4}{\pi} \left( \frac{ \sqrt{3}}{2} + \sinh^{-1} \frac{1}{\sqrt{2}} \right) - \frac{2}{\pi} \approx 1.30443945503\dots$$ miles.

Posted by at No comments:

The longest wave

Semicircle Island is shaped like a perfect semicircle (or semidisk, technically), with a radius of $1$ mile. It doesn’t have any permanent residents, but it’s a very popular destination for surfers.

Rumor has it that a big wave is headed toward the island. This thin, straight wall of water never changes speed or direction. It will first make contact with the island at 10 a.m. and it will last be in contact with the island at 10:10 a.m. What is the longest possible stretch of land that is directly under the wave at 10:05 a.m.?

With my deepest apologies for my bad Paint skills, let's use a modified version of picture from the Extra Credit prompt and note that I inserted a ray that is perpendicular to the direction of travel of the wave that happens to make an angle of $\theta$ with the positive $x$-axis.

Let's assume that the center of the semi-disk is the point $(0,0),$ the place where the wave first hits the island is at the point $(\cos \theta, \sin \theta)$ and the formula for the ray connecting the origin and this point is $y = x \tan \theta$ as long as $\theta \ne \frac{\pi}{2}.$ Since the wave is perpendicular to this ray, the wave's slope must be the negative reciprocal of that of the ray, so we have the fomula for the wave at 10:00 a.m. is $y= -x \cot \theta + \csc \theta,$ which works as long as $x \not\in \{ 0, \pi\}.$ We similarly see that since the wave at each future point will be parallel to this line that the equation that models the position of the wave at 10:10 a.m. is either $y= -(x+1) \cot \theta,$ if $\theta \in (0, \frac{\pi}{2}),$ or $y = -(x-1) \cot \theta$ if $\theta \in ( \frac{\pi}{2}, \pi ).$ For simplicity, and by symmetry let's just assume going forward that $\theta \in (0, \frac{\pi}{2}).$ In this case, we see that the formula that models the position of the wave at 10:05 a.m., based on the uniform motion of the wave, is then $$y = -x \cot \theta + \frac{\left(\csc \theta + (-\cot \theta)\right)}{2} = -x \cot \theta + \frac{1 - \cos \theta}{2 \sin \theta}.$$

Let's pause here and think about what the length of a chord of a full circle would be. For simplicity let's assume that the chord is parallel to the $x$-axis, at say $y = h.$ In this case, we see that the endpoints of the chord are at $(\pm \sqrt{1-h^2}, h),$ so the length of the curve is $2\sqrt{1-h^2}.$ We further notice that if we rotate the entire $xy$-plane clockwise by angle $\frac{\pi}{2} - \theta,$ then the positive $y$-axis would be mapped to the ray $y= x \tan \theta,$ as we had before. In the case of the circle case, the chord length is obviously preserved in this orthogonal rotation, but now we want to only include the portion of the rotated chord that is now above the $x$-axis. We see that the portion of the chord that was in quadrant II before the rotation is still definitely in the upper half-plane post-rotation, so we should get at least $\sqrt{1-h^2}.$ The only thing to calculate is how much of the half-chord that was in the quadrant I. Firstly, it is perhaps the case depending on the height $h$ and rotational angle $\theta$ that the entirety of the half-chord is in the upper half-plane post-rotation, so the maximum that we could ever get is $\sqrt{1-h^2}.$ On the other hand, if we look at the right triangle formed by the ray $y = x\tan \theta,$ the rotated half-chord and the $x$-axis. Using trigonometry we see that the side with length $h$ is adjacent to the angle whose measure is \theta, with the half-chord opposite that angle, so we have the length of the half-chord in the upper half-plane as $h \tan \theta.$ So putting this altogether, we see that in a case where the we have the line $y=h$ and a rotation of the xy-plane clockwise by $\frac{\pi}{2}-\theta$ then the length of the chord that remains in the upper half-plane is $$\ell(h, \theta) = \min \{ 2 \sqrt{1-h^2}, \sqrt{1-h^2} + h \tan \theta \}.$$

That's cool an all, but let's return to our particular wave. We see that the we certainly have $\theta,$ by design, but all we need is to determine $h$ in this case. In the case of our wave that is modeled by the line $$y = -x\cot \theta + \frac{1- \cos \theta}{\sin \theta},$$ we can use that same right triangle that we used in the generic case above and the fact that the line crosses the $x$-axis as the point $x = \frac{\sec \theta - 1}{2}$ to determine that $$h = \frac{\sec \theta - 1}{2} \cos \theta = \frac{1 - \cos \theta}{2}.$$ Therefore, we see that the length of the stretch of land covered at 10:05 a.m. if it first touches the island at a point $(\cos \theta, \sin \theta)$ is \begin{align*}\ell(\theta) = \ell\left(\frac{1- \cos\theta}{2}, \theta\right) &= \min \left\{ 2 \sqrt{ 1 - \left(\frac{1 - \cos \theta}{2} \right)^2 }, \frac{1 - \cos \theta}{2}\tan \theta + \sqrt{ 1 - \left( \frac{1 - \cos \theta}{2} \right)^2 } \right\} \\ &= \min \left\{ \sqrt{ (3 - \cos \theta) (1 + \cos \theta) }, \frac{\tan \theta ( 1 - \cos \theta) + \sqrt{(3-\cos \theta)(1 + \cos \theta)} }{2} \right\},\end{align*} for $\theta \in (0, \frac{\pi}{2}).$ Analyzing the parts we see that $\tan \theta (1 - \cos \theta)$ is always increasing on this interval, while the term within the square root is always decreasing, therefore we can reason that that maximal length occurs exactly at the cutover point when $$\tan \theta (1 - \cos \theta) = \sqrt{ (3 - \cos \theta) (1 + \cos \theta) }.$$ While I am sure there are many who may want to try to solve analytically, from a geometric intuition perspective, this cutover occurs exactly when the point where the wave crosses the $x$-axis is at the point $(1,0)$, that is, when $$\frac{\sec \theta^* - 1}{2} = 1,$$ or $\sec \theta^* = 3,$ or $\theta^* = \cos^{-1} \frac{1}{3}.$ At this critical point, the longest possible stretch of land that the wave is covering at 10:05 a.m. is $$\ell^* = \ell( \cos^{-1} \frac{1}{3} ) = \sqrt{ (3 - \frac{1}{3}) (1 + \frac{1}{3} ) } = \frac{4}{3} \sqrt{2} \approx 1.88561808316\dots$$ miles.

For absolute completeness we can cover the cases of $\theta = 0,$ in which case wave is represented by vertical lines and at 10:05 a.m., the wave would be covering the unit interval along the positive $y$-axis and have a length of one mile. For the case of $\theta = \frac{\pi}{2},$ where the wave is represented by horizontal lines and the wave would be at $y= \frac{1}{2}$ and cover a distance of $2\sqrt{1 - \frac{1}{2}} = \sqrt{3} \lt \frac{4}{3} \sqrt{2}$ at 10:05 a.m. By symmetry, we can cover the case of $\theta \in (\frac{\pi}{2} , \pi)$ and by another symmetry we can cover the case of what if instead of last hitting the point at $(1,0)$ the wave first hits the point at $(1,0)$ and then only at 10:10 a.m. arrives at the point $(\cos \theta, \sin \theta),$ to show that there is certainly not a larger possible stretch of land to be found if instead of the subset $(0, \frac{\pi}{2})$ that we spent most of our time on, the wave came with an orientation of \theta with respect to the positive $x$-axis for some $\theta \in (\frac{\pi}{2}, 2\pi)$... but more on this later.

Posted by at No comments:

Sunday, May 31, 2026

Two sheep

Two sheep are at two random points inside a square pen. They are munching grass and staring in two random directions. Each sheep has a field of view that’s 180 degrees. What is the probability that they both see each other?

Let's first start with two sheep in a one-dimensional unit interval pen each of which randomly either look to the right or to the left. Obviously in this case, each sheep has a $50\%$ chance of randomly looking at the other sheep and their directional choices are independent, so the probability is $25\%.$

But wait, weren't we dealing with two sheep in a unit square pen? Sure, let's assume that one sheep is at the point $(a,b)$ and another is at $(c,d).$ Next let's draw the straight line $y = \frac{d-b}{c-b} (x - a) + b$ through these two points. The sheep at $(a,b)$ is staring into space in a direction that makes an angle $\theta$ with respect to the ray of the line that we just drew as $x$ increases. We see that either $0 \leq \theta \leq \frac{\pi}{2},$ in we can think of this as looking to the right with respect to the line between the sheep, or $\frac{\pi}{2} \leq \theta \leq \pi$ in which case we can think of this as looking to the left. Therefore, despite living in a fully two dimensional field, we can project this problem back into the one dimensional problem. Similarly, we can therefore conclude that the probability of these two sheep seeing each other in the square pen is $25\%.$

Posted by at No comments:

Three sheep

Now, three sheep are at three random points inside a square pen. They are munching grass and staring in three random directions. As before, each sheep has a field of view that’s 180 degrees. What is the probability that all three sheep see each other?

Here we have to be a bit less handwavy, but let's assume that the sheep are located at points $A=(a_1,a_2),$ $B=(b_1,b_2)$ and $C=(c_1,c_2)$, where the measure of the angle $m\angle CAB = \alpha,$ $m\angle ABC = \beta,$ and $m\angle BCA = \gamma.$ In this case the sheep at $A$ can only see $B$ if it is looking up to an angle of $\frac{\pi}{2}$ to the left or right of the line between $A$ and $B$. Similarly, it can only see $C$ if it is looking up to an angle of $\frac{\pi}{2}$ to the left or right of the line between $A$ and $C.$ Let's assume that the line between $A$ and $B$ forms an angle of $\theta$ with respect to the positive $x$-axis. Then since $m\angle CAB = \alpha,$ we see that the line between $A$ and $C$ must either form an angle of $\theta-\alpha$ or $\theta+\alpha.$ That means that either the sheep must be staring in the direction of $\phi \in \left[ \theta - \frac{\pi}{2}, \theta + \frac{\pi}{2} \right] \cap \left[ \theta - \alpha - \frac{\pi}{2}, \theta - \alpha + \frac{\pi}{2} \right] = \left[ \theta - \frac{\pi}{2}, \theta - \alpha + \frac{\pi}{2} \right]$ or $\phi \in \left[ \theta - \frac{\pi}{2}, \theta + \frac{\pi}{2} \right] \cap \left[ \theta + \alpha - \frac{\pi}{2}, \theta + \alpha + \frac{\pi}{2} \right] = \left[ \theta + \alpha - \frac{\pi}{2}, \theta + \frac{\pi}{2} \right],$ so in either case we have that the probability of the sheep at $A$ looking at both the sheep at $B$ and the sheep at $C$ is $$\frac{ \pi - \alpha }{ 2\pi} = \frac{1}{2} - \frac{\alpha}{2\pi}.$$ Since there was nothing special about $A$ and everything is independent, we see that the probability of all of the sheep looking at each other given the angles $\alpha,$ $\beta$ and $\gamma$ are $$p(\alpha, \beta, \gamma) = \left( \frac{1}{2} - \frac{\alpha}{2\pi}\right) \left( \frac{1}{2} - \frac{\beta}{2\pi} \right) \left( \frac{1}{2} - \frac{\gamma}{2\pi}\right).$$ We see that the maximum probability for any particular shape would be for an equilateral triangle $(\alpha=\beta=\gamma=\frac{\pi}{3})$, where the probability is $\frac{1}{27} = 3.\overline{703}\%,$ whereas the minimum probability is for three collinear points where say $\alpha=\pi$ and $\beta=\gamma=0,$ where the probability is $0.$

So if we know where $A$, $B$ and $C$ are all then we can get the side lengths of the triangle $a=\|B-C\|,$ $b=\|A-C\|,$ and $c=\|A-B\|.$ From this we can use the law of cosines to get \begin{align*}\alpha &= \cos^{-1} \left( \frac{b^2 + c^2 - a^2}{2bc} \right) = \cos^{-1} \left( \frac{ \|A-C\|^2 + \|A-B\|^2 - \|B-C\|^2}{ 2 \|A-B\| \|A-C\| } \right)\\ \beta &= \cos^{-1} \left( \frac{a^2 + c^2 - b^2}{2ac} \right) = \cos^{-1} \left( \frac{ \|B-C\|^2 + \|A-B\|^2 - \|A-C\|^2}{ 2 \|A-B\| \|B-C\| } \right)\\ \gamma &= \cos^{-1} \left( \frac{a^2 + b^2 - c^2}{2ab} \right) = \cos^{-1} \left( \frac{ \|B-C\|^2 + \|A-C\|^2 - \|A-B\|^2}{ 2 \|A-C\| \|B-C\| } \right),\end{align*} so we get $$p(A,B,C) = \left( \frac{1}{2} - \frac{\alpha(A,B,C)}{2\pi} \right) \left( \frac{1}{2} - \frac{\beta(A,B,C)}{2\pi} \right) \left( \frac{1}{2} - \frac{\gamma(A,B,C)}{2\pi} \right)$$ Putting this all together we get the probability that all three sheep see each other as $$P = \iint_{A \in [0,1]^2} \iint_{B \in [0,1]^2} \iint_{C \in [0,1]^2} p(A,B,C) \,dA\,dB\,dC,$$ which we will just use some Monte Carlo to estimate this probability.

After 10,000 Monte Carlo simulations for $A$, $B$, and $C,$ we obtain an estimated probability of all three sheep looking at one another $P \approx 2.72\%$. Knowing the way that these problems work out I wouldn't be surprised if somehow the integral works out to roughly $\frac{e}{100},$ but looking at the gnarliness of the integral, I would also be relatively surprised if it did.

Posted by at No comments:

Monday, May 25, 2026

June's Shortest Cylindrical Shell Path

Now, June is on a hollowed-out cylinder, also known as a “cylindrical shell.” The shell’s outer radius is $2$ meters and its inner radius is $1$ meter. The shell is $2$ meters tall. June is on the outer edge of one of the cylinder’s two flat faces. Her dinner is on the opposite face, and all the way around on the other end of that face.

Once again, your job is to help June find the shortest path along the surface of the shell so that she can chow down as quickly as possible. What’s the length of this shortest path?

In the classic problem, June was able to roughly ignore the rounded edge of the cylinder and use two straight lines to reach the food. Here, the hollowed out center will force her to take another approach. Let's again assume that June starts at $(2, 0, 2),$ her food is at $(-2, 0, 0),$ June's last stop on the upper face is at the point $(\cos \theta, \sin \theta, 2)$ and first stop on the lower face is at the point $(\cos \phi, \sin \phi, 0),$ for some $0 \leq \theta \leq \frac{\pi}{3}$ and $\frac{2\pi}{3} \leq \phi \leq \pi.$ Here, we note that we can constrain $\theta$ and $\phi$ a little bit more than in the Classic problem, since the distance from $(\cos \theta, \sin \theta, 2)$ to $(\cos \phi, \sin \phi, 0)$ is $$d_2(\theta, \phi) = \sqrt{4 + (\phi-\theta)^2},$$ which is always less than descending vertically down from the upper to lower faces and then traversing along the inner radius from angle $\theta$ to $\phi,$ or vice versa. This means that we can rule out any of the values for $\theta$ and $\phi$ in $[\pi/3, 2\pi/3],$ where the straight line path would cross within the hollowed out inner circle and require June to travel along the curved inner radius.

Therefore, taking the Euclidean distances along the upper and lower faces of the cylindrical shell, we have that the Extra Credit distance formula is given by $$d(\theta, \phi) = \sqrt{5 - 4 \cos \theta} + \sqrt{5 + 4 \cos \phi} + \sqrt{4 + (\phi - \theta)^2}.$$ so we need to find $$d^* = \inf \left\{ d(\theta, \phi) \mid 0 \leq \theta \leq \frac{\pi}{3}, \frac{2\pi}{3} \leq \phi \leq \pi \right\}.$$ From a symmetry perspective, let's assume that $\phi = \pi - \theta,$ which means that we can define \begin{align*}\tilde{d} (\theta) &= d(\theta, \pi-\theta) \\ &= \sqrt{5 - 4\cos \theta} + \sqrt{5 + 4 \cos (\pi - \theta)} + \sqrt{4 + (\pi - \theta - \theta)^2} \\ &= 2 \sqrt{5 - 4 \cos \theta} + \sqrt{4 + (\pi - 2\theta)^2}.\end{align*} Here we see that $$\tilde{d}^\prime (\theta) = \frac{4\sin \theta}{\sqrt{ 5 - 4 \cos \theta}} + \frac{ 2 (2\theta - \pi) }{\sqrt{ 4 + (\pi - 2\theta)^2} },$$ so setting this equal to zero we get $$\frac{4 \sin \theta}{\sqrt{5 - 4 \cos \theta}} = \frac{ 2 (\pi - 2\theta) }{\sqrt{4 + (\pi - 2\theta)^2}}.$$ Squaring both sides and using some trigonometry identities, we see that this is equivalent to the implicit function $$\theta + \frac{2\sin \theta}{2 \cos \theta - 1} = \frac{\pi}{2}.$$

Let's use Newton-Raphson method on the function $$f(\theta) = \theta + \frac{2\sin \theta}{2\cos \theta - 1} - \frac{\pi}{2},$$ where $$f^\prime(\theta) = 1 + \frac{4-2\cos \theta}{(2\cos \theta - 1)^2},$$ to figure out the proper root of this implicit function, we see that we can start with an example of $\theta_0 = \frac{1}{2},$ then $$\theta_{n+1} = \theta_n - \frac{f(\theta_n)}{f^\prime(\theta_n)},$$ for $n = 0, 1, 2, \dots.$ We see that after only a few steps we quickly settle into $$\theta^* = \lim_{n \to \infty} \theta_n = 0.457751785361\dots.$$ This translates into a minimal distance for June to get to her food on the cylindrical shell of $$\tilde{d}^* = \tilde{d}(\theta^*) \approx 5.368959019243\dots$$ meters.

$n$ $\theta_n$ $f(\theta_n)$ $f^\prime(\theta_n)$ $\tilde{d}(\theta_n)$
1 0.500000000000 0.198927402511 4.936412045223 5.371299778386
2 0.459702026353 0.008790035183 4.516178419967 5.368964120693
3 0.457755682704 0.000017530945 4.498196526681 5.368959019263
4 0.457751785377 0.000000000070 4.498160714274 5.368959019243
5 0.457751785361 0.000000000000 4.498160714132 5.368959019243
Posted by at No comments:

June's Shortest Cylindrical Path

June the ant is on a cylinder. More specifically, she is on the edge of one of the cylinder’s two circular faces. Her dinner is on the edge of the opposite circular face, and all the way around on the other side of that face. The radius of the cylinder is $2$ meters and its height is $2$ meters.

Your job is to help June find the shortest path along the surface of the cylinder so that she can chow down as quickly as possible. What’s the length of this shortest path?

Let's assume that June is located at the point $(2,0,2)$ while her food is located at $(-2,0,0),$ making the center of the cylinder aligned with the positive $z$-axis. Let's assume that June's path last leaves the top circular face at the point $(2\cos \theta, 2\sin \theta, 2),$ for some $0 \leq \theta \leq \pi.$ Similarly, let's assume that June's path first arrives on the bottom circular face at the point $(2 \cos \phi, 2\sin \phi, 0),$ for some $\theta \leq \phi \leq \pi.$ Though June's path could theoretically wander about anywhere, let's assume that she will walk in straight lines when on the two circular faces and on a straight line with respect to the curved outer edge. The path along the upper circular face will have a distance $$d_1(\theta) = \sqrt{ (2\cos \theta - 2)^2 + (2 \sin \theta)^2 + (2-2)^2 } = 2 \sqrt{ 1 - 2 \cos \theta } = 4 \sin \frac{\theta}{2}.$$ The path along the lower circular face will have a distance $$d_3(\phi) = \sqrt{ (2 \cos \phi + 2)^2 + (2 \sin \phi)^2 + (2-2)^2 } = 2 \sqrt{ 1 + 2 \cos \phi } = 4 \cos \frac{\phi}{2}.$$ The path along the curved outer edge is given by $d_2(\theta, \phi) = 2 \sqrt{1 + (\phi - \theta)^2},$ which we can see either by unrolling the curved outer edge into a rectangle and realizing that the path is the hypotenuse of a triangle with height $2$ and base $2 (\phi - \theta)$, or more formally by paramaterizing the path along the outer edge as the curve $x(t) = 2 \cos t,$ $y(t) = 2 \sin t,$ $z(t) = 2 \frac{\phi - t}{\phi - \theta},$ for $t \in [\theta, \phi]$ and finding \begin{align*}d_2(\theta, \phi) &= \int_\theta^\phi \sqrt{ \left(\frac{dx}{dt}\right)^2 + \left( \frac{dy}{dt} \right)^2 + \left( \frac{dz}{dt} \right)^2 } \,dt \\ &= \int_\theta^\phi \sqrt{ (-2\sin t)^2 + (2 \cos t)^2 + \left(\frac{-2}{\phi - \theta}\right)^2 } \,dt \\ &= \int_\theta^\phi \sqrt{ 4 \sin^2 t + 4 \cos^2 t + \frac{4}{(\phi - \theta)^2} } \,dt \\ &= \frac{2 \sqrt{1 + (\phi - \theta)^2}}{\phi - \theta} \int_\theta^\phi \,dt \\ &= 2 \sqrt{ 1 + (\phi - \theta)^2 }.\end{align*} So the total distance is $$d(\theta, \phi) = d_1(\theta) + d_2(\theta, \phi) + d_3(\phi) = 4 \sin \frac{\theta}{2} + 4 \cos \frac{\phi}{2} + 2 \sqrt{ 1 + (\phi - \theta)^2 }.$$

So June would want to find $$d^* = \inf \{ d(\theta, \phi) \mid 0 \leq \theta \leq \phi \leq \pi \}.$$ Let's treat the case where $\theta = \phi$ and hence we have a univariate problem $$\tilde{d}(\theta) = 4 \sin \frac{\theta}{2} + 4 \cos \frac{\theta}{2} + 2.$$ We see that in this case, we have $$\frac{d}{d\theta} \tilde{d} = 2 \cos \frac{\theta}{2} - 2 \sin \frac{\theta}{2}$$ which has critical points whenever $\tan \frac{\theta}{2} = 1,$ that is $\frac{\theta}{2} = \frac{\pi}{4},$ or $\theta^* = \frac{\pi}{2}.$ Therefore, we see that the minimal value of $$ \tilde{d}^* = \inf_{0 \leq \theta \leq \pi} \tilde{d}(\theta) = \min \left\{ \tilde{d}(0), \tilde{d}(\pi), \tilde{d} \left( \frac{\pi}{2} \right) \right\} = \min \{ 6, 6, 4\sqrt{2}+2 \} = 6,$$ which occurs when either $\theta=0$ or $\theta=\pi.$ This amounts to either going straight down the curved side and then taking a straightline path across the diameter to the food, or vice versa.

Let's fix some $\theta \in [0,\pi)$ and then try to minimize with respect to $\phi.$ We see that $$\frac{\partial d}{\partial \phi} = -2 \sin \frac{\phi}{2} + \frac{ 2(\phi - \theta)}{\sqrt{1 + (\phi-\theta)^2}}.$$ Setting this equal to zero and doing a bunch of algebra and trigonometry identities we get the implicit function $$\phi - \tan \frac{\phi}{2} = \theta.$$ Letting $g(t) = t - \tan \frac{t}{2},$ we see that $g^\prime(t) = 1 - \frac{1}{2} \sec^2 \frac{t}{2},$ so the largest possible value of $g$ occurs when $\sec^2 \frac{t}{2} = 2$ or equivalently when $\cos \frac{t}{2} = \frac{\sqrt{2}}{2},$ that is when $t = \frac{\pi}{2},$ and in particular we see that $$g(t) \leq g^* = g( \frac{\pi}{2} ) = \frac{\pi}{2} - 1.$$ Therefore, we see that if $\theta \geq \frac{\pi}{2} - 1$ then we have $\frac{\partial d}{\partial \phi} \leq 0$ for all $\phi \in [\theta, \pi],$ so if $\theta \gt \frac{\pi}{2} - 1,$ then the shortest path that can be obtained by choosing $\phi = \pi$ is $$ \inf_{\phi \in [\theta, \pi]} d(\theta, \phi) = d(\theta, \pi) = 4 \sin \frac{\theta}{2} + 2 \sqrt{ 1 + (\pi - \theta)^2}.$$ We see that in this case if we set $$\delta(\theta) = 4 \sin \frac{\theta}{2} + 2 \sqrt{ 1 + (\pi - \theta)^2}$$ that $$ \delta^* = \inf_{\theta \in [\frac{\pi}{2} -1, \pi]} \delta(\theta) = \delta(\pi) = 6.$$

Ok, so we are now left with only the case where $\theta \in [0, \frac{\pi}{2} -1).$ In this case, we can approximate the implicit equation using a cubic function, since $\tan \frac{t}{2} \approx \frac{t}{2} + \frac{t^3}{24} + O(t^4)$ for $|t| \lt 1.$ This yields the new approximate implicit equation $$\phi - \left( \frac{\phi}{2} + \frac{\phi^3}{24} \right) = \theta,$$ or equivalently, $$\phi^3 - 12\phi + 24 \theta = 0.$$ This cubic has three real roots, and the middle one will yield a local minimum since it will represent the place where $\frac{\partial d}{\partial \phi} \lt 0$ to the left of the root and $\frac{\partial d}{\partial \phi} \gt 0$ to the right of the root. From the Viete formula, we see that this root will be at $$\phi^*(\theta) = 4 \cos \left( \frac{ \cos^{-1} \left( -\frac{3\theta}{2} \right) - 2\pi }{3} \right).$$ Importantly, we remember that we got into this mess because $\phi^*(\theta)$ roughly satisfies $$\frac{\partial d}{\partial \phi} (\theta, \phi^*(\theta)) \approx 0.$$ So let's define $$\Delta(\theta) = d(\theta, \phi^*(\theta)),$$ and look to find $\Delta^* = \inf \{\Delta(\theta) \mid \theta \in [0,\frac{\pi}{2}-1]\}.$ Thankfully, we see that \begin{align*}\Delta^\prime(\theta) &= 2 \cos \frac{\theta}{2} - 2 \sin \frac{\phi^*(\theta)}{2} (\phi^*)^\prime (\theta) + \frac{ 2(\phi^*(\theta) - \theta) }{ \sqrt{ 1 + (\phi^*(\theta) - \theta)^2 }} (\phi^*)^\prime (\theta) \\ &= 2 \cos \frac{ \theta}{2} + (\phi^*)^\prime (\theta) \left( - 2 \sin \frac{ \phi^*(\theta) }{2} + \frac{ 2( \phi^*(\theta) - \theta }{ \sqrt{ 1 + (\phi^* (\theta) - \theta)^2 }} \right) \\ & = 2 \cos \frac{ \theta}{2} + (\phi^*)^\prime (\theta) \frac{\partial d}{\partial \phi} (\theta, \phi^*(\theta)) \\ & \approx 2 \cos \frac{\theta}{2} \gt 0,\end{align*} for all $\theta \in [0, \frac{\pi}{2} - 1),$ therefore we see that $\Delta^* = \Delta(0) = 6.$

Therefore, since we went through all of the cases, we now anticlimactically confirm that in fact, June's shortest path to the food is 6 meters long.

Posted by at No comments:

Monday, May 11, 2026

Extra Credit Random-Ade Recipe

Once again I’m preparing random-ade, but this time I have three 12-ounce glasses.

I fill the first glass with a random amount of lemon juice, the second glass with a random amount of lime juice, and the third glass with a random amount of water. As before, each amount is chosen uniformly between 0 and 12 ounces, and all amounts are independent. Next, I pour an equal amount from each glass into the pitcher until one of the glasses is empty.

At this point, I refill that empty glass with yet another random amount of the same liquid it previously contained. Once again, I pour an equal amount from each glass into the pitcher until one of the glasses is empty.

Then I refill that now-empty glass with yet another random amount of the same liquid it previously contained. Again, I pour an equal amount from each glass into the pitcher until one of the glasses is empty.

On average, how much random-ade can I expect to prepare?

OK, so in the extra credit version we can let $E, I, W \sim U(0,12)$ represent the random volume in ounces of l"E"mon juice, l"I"me juice and "W"ater, respectively, that are initially poured into the glasses. Let $V_1, V_2 \sim U(0,12)$ be the additional random volumes that are poured into the then empty glasses. Here again we have $E, I, W, V_1,$ and $V_2$ independent. We have $$\tilde{R}(E,I,W,V_1,V_2) = \begin{cases} \min \{E,I,W\} + V_1 + V_2, & \text{if $V_1 + V_2 \leq \text{med} \{E, I, W \} - \min \{E, I, W \}$} \\ \text{med} \{E, I, W\}, &\text{if $V_1 \leq \text{med} \{E, I, W \} - \min \{E, I, W\} \leq V_1 + V_2$}\\ \text{med} \{E, I, W \} + \min \{ V_1, V_2 \}, &\text{if $\text{med}\{E, I, W\} - \min \{E, I, W\} \leq V_1$} \\ & \,\,\,\,\,\, \text{ and $\min \{V_1, V_2 \} \leq \max \{E, I, W \} - \text{med} \{E, I, W\}$}\\ \max \{E, I, W \}, &\text{if $\text{med} \{E, I, W\} - \min \{ E, I, W\} \leq V_1$}\\ & \,\,\,\,\,\, \text{ and $\min \{V_1, V_2\} \geq \max \{E, I, W\} - \text{med} \{E, I, W\}.$} \end{cases}$$

As we can see there are many possible cases to go through in order to get the theoretical solution; however, it is relatively easy to set up a Monte Carlo simulation. Doing so with $N= 100,000$ simulations gives an average $\tilde{R}$ value of $\hat{R} = 7.400516$ with standard error of $0.0081.$ So we can confidently say that the expected volume of the Extra Credit Ranom-Ade is about 7.40 ounces.

Posted by at No comments:

Classic Random-Ade Recipe

I’m preparing a mixture of “random-ade” using a large, empty pitcher and two 12-ounce glasses.

First, I fill one glass with some amount of lemon juice chosen randomly and uniformly between 0 and 12 ounces. I fill the other glass with some amount of water, also chosen randomly and uniformly between 0 and 12 ounces. Next, I pour an equal amount from each glass into the pitcher until one of the glasses is empty.

At this point, I refill that empty glass with yet another random amount of the same liquid it previously contained. Once again, I pour an equal amount from each glass into the pitcher until one of the glasses is empty.

On average, how much random-ade can I expect to prepare? (Note that all three random amounts in this problem are chosen independently of each other.)

Let's first define some terms. Let $L \sim U(0,12)$ be the random volume of lemon juice in ounces first poured into the lenom juice glass. Let $W \sim U(0,12)$ be the random volumn of water in ounces first poured into the water glass. Let $V \sim U(0,12)$ be the random volume poured into the empty glass after the first volume of random-ade was poured into the pitcher. By desing with have $L,$ $W,$ and $V$ independent.

There are two volumes of random-ade that are generated. First, the amount $\min \{ L, W \}$ is poured into the pitcher. After $V$ is poured into the now empty glass, the two glasses have volumes of $|L - W|$ and $V$. So the second volume of random-ade that is poured is $\min \{ V, |L - W | \}.$ Therefore, the total amount of random-ade that is generated is $$R(L, W, V) = \min \{ L, W \} + \min \{ V, |L - W |\}.$$ The only thing left to do is to take the average.

We can do this by first taking the conditional average based on the value of $V.$ This gives us a nice two dimensional integral, \begin{align*} R(V) = \mathbb{E} \left[ R( L, W, V ) \mid V \right] &= \int_0^{12} \int_0^{12} R( L, W, V ) \, \frac{dW}{12} \frac{dL}{12} \\ &= 2 \int_0^{12} \int_L^{12} R(L, W, V) \frac{dW}{12} \frac{dL}{12},\end{align*} where we second inequality is based on the symmetry about the line $L = W.$ We can break this further down into three cases:

  • $A = \{ (L, W) \mid 0 \leq L \leq 12 - V, L + V \leq W \leq 12 \},$ where we have $R(L, W, V) = L + V;$
  • $B = \{ (L, W) \mid 0 \leq L \leq 12 - V, L \leq W \leq L + V \},$ where we have $R(L, W, V) = L + (W-L) = W;$
  • $C = \{ (L, W) \mid 12 - V \leq L \leq 12, L \leq W \leq 12 \},$ where we have $R(L, W, V) = L + (W-L) = W.$

Therefore, we see that \begin{align*}A(V) &= \iint_A R(L, W, V) dA = \int_0^{12-V} \int_{L+V}^{12} (L+V) \,\frac{dW}{12} \frac{dL}{12} \\ &= \frac{1}{144} \int_0^{12-V} (L+V)(12 - L - V) \,dL \\ &= \frac{1}{144} \int_V^{12} u(12-u) \,du \\ &= \frac{1}{144} \left[ 6u^2 - \frac{u^3}{3} \right]_{u=V}^{u=12} \\ &= 2 - \frac{1}{24}V^2 + \frac{1}{432}V^3\end{align*} along with \begin{align*}B(V) &= \iint_B R(L, W, V) dA = \int_0^{12-V} \int_{L}^{L+V} W \, \frac{dW}{12} \frac{dL}{12} \\ &= \frac{1}{144} \int_0^{12-V} \left[\frac{W^2}{2} \right]^{W=L+V}_{W=L} \,dL \\ &= \frac{1}{144} \int_0^{12-V} \left( \frac{(L+V)^2 - L^2}{2} \right) \,dL \\ &= \frac{1}{288} \int_0^{12-V} 2LV + V^2 \,dL \\ &= \frac{1}{288} \left( V(12-V)^2 + V^2(12-V) \right) \\ &= \frac{1}{2}V - \frac{1}{24} V^2,\end{align*} and finally \begin{align*}C(V) &= \iint_C R(L,W,V) dQ = \int_{12-V}^{12} \int_L^{12} W \,\frac{dW}{12} \frac{dL}{12} \\ &= \frac{1}{144} \int_{12-V}^{12} \left(72 - \frac{L^2}{2} \right) \,dL \\ &= \frac{1}{144} \left[ 72L - \frac{L^3}{6} \right]_{L=12-V}^{L=12} \\ &= \frac{1}{144} \left( \left(72 \cdot 12 - \frac{12^3}{6} \right) - \left( 72 \cdot (12 - V) - \frac{(12-V)^3}{6} \right) \right) \\ &= \frac{1}{144} \left( 6V^2 - \frac{V^3}{6} \right) = \frac{1}{24} V^2 - \frac{1}{864} V^3. \end{align*} So putting this altogether we see that \begin{align*}R(V) &= \mathbb{E}\left[ R(L, W, V) \mid V \right] \\ &= 2 \left( A(V) + B(V) + C(V) \right) \\ &= 2 \left( 2 + \frac{1}{2} V - \frac{1}{24} V^2 + \frac{1}{864} V^3 \right) \\ &= 4 + V - \frac{1}{12} V^2 + \frac{1}{432} V^3.\end{align*} Therefore, taking the expected value we get that the average volume of random-ade made with this Classic recipe is \begin{align*}\mathbb{E}[R] &= \int_0^{12} R(V) \, \frac{dV}{12} \\ &= \frac{1}{12} \int_0^{12} \left( 4 + V - \frac{1}{12} V^2 + \frac{1}{432} V^3 \right) \,dV \\ &= \frac{1}{12} \left( 4 \cdot 12 + \frac{12^2}{2} - \frac{12^3}{36} + \frac{12^4}{1728} \right) \\ &= 4 + 6 - 4 + 1 = 7\end{align*} ounces.

Posted by at No comments:

Monday, May 4, 2026

A frog's tour

The frog is jumping around the board with the same minimum distance $L$ you just found. But this time, the frog also wants to be able to hop to every location on the chessboard. What is the minimum value of $N$ for which this is possible?

In general, we want to find the equivalent of a knight's tour, a path taken by a knight that visits all of the squares on the chess board exactly once. The frog doesn't specify that it wants to start and end his tour of the board at the same spot, so this is known as an ``open'' tour, as opposed to a closed tour that starts and ends on the same square. In particular, if we hadn't added the extra condition of not being a rook's move away from the starting spot and could stick with knight moves for the frog, then the smallest possible board that has a knight's tour is a $5\times 5$ board. One heuristic method for finding knight's tour is known by Warnsdorf's rule: Move from the current square to the neighbor that has the fewest remaining viable moves.

Ok, so we found $L = \sqrt{65},$ which means any of the 16 possible steps: $(\pm 1, \pm 8),$ $(\pm 8, \pm 1),$ $(\pm 4, \pm 7),$ $(\pm 7, \pm 4).$ For $N\leq 13,$ there are inaccessible squares, e.g. on a $13\times 13$ board, the center square $g7$ has no adjacent squares, since each of the borders are only $6$ squares away from the center, so any frog jump away from the center square will end up off the board.

For $N=14,$ using a modified Warnsdorf's rule heuristi, we can find an open frog’s tour of all squares on a $14 \times 14$ board, see below using algebraic notation:

1.a129.j1457.g785.e5113.n2141.d14169.l2
2.h530.k658.n1186.d13114.j9142.e6170.d1
3.g1331.l1459.m387.k9115.f2143.f14171.k5
4.n932.h760.f788.d5116.m6144.m10172.c6
5.m133.a1161.b1489.l6117.e7145.f6173.j2
6.i834.e462.i1090.k14118.i14146.m2174.k10
7.a935.d1263.e391.d10119.j6147.e1175.c11
8.b136.c464.a1092.e2120.n13148.l5176.k12
9.f837.b1265.b293.i9121.f12149.e9177.j4
10.n738.f566.j194.b13122.m8150.i2178.b3
11.g339.n467.n895.c5123.i1151.h10179.i7
12.h1140.m1268.g496.g12124.a2152.a14180.b11
13.a741.l469.h1297.f4125.h6153.i13181.j10
14.h342.e870.a898.e12126.g14154.b9182.k2
15.g1143.l1271.h499.a5127.n10155.i5183.c3
16.k444.m472.l11100.i6128.g6156.a6184.j7
17.d845.i1173.k3101.e13129.c13157.h2185.b6
18.h146.a1274.j11102.l9130.b5158.g10186.c14
19.l847.b475.i3103.k1131.a13159.n14187.k13
20.d748.j376.b7104.g8132.h9160.f13188.d9
21.h1449.c777.j8105.n12133.g1161.g5189.c1
22.l750.k878.n1106.f11134.c8162.h13190.j5
23.e1151.d479.m9107.m7135.j12163.d6191.c9
24.a452.c1280.e10108.f3136.n5164.e14192.j13
25.h853.k1181.a3109.b10137.m13165.l10193.n6
26.l154.l382.i4110.c2138.f9166.d11194.g2
27.d255.m1183.b8111.g9139.m5167.k7195.f10
28.c1056.n384.i12112.f1140.l13168.d3196.m14

So, we have shown that if all the frog wanted was to make jumps of size $L=\sqrt{65}$ and have an open tour of the entire board, then $N=14$ would be the minimal size of the chess board.

However, covering bases and doing a deep grammatical scrub of the prompt, since it says the frog “also wants to be able to hop to every location on the chessboard", it means that the frog must still want to be able to do its rhomboidal path from the Classic problem. Since the path goes from $(-4,-7)$ to $(1,8),$ we need to have at least $N=16$ squares, that is, $\{-7, -6, \dots, -1, 0, 1, \dots, 8\}.$ This would rule out our $14 \times 14$ frog's path. However, we can again use Warnsdorf's rule to find a frog’s tour of all squares on a $16\times 16$ board, see below:

1.a133.m1165.j1297.f8129.l6161.c13193.i15225.d12
2.i234.e1066.b1398.b15130.d5162.k12194.j7226.k8
3.a335.m967.j1499.a7131.k1163.l4195.b8227.j16
4.b1136.n168.c10100.h11132.l9164.e8196.f1228.f9
5.c337.f269.g3101.a15133.p16165.i1197.e9229.m5
6.d1138.n370.n7102.i14134.o8166.h9198.i16230.l13
7.e339.f471.m15103.h6135.g9167.d16199.h8231.d14
8.a1040.g1272.f11104.a2136.c16168.l15200.d1232.h7
9.b241.o1173.b4105.i3137.d8169.m7201.l2233.p6
10.j142.g1074.a12106.a4138.l7170.n15202.p9234.h5
11.c543.o975.i13107.b12139.k15171.o7203.h10235.o1
12.k444.p176.j5108.j11140.c14172.h3204.d3236.g2
13.l1245.h277.c1109.b10141.d6173.g11205.c11237.n6
14.m446.p378.b9110.f3142.l5174.c4206.k10238.m14
15.n1247.h479.j10111.n4143.p12175.j8207.c9239.f10
16.g1648.p580.k2112.f5144.o4176.k16208.j13240.n9
17.o1549.o1381.l10113.m1145.k11177.l8209.k5241.j2
18.p750.k682.m2114.e2146.d7178.p15210.d9242.b3
19.l1451.d283.n10115.d10147.h14179.i11211.h16243.i7
20.d1352.l184.j3116.c2148.g6180.b7212.o12244.p11
21.e553.k985.c7117.k3149.k13181.j6213.p4245.o3
22.m654.o1686.g14118.o10150.c12182.b5214.i8246.n11
23.n1455.p887.f6119.n2151.g5183.a13215.e1247.g15
24.f1356.i488.e14120.m10152.o6184.e6216.a8248.o14
25.b657.a589.m13121.e11153.p14185.f14217.e15249.g13
26.a1458.e1290.i6122.m12154.h15186.n13218.l11250.c6
27.e759.d491.p2123.e13155.g7187.f12219.m3251.k7
28.d1560.l392.h1124.a6156.k14188.m16220.f7252.j15
29.l1661.p1093.o5125.i5157.c15189.n8221.b14253.b16
30.m862.o294.p13126.b1158.g8190.g4222.i10254.c8
31.n1663.g195.i9127.a9159.f16191.h12223.a11255.j4
32.f1564.n596.e16128.h13160.j9192.a16224.e4256.i12

So, we have shown that if the frog wanted both to make jumps of size $L=\sqrt{65}$ in a rhombus pattern from the Classic problem and have an open tour of the entire board, then $N=16$ is the minimal size of the chess board.

Posted by at No comments:

Sunday, May 3, 2026

A frog's path

A frog is hopping around a chessboard, always from the center of one square to the center of another square. Each square has side length 1, but the board itself is not necessarily $8$-by-$8$. Instead, it’s $N$-by-$N$, where $N$ is some large whole number.

Every jump the frog makes must be the same distance, which we’ll call $L.$ The frog wants to make four jumps such that:

  • After the fourth jump, the frog has returned to its starting square.
  • The frog visits a total of four distinct squares along the way, including the square on which it starts (and also stops).
  • The path the frog takes is not a square loop.
  • The frog is never on a square that is diagonal (i.e., a bishop’s move away) or horizontal/vertical (i.e., a rook’s move away) from the starting square.

What is the smallest jumping distance $L$ for which this is possible?

Let's first analyze what happens if we ignore the rook's move away condition that was somewhat late breaking. In this case, the frog can emulate a standard chess knight which makes a jump of length $\ell = \sqrt{5}.$ Let's assume the frog is at a standard white knights position, say $b1$. The following four step circuit only violates the horizontal/vertical condition:

1. Nc3
2. Nb5
3. Na3
4. Nb1

We see that the frog returns to its starting spot; it visits four distinct squares; the path is not a square (though it is a rhombus); and it does not not hit any square that is a bishop's move away from the starting square (those are a2, c2, d3, e4, etc.). Alas, the additional condition to avoid a rooks move from the starting square was added, so there goes that simplified idea.

Ok, so let's first generalize so that we can solve the problem. Let's assume that we are at some starting square that we will call $(0,0)$. Then the set of all positions that are a bishop's or rook's move away from $(0,0)$ is defined by $$\mathfrak{X} = \left( \mathbb{Z} \times \{0\} \right) \cup \left( \{ 0 \} \times \mathbb{Z} \right) \cup \{ (p,q) \in \mathbb{Z}^2 \mid |p| = |q| \}.$$ The simplest idea is to perhaps move to different types of knight like pieces, perhaps that move $m$ squares in one direction and then $n$ squares in some perpendicular direction, with $1 \leq m \lt n,$ such that the frog could first move to one of the following eight squares: $(m,n), (m,-n), (-m,n), (-m,-n), (n,m), (n,-m), (-n,m), (-n,-m),$ where none of them are in $\mathfrak{X}.$ Without loss of generality, let's assume that the frog went to $x_1 = (m,n).$ Since we want $x_2 \not\in \mathfrak{X},$ the frog can only make the following moves to arrive at $$x_2 \in \left\{ (2m,2n), (m+n, n-m), (m-n, m+n) \right\}.$$ We see that in order for the frog to be able to make it back to $(0,0)$ at the end of its 4th move it would have to arrive at one of the following seven possibilities: $$x_3 \in \{ (m,-n), (-m,n), (-m, -n), (n,m), (n,-m), (-n, m), (-n,m) \}.$$ In this case, we can just test each of the distances from the candidate $x_2$ positions and $x_3$ positions and check whether any of them has a distance of $L = \sqrt{m^2+n^2}:$ \begin{align*} d( (2m,2n), (m,-n) ) &= \sqrt{m^2 +9n^2} \gt L \\ d( (2m,2n), (-m, n) ) &= \sqrt{9m^2 + n^2} \gt L \\ d( (2m,2n), (-m,-n) ) &= \sqrt{9m^2 +9n^2} = 3L \gt L \\ d( (2m,2n), (n, m) ) &= \sqrt{m^2 + n^2 + 4(m-n)^2} \geq L\\ d( (2m,2n), (n,-m) ) &= \sqrt{m^2 +9n^2} \gt L \\ d( (2m,2n), (-n, m) ) &= \sqrt{9m^2 + n^2} \gt L \\ d( (2m,2n), (-n,-m) ) &= \sqrt{m^2 +n^2+4(m+n)^2} \gt L \\ d( (m+n, n-m), (m, -n)) &= \sqrt{m^2 -4mn + 5n^2} = \sqrt{ m^2 + n^2 - 4n(m-n)} \\ d( (m+n, n-m), (-m,n) ) &= \sqrt{5m^2 -4mn + n^2} = \sqrt{ m^2 + n^2 + 4m(m-n)} \\ d( (m+n, n-m), (-m,-n)) &= \sqrt{5m^2 + 5n^2 } = \sqrt{5}L \gt L \\ d( (m+n, n-m), (n, m) ) &= \sqrt{5m^2 - 4mn + n^2} = \sqrt{ m^2 + n^2 + 4m(m-n)} \\ d( (m+n, n-m), (n,-m) ) &= \sqrt{m^2 + n^2 } = L \\ d( (m+n, n-m), (-n,m) ) &= \sqrt{5m^2 - 4mn + n^2} = \sqrt{ m^2 + n^2 + 4m(m-n)} \\ d( (m+n, n-m), (-n,-m)) &= \sqrt{m^2 + n^2 } = L \\ d( (m-n, m+n), (m, -n)) &= \sqrt{m^2 + n^2 } = L \\ d( (m-n, m+n), (-m,n) ) &= \sqrt{5m^2 -4mn + n^2} = \sqrt{ m^2 + n^2 + 4m(m-n)} \\ d( (m-n, m+n), (-m,-n)) &= \sqrt{m^2 + n^2 } = L \\ d( (m-n, m+n), (n, m) ) &= \sqrt{m^2 - 4mn + 5n^2} = \sqrt{ m^2 + n^2 - 4n(m-n)} \\ d( (m-n, m+n), (n,-m) ) &= \sqrt{m^2 - 4mn + 5n^2} = \sqrt{ m^2 + n^2 - 4n(m-n)} \\ d( (m-n, m+n), (-n,m) ) &= \sqrt{m^2 - 4mn + 5n^2} = \sqrt{ m^2 + n^2 - 4n(m-n)} \\ d( (m-n, m+n), (-n,-m)) &= \sqrt{5m^2 + 5n^2 } = \sqrt{5}L \gt L \\ \end{align*}

We see that there are nince cases where the distance is always greater than or equal to $L,$ with equality only when $m=n$, which we can ignore because the frog would not be able to complete a circuit. Additionally, there are eight cases, where the distances can either be greater or less than $L$ depending on the values of $m$ and $n,$ with equality only when $m=n$. Since if $m=n$ then $(m,n) \in \mathfrak{X}$, we can ignore these cases too. Finally, there are also 4 cases where the distance is equal to $L$ for any value of $m$ and $n$:

  • $(0,0) \to (m,n) \to (m+n, n-m) \to (n, -m) \to (0,0)$
  • $(0,0) \to (m,n) \to (m+n, n-m) \to (-n, -m) \to (0,0)$
  • $(0,0) \to (m,n) \to (m-n, m+n) \to (-m, n) \to (0,0)$
  • $(0,0) \to (m,n) \to (m-n, m+n) \to (-m, -n) \to (0,0)$

In each of these cases, we see that diagonal lengths are equal, for instance in the case of the first potential path we have diagonal lengths $$d((0,0), (m+n,n-m)) = d((m,n), (n,-m)) = \sqrt{(m+n)^2 + (m-n)^2} = \sqrt{2}L,$$ so these must be in fact forbidden squares, which are not allowed in the frog's path. So we are left with no acceptable paths with just one type of step.

OK, so what next? Naturally, we need to look for length $L$ where we can find two distinct solutions, $1 \leq a \lt b,$ $1 \leq m \lt n$ with $a \ne m$ and $b \ne n,$ such that $L = \sqrt{a^2 + b^2} = \sqrt{m^2 + n^2}.$ If we do have two such independent solutions, then we can take the following path, say $$(0,0) \to (a,b) \to (a-m, b-n) \to (-m, -n) \to (0,0),$$ which will certainly satisfy conditions 1 and 2 of the frog's path, since $(a,b) \ne (m,n).$ Let's check the diagonal lengths $$\delta_1 = d((0,0), (a-m, b-n)) = \sqrt{ (a-m)^2 + (b-n)^2 } = \sqrt{ 2(L^2 - am -bn) }$$ and $$\delta_2 = d((a,b), (-m,-n)) = \sqrt{ (a+m)^2 + (b+n)^2 } = \sqrt{2(L^2 + am + bn)},$$ where we see that $\delta_1 = \delta_2$ if and only if $m=n=0,$ which would not make for a very large frog's jump. Therefore, we must have different diagonal lengths, so this path is a rhombus but not a square. Finally, by construction we have $(a,b), (-m,-n) \not\in \mathfrak{X}.$ Further, since $(a,b) \ne (m,n)$ we have $a-m \ne 0$ and we have $b-n = \sqrt{L - a^2} - \sqrt{L^2-m^2},$ so we see that we would have $|b-n| = |a-m|$ if and only if we have $$\left| \frac{\sqrt{L^2 -a^2} - \sqrt{L^2 - m^2} }{a-m} \right| = 1.$$ However, this would happen if and only if $m = \sqrt{L^2 - a^2} = b$ and hence we would arrive at $n = a = \sqrt{L^2 - b^2},$ one of our two assumptions that $1 \leq a \lt b$ and $1 \leq m \lt n$ is violated. Therefore, we see that $(a-m, b-n) \not\in \mathfrak{X}$ as well.

Now that we have proven that we can get a bona fide frog's path whenever there are two distinct positive solutions of $a^2 + b^2 = K = m^2 + n^2$ we simply need to find the smallest possible value of $K$ that has two such distinct solutions. To do this, let's first avail ourselves of Jacobi's two-square theorem, which states that if $r_2(n)$ is the number of ways to represent that positive integer $n$ as the sum of two squares of integers, then $_2(n) = 0$ if there is some prime divisor $p \mid n$ with $p^k \mid n$ for $k$ odd and $p \equiv 3 \mod 4,$ and $$r_2(n) = 4( d_1(n) - d_3(n) ),$$ where $d_1(n)$ is the number of divisors of $n$ that are congruent to $1 \mod 4$ and $d_3(n)$ is the number of divisors of $n$ that are congruent to $3 \mod 4.$ We see for instance that $r_2(1) = 4,$ since $1 = 1^2 + 0^2 = (-1)^2 + 0^2 = 0^2 + 1^2 = 0^2 + (-1)^2.$ Similarly $r_2(10) = 8$ since $(\pm 1)^2 + (\pm 3)^2 = (\pm 3)^2 + (\pm 1)^2 = 10.$ For our purposes, the four different combinations are not super interesting, so we just need to look for small values of $K$ for which $r_2(K) \gt 8.$ We see that the first such integer is $K=25,$ where $r_2(25) = 12$ since we have $$0^2 + (\pm 5)^2 = (\pm 5)^2 + 0^2 = (\pm 3)^2 + (\pm 4)^2 = (\pm 4)^2 + (\pm 3)^2 = 25.$$ Similarly, we have $r_2(50) = 12$ since $$(\pm 1)^2 + (\pm 7)^2 = (\pm 7)^2 + (\pm 1)^2 = (\pm 5)^2 + (\pm 5)^2 = 50.$$ In both of these cases, we cannot actually obtain two distinct solutions $1 \leq a \lt b$ and $1 \leq m \lt n$ with $a^2 + b^2 = m^2 + n^2 = K,$ since in the case of $K = 25$ one of the solutions is contains a zero and in the case of $K=50$ one of the solutions is on the diagonal.

This brings us to the case of $K = 65,$ where we finally see that we get $r_2(65) = 16$ because we have \begin{align*}65 &= (\pm 1)^2 + (\pm 8)^2 \\ &= (\pm 8)^2 + (\pm 1)^2 \\ &= (\pm 4)^2 + (\pm 7)^2 \\ &= (\pm 7)^2 + ( \pm 4)^2.\end{align*} So we see that we can distinctly choose the solutions $(a,b) = (1,8)$ and $(m,n) = (4,7)$ and arrive at a frog's path with a minimal distance of $L = \sqrt{65},$ which gives one instance of the frog's desired minimal path as $$(0,0) \to (1,8) \to (-3,1) \to (-4,-7) \to (0,0).$$

Posted by at No comments:

Monday, April 27, 2026

The timing is nearly right ...

At various times of day, the minute and hour hands form a right angle. But is there a time of day when the hour hand, minute hand, and second hand together form two right angles, as illustrated below? If you can find such a time or times, what are they?

If you cannot find any such times, suppose the measures of the two nearly right angles formed by the three hands measure A and B degrees. What time or times of day minimize the square error function $$f(A, B) = (A − 90)^2 + (B − 90)^2?$$

By the rule of the benevolent Fiddler master, we can safely assume that there is no perfect time when the hour, minute and second hands each form right angles with one another. Otherwise, why come up with the second formulation, amirite?

Anywho, we already defined the phase of the hour and minute hands as $h(t)$ and $m(t),$ respectively. Similarly, since the second hand makes 60 full revolutions per hour, its phase can be modeled as $s(t) = 60t - \lfloor 60t \rfloor.$ By taking absolute values of the $\Delta$ function in the Classic problem we get the triangular wave with period $\tau_1 = \frac{12}{11}$ given by $$\Delta_1(t) = | h(t) - m(t) | = \left| \frac{11t}{12} - \left\lfloor \frac{11t}{12} + \frac{1}{2} \right\rfloor \right|.$$ Similarly, we can define the triangular wave with period $\tau_2 = \frac{12}{719}$ given by $$\Delta_2(t) = | h(t) - s(t) | = \left| \frac{719t}{12} - \left\lfloor \frac{719t}{12} + \frac{1}{2} \right\rfloor \right|$$ and the triangular wave with period $\tau_3 = \frac{1}{59}$ given by $$\Delta_3(t) = |m(t) - s(t)| = \left| 59t - \left\lfloor 59t + \frac{1}{2} \right\rfloor \right|.$$

While there is likely some complicated formula for determining which of $\Delta_1,$ $\Delta_2,$ and $\Delta_3$ should be considered the measures A and B, let's ignore this assignment difficult and just reason that we want to let A and B be the minimum and the median of $\Delta_1,$ $\Delta_2$ and $\Delta_3,$ respectively. So we can reframe $f(A,B)$ as $$f(t) = f(\Delta_1, \Delta_2, \Delta_3) = \left( \sum_{i=1}^3 \left(\Delta_i(t) - \frac{1}{4}\right)^2 \right) - \left( \max_i \Delta_i - \frac{1}{4} \right)^2.$$ After an exhaustive search through points in the interval $[0,12],$ our closest almost right times are at $t_1 = 3:49:04.0786$ and $t_2 = 12 - t_1 = 8:10:55.9214,$ each with value of $f(t_1)=f(t_2) = 6.13819\times 10^{-8}.$

Posted by at No comments:

Sunday, April 26, 2026

You probably could have just asked me to arrive at the right time ...

A standard analog clock includes an hour hand, a minute hand, and 60 minute markers, 12 of which are also hour markers.

At a certain time, both the hour hand and minute hand are both pointing directly at minute markers (either of which could also be an hour marker). The hour hand is 13 markers ahead (i.e., clockwise) of the minute hand. At what time does this occur?

Let's set up the problem. We can represent each hand by its phase on the clockface, that is the proportion of the entire rotation that the hand has already completed. Let $h(t)$ and $m(t)$ be the phase of the hour and minute hands, respectively, at time $t,$ measured in hours. Since the minute hand makes one full rotation every hour, we see that the minute hand's phase at time $t$ is always the fractional part of $t$, that is $m(t) = t - \lfloor t \rfloor.$ Similarly, since in one hour the hour hand only travels 1/12th of a rotation that we have $h(t) = t/12 - \lfloor t / 12 \rfloor.$

The difference in the phases can be transformed into the angle between the hour and minute hands, so we could look at $$\delta(t) = h(t) - m(t) = \left\lfloor t \right\rfloor - \left\lfloor \frac{t}{12} \right\rfloor - \frac{11t}{12}.$$ However, since the angle between two hands is always less than or equal to $180^\circ,$ or phase of $1/2,$ we instead should look at $$\Delta(t) = \delta(t) - \lfloor \delta(t) + 1/2 \rfloor = \begin{cases} -\frac{11}{12}t, & 0 \leq t \lt \frac{6}{11} \\ 1 - \frac{11}{12}t, & \frac{6}{11} \leq t \lt \frac{18}{11}; \\ \dots, & \\ k - \frac{11}{12}t, & \frac{6(2k-1)}{11} \leq t \lt \frac{6(2k+1)}{11}; \\ \dots, & \\ 11-\frac{11}{12}t, & \frac{138}{11} \leq t \lt 12. \end{cases}$$ We can see graphically that $\Delta$ is cyclical and that there are 11 full cycles within the 12 hour cycle of the clock face, that is, a period of $\tau = 12/11.$

Let's first try to find the solution to $$\Delta(t_0) = 1 - \frac{11t_0}{12} = \frac{13}{60},$$ with $6/11 \leq t_0 \lt 18/11.$ We see that we have $$t_0 = \frac{47}{55}.$$ Since $\Delta$ is periodic, we see that all of the solutions of the $\Delta = 13/60$ are of the form $$t_k = t_0 + k \tau = \frac{47}{55} + \frac{12k}{11} = \frac{47 + 60k}{55},$$ for $k = 0, 1, \dots, 10,$ as summarized in the table below.

$k$ $t_k$ hh:mm:ss
0 47/55 12:51:36
1 107/55 01:56:44
2 167/55 03:02:11
3 227/55 04:07:38
4 287/55 05:13:05
5 347/55 06:18:33
6 407/55 07:24:00
7 467/55 08:29:27
8 527/55 09:34:55
9 587/55 10:40:21
10 647/55 11:45:49

So we see that the appropriate time where the hour and minute hands are pointing at minute markers that are 13 markers apart is at 7:24.

Posted by at No comments:

Sunday, April 19, 2026

Buzzing with excitement

The children's game called “Buzz” (also known as “Fizz buzz”) is where players take turns reciting whole numbers in order. However, in one particular variant of the game, anytime a number is a multiple of 7 or at least one of its digits is a 7, the player must say “buzz” instead of that number.

For example, here is how the first 20 turns of the game should proceed: 1, 2, 3, 4, 5, 6, buzz, 8, 9, 10, 11, 12, 13, buzz, 15, 16, buzz, 18, 19, 20.

How many times should “buzz” be said in the first 100 turns of the game (including those mentioned above in the first 20 turns)?

There are 14 multiples of 7 that are less than 100, since $100 / 7 = 14.2857\dots,$ so each of those numbers would be buzzes. Additionally, given that if we remove the possibility of there being a 7, then there are only 9 possible digits to choose from to make an up to two digit number with no 7s, that is a number from 0 to 99. Since we don't want 0 but do want 100, we see that there still are 81 possible numbers that do not contain any 7's, so that means that there would be 100 - 81 = 19 numbers that would buzz because they contain a 7. However, we have some overlaps, since 7, 70 and 77 are also multiples of seven, so from the inclusion-exclusion principle, the total number of buzzes in the first 100 numbers is $19 + 14 - 3 = 30$ buzzes.

As we just saw, in the first 20 turns of the game, 15 percent of the numbers were “buzzed.” But as the game proceeds, an increasing frequency of numbers get buzzed.

There is a certain minimum number $N$ such that, for the Nth turn in the game and for every turn thereafter, at least half the numbers up to that point have been buzzed. What is this value of $N$?

We can also encode a quick Python script to enumerate all buzzes in the first $N$ numbers:

def buzz(N):
    b = []
    for i in range(1,N+1):
        if i % 7 == 0:
            b.append(i)
        elif '7' in str(i):
            b.append(i)
    return b

By either a healthy amount of hunting and pecking, or some more systematic sounding of the phase space, we see that when $N = 708588$ that there are exactly 354294 buzzes, which is good for a ratio of 50% buzzes.

Posted by at No comments:
Subscribe to: Posts (Atom)