Monday, June 23, 2025

Greedy Mowing Madness

You’re mowing a circular lawn with a radius of $1$ unit. You can mow in straight strips that are $1$ unit wide. The fewest number of passes you would need to mow the entire lawn is two, as shown below. In one pass (shown in blue) you can mow half the circle, and in the second pass (shown in red) you can mow the other half of the circle.

However, instead of minimizing the number of passes, you greedily choose how to orient each pass so it cuts as much of the unmowed grass as possible. A pass doesn’t have to go through the center of the circle and can be in any direction, but must be straight and cannot bend.With this “greedy” approach, how many passes will it take for you to mow the entire lawn?

First let's establish the first greedy mowing pass. Without loss of generality, we can set our circular lawn's center at the origin, and by rotating, we can assume that the first pass will be parallel to the $y$-axis. In this case, the center of the pass will be at the line $x = x_0$ for some $x_0 \in (-1,1)$ and the strip will cover the set $$\Omega_1(x_0) = \{ (x,y) \in B(0,1) \mid |x - x_0| \lt \frac{1}{2} \}.$$ The area of the circular lawn that this pass will mow is $$A_1(x_0) = \int_{\max \{ -1, x_0 - \frac{1}{2} \}}^{\min \{ 1, x_0 + \frac{1}{2} \}} 2 \sqrt{1-x^2} \,dx.$$ Differentiating under the integral sign, we get \begin{align*}A_1^\prime(x_0) &= 2\sqrt{ 1 - \min \{1, x+ \frac{1}{2} \}^2 } \frac{d}{dx} \min \{ 1, x + \frac{1}{2} \} - 2\sqrt{1 - \max \{ -1, x - \frac{1}{2} \}^2 } \frac{d}{dx} \max \{ -1, x - \frac{1}{2} \} \\ &= \begin{cases} 2\sqrt{1 - (x+\frac{1}{2})^2}, &\text{if $x \in (-1, -\frac{1}{2})$;} \\ 2\left( \sqrt{1 - (x+\frac{1}{2})^2} - \sqrt{1 - (x-\frac{1}{2})^2} \right), &\text{if $ x \in (-\frac{1}{2}, \frac{1}{2})$;}\\ -2 \sqrt{1 - (x-\frac{1}{2})^2}, &\text{if $x \in (\frac{1}{2}, 1).$}\end{cases}\end{align*} Solving we for $A^\prime_1(x_0) = 0$ we get the only critical point as $x^*_0 = 0,$ which yields $A_1(0) = \int_{-1/2}^{1/2} 2\sqrt{1-x^2}\,dx = \frac{\pi}{3} + \frac{\sqrt{3}}{2}.$ So let's assume that the first pass is $\Omega_1 = \{ (x, y) \in B(0,1) \mid |x| \lt \frac{1}{2} \}.$

Let's move on to the next greedy pass. Now obviously from the first pass we see that the optimal method is to have some path of the mower that goes through the origin, so without loss of generality, let's assume that the center of the second pass goes through the line $y = mx,$ for some $m \in (-\infty, \infty).$ The second pass is thus the area $$\Omega_2(m) = \{ (x,y) \in B(0,1) \mid | mx - y | \lt \frac{\sqrt{1 + m^2}}{2} \}.$$ The newly mowed area in pass two is the entirety of $A_1(0)$ minus the area of the overlap between the two passes $\Omega_1(0) \cap \Omega_2(m).$ For $m \in (-\frac{\sqrt{3}}{3}, \frac{\sqrt{3}}{3}),$ we see that the overlap is the parallelogram formed by the lines $x = \pm \frac{1}{2},$ $y = mx + \frac{\sqrt{1+m^2}}{2},$ and $y=mx-\frac{\sqrt{1+m^2}}{2},$ that is $O(m) = \sqrt{1+m^2}.$ Therefore, the new area mowed by pass two is $$A_2 (m) = A_1(0) - O(m) = \frac{\pi}{3} + \frac{\sqrt{3}}{2} - \sqrt{1+m^2}.$$ This is maximized when $m^* = 0,$ and when $$A_2^* = A_2(0) = \frac{\pi}{3} + \frac{\sqrt{3}}{2} - 1.$$ We can see that if $|m| \gt \frac{\sqrt{3}}{3},$ the overlapping area of $\Omega_1(0) \cap \Omega_2(m)$ is larger than the area given by the parallelogram when $m = \pm \frac{\sqrt{3}}{3},$ so $A_2(m) \lt A_2( \sqrt{3}/3)$ for all $|m| \gt \frac{\sqrt{3}}{3},$ so we can claim that not only is $m^*=0$ the optimizer within the neighborhood $(-\frac{\sqrt{3}}{3}, \frac{\sqrt{3}}{3})$ but in fact for all $m \in \mathbb{R}.$

So after two passes we are left with the unmowed area $$U = \{ (x,y) \in B(0,1) \mid \max \{ |x|, |y| \} \gt \frac{1}{2} \}.$$ This has four sub-regions, one in each quadrant of the plane. It is easy enough to construct a mowing path that covers at least two of the four sub-regions, but you cannot cover all four sub-regions with an acceptable mowing path, for instance, take the path $$\Omega_3 = \{ (x,y) \in B(0,1) \mid |x + y| \lt \frac{\sqrt{2}}{2} \}.$$ Though there is in fact definitely a better approach that can cover strictly greater than two complete sub-regions, once at least two of the four sub-regions are covered, all remaining unmowed area is coverable within one more pass. Therefore, the greedy approach will take four passes to cover the lawn.

Monday, June 16, 2025

Zeno's Paradoxical 5K - Extra Credit

I still want to run a negative split, but upping my tempo in discrete steps is such a slog. Instead, my next plan is to continuously increase my pace in the following way:

At the beginning of the race, I’ll start with a 24-minute pace. Then, wherever I am on the race course, I’m always running 10 percent faster than I was when I was twice as far from the finish line. Also, my speed should always be increasing in a continuous and smooth fashion. Using this strategy, how long will it take me to complete the 5K? Once again, I’m hoping it’s faster than my steady 23-minute pace, even though I started out slower.

Let's again assume that the race start at $x=0$ and finish at $x=5,$ but we will need to understand some sort of history, since otherwise when I am one step into the race, I would need to know how fast I was going about 2 steps closer than $5$ kilometers before the beginning of the race. So here let's define $x_n = 5(1 - 2^{-n})$ for $n = \mathbf{-1}, 0, 1, 2, \dots$ be breakpoints where we will be interested in defining our speed. Let $v(x)$ denote the velocity you are running (in kmph), when you are at some $x \in (-5,5).$ Again, here we are given that $v(0) = 12.5$ and that at any point $x \in (0,5)$ we have $$v(x) = 1.1 v(2x-5).$$ Since $x_0 = 0,$ and $2x_n-5 = x_{n-1}$ for each $n = 0, 1, \dots,$ we can use the recursive formula to find the values of $$v_n = v(x_n) = 12.5 \cdot 1.1^n, \,\, n = -1, 0, 1, 2, \dots$$

Now let's tackle what smooth means here. The link provided in the prompt to Wolfram suggests that we are talking about some sort of $C^n(-5,5)$ space of functions on $(-5,5)$ that are continuous and have continuous derivatives up to order $n$ for some $n.$ We could of course overachieve and go with $C^\infty(-5,5),$ which we will start with here, but then see if we can relax this for some more Zeno's 5K fun. So without further adieu, let's start with the $C^\infty(-5,5)$ solution:

First, by design and analogy, we are likely to have a velocity function $v$ that blows up to $\infty$ as $x \to 5^-.$ Let's try something from the parametric family $$v_\alpha(x) = \frac{12.5}{(1-\frac{x}{5})^\alpha}$$ for $\alpha \gt 0,$ which satisfy $v_\alpha \in C^\infty(-5,5),$ $v_\alpha(0) = 12.5$ and $v_\alpha^\prime (x) \geq 0$ for all $x \in (-5,5).$ The only thing left to do is to decide which value of $\alpha$ satisfied the recursion formula. Note that $$v_\alpha(2x-5) = \frac{12.5}{\left(1 - \frac{2x-5}{5}\right)^\alpha} = \frac{v_\alpha(x)}{2^\alpha},$$ for all $x \in (0, 5)$ so in order to satisfy the recursion formula $v(x) = 1.1 v(2x-5)$ we must have $$\alpha = \frac{\ln 1.1}{\ln 2}.$$ So we have a $C^\infty (-5,5)$ solution for velocity at position $x \in (0,5),$ $$v^*(x) = 12.5 \left( 1 - \frac{x}{5} \right)^{-\frac{\ln 1.1}{\ln 2}},$$ which gives a completion time for the $C^\infty$ extra credit Zeno's 5K of \begin{align*}T = \int_0^5 \, \frac{dx}{v(x)}& = \int_0^5 \frac{ \left(1 - \frac{x}{5} \right)^{\frac{\ln 1.1}{\ln 2}} }{12.5} \,dx\\ &= \frac{5}{12.5} \int_0^1 u^{\frac{\ln 1.1}{\ln 2}} \,du \\ &= \frac{5}{12.5} \frac{1}{1 + \frac{\ln 1.1}{\ln 2}} = 0.351647262315\dots \,\,\,\text{hours},\end{align*} or $21.0988357389\dots$ minutes.

Obviously, $C^\infty$ qualifies as smooth, but what if we are willing to go with only $C^1(-5,5)$ solutions. Obviously, since $C^\infty \subsetneq C^1,$ we still have the solution $v^*$ from above, but what if we use our points $\mathcal{X} = \{x_{-1}, x_0, x_1, \dots \}$ as knots to define a $C^1$ quadratic spline. Can we still get a solution that is C^1 and satisfies the recursion formula? It turns out, $\dots$ yes!

Lets define the velocity function $u = u(x)$ by spline components $$u_n(x) = a_n + b_nx + c_nx^2$$ for $x_{n-1} \leq x \leq x_n,$ for $n = 0, 1, 2, \dots.$ In order to satisfy the recursion formula, since $2x-5 \in (x_{n-1},x_n)$ for all $x \in (x_n, x_{n+1}),$ we would need \begin{align*}u_{n+1}(x) &= a_{n+1} + b_{n+1} x + c_{n+1} x^2 \\ &= 1.1 u_{n}(2x-5)\\ &= 1.1 \left( a_n + b_n (2x-5) + c_n (4x^2 - 20x + 25) \right)\\ &= 1.1 (a_n - 5 b_n + 25 c_n) + 1.1 (2b_n - 20c_n) x + 4.4 c_n x^2,\end{align*} so we must have the recursion formulae \begin{align*} a_{n+1} &= 1.1 \left( a_n - 5b_n + 25 c_n \right) \\ b_{n+1} &= 2.2 \left( b_n - 10 c_n \right) \\ c_{n+1} &= 4.4 c_n \end{align*} for all $n = 0, 1, \dots.$

Using this recursion formula we can define each quadratic spline component in terms of the parameters $(a_0, b_0, c_0).$ We need to confirm that we can choose appropriate values of $(a_0, b_0, c_0)$ such that the resulting spline $u = u(x) \in C^1(-5,5),$ that $u^\prime(x) \geq 0$ for all $x \in (-5,5)$ and the $u(0) = 12.5.$ Since $x_0 = 0$ is on both the $u_0$ and $u_1$ components of the spline and we want both $u$ and $u^\prime$ continuous at $x_0$ we must have $$u_0(0) = a_0 = u_1(0) = a_1 = 1.1 (a_0 - 5b_0 + 25 c_0) = 12.5$$ and $$u^\prime_0(0) = b_0 = u^\prime_1(0) = b_1 = 2.2 (b_0 - 10c_0).$$ So we can group these conditions into the system of three equations and three unknowns \begin{align*}a_0 &= 12.5 \\ 0.1 a_0 - 5.5 b_0 + 27.5 c_0 &= 0 \\ 1.2 b_0 - 22 c_0 &= 0,\end{align*} which can be solved by $(a_0,b_0,c_0) = (12.5, \frac{5}{16}, \frac{3}{176}).$

From the choice of $(a_0,b_0,c_0)$ we have already established the base case $u_0(x_0) = u_1(x_0) = v_0 = 12.5.$ Suppose that for some $n$ we have $u_n(x_{n-1}) = u_{n-1}(x_{n-1}) = v_{n-1}.$ By construction, we have $u_n(x_n) = 1.1u_{n-1}(2x_n-5) = 1.1u_{n-1}(x_{n-1}) = v_n.$ Similarly, by construction, we have $u_{n+1}(x_n) = 1.1u_n(2x_n-5) = 1.1u_n(x_{n-1}) = v_n.$ Therefore, for each n = 0, 1, \dots, by induction we have $u_n(x_n) = u_{n+1}(x_n) = v_n,$ which proves that $u \in C(-5,5).$ Similarly, we have from the choice of $(a_0,b_0,c_0)$ already established that $u_0^\prime(x_0) = u_1^\prime(x_0).$ Assume that for some $n$ we have $u_n^\prime(x_n) = u_{n+1}^\prime(x_n).$ Since $u_{n+1}(x) = 1.1u_n(2x-5)$ we have $u^\prime_{n+1}(x) = 2.2u_n^\prime(2x-5),$ so in particular $$u^\prime_{n+1}(x_{n+1})=2.2u_n^\prime(2x_{n+1}-5) = 2.2u_n^\prime(x_n).$$ Similarly, we have $u^\prime_{n+2}(x) = 2.2u_{n+1}^\prime (2x-5),$ so in particular $$u^\prime_{n+2}(x_{n+1}) = 2.2u^\prime_{n+1}(2x_{n+1}-5) = 2.2u_{n+1}^\prime(x_n) = 2.2u_n^\prime(x_n) = u^\prime_{n+1}(x_{n+1}),$$ so we conclude that $u_n^\prime(x_n) = u_{n+1}^\prime (x_n),$ for all $n = 0, 1, 2, \dots,$ so $u \in C^1(-5,5).$ From the solution of $(a_0,b_0,c_0)$ we have $u_0^\prime(x) \geq 0$ for all $x \in (x_{-1}, x_0),$ and since $$u^\prime_{n}(x) = 2.2^n u_0(2^nx - 5(2^n-1)) \geq 0$$ for each $n = 1, 2, \dots,$ we have $u^\prime(x) \geq 0$ for all $x \in (-5,5).$ So the $C^1$ monotonic increasing quadratic spline $u$ is another $C^1$ solution to the extra credit Zeno 5K. This quadratic spline solution provides a slightly slower $C^1$ completion time of $$T = \int_0^5 \,\frac{dx}{u(x)} \approx 0.354718139\dots \,\,\text{hours}$$ or $21.28308834\dots$ minutes. Ultimately, it would appear that for any $n$ there is a $C^n$ solution comprised of a monotonically increasing $(n+1)$th order polynomial spline that satisfies the recursion formula of $v(x) = 1.1v(2x-5)$ for all $x \in (0,5).$

Zeno's Paradoxical 5K

I’ve been experimenting with different strategies in $5000$-meter races (known as “5K”s). If I run the distance at a steady pace, I’ll finish in precisely $23$ minutes. However, I tend to find a burst of energy as I near the finish line. Therefore, I’ve tried intentionally running what’s called a “negative split,” meaning I run the second half of the race faster than the first half—as opposed to a “positive split,” where I run a slower second half.

I want to take the concept of a negative split to the next level. My plan for an upcoming race—the “Zeno Paradox 5K”—is to start out with a $24$-minute pace (i.e., running at a speed such that if I ran the whole distance at that speed, I’d finish in $24$ minutes). Halfway through the race by distance (i.e., after $2500$ meters), I’ll increase my speed by $10$ percent. Three-quarters of the way through, I’ll increase by another $10$ percent. If you’re keeping track, that’s now $21$ percent faster than my speed at the start.

I continue in this fashion, upping my tempo by $10%$ every time I’m half the distance to the finish line from my previous change in pace. (Let’s put aside the fact that my speed will have surpassed the speed of light somewhere near the finish line.) Using this strategy, how long will it take me to complete the 5K? I’m really hoping it’s faster than my steady $23$-minute pace, even though I start out slower (at a $24$-minute pace).

Let the race start at $x=0$ and finish at $x=5.$ Let $x_n = 5(1 - 2^{-n})$ for $n = 0, 1, 2, \dots$ be the breakpoints where you are increasing your speed. Let $v(x)$ denote the velocity you are running (in kmph), when you are at some $x \in (0,5).$ Then $$v(x) = 12.5 \cdot 1.1^{\max \{ i : x_i \lt x \} }.$$ The time spent at the velocity $v_n = 12.5 \cdot 1.1^n$ is $$t_n = \frac{ x_{n+1}-x_n }{ v_n } = \frac{ 5 \cdot 2^{-(n+1)} }{ 12.5 \cdot 1.1^n } = \frac{2.2^{-n}}{5},$$ so the total time to complete the 5K in this fashion is $$T = \sum_{n=0}^\infty \frac{2.2^{-n}}{5} = \frac{1}{5} \frac{1}{1- \frac{1}{2.2}} = \frac{2.2}{5 \cdot 1.2} = \frac{11}{30}\,\,\text{ hours},$$ or $22$ minutes.

Monday, June 9, 2025

Overlapping bubble packing

Draw a unit circle (i.e., a circle with radius $1$). Then draw another unit circle whose center is not inside the first one. Then draw a third unit circle whose center is not inside either of the first two.

Keep doing this until you have drawn a total of seven circles. What is the minimum possible area of the region that’s inside at least one of the circles?

Let's work smarter rather than harder and first note that the if we want to pack a circle full of seven non-overlapping unit circles then the enclosing circle's radius would be $3$, with one circle concentric with the enclosing circle and the other $6$ circles arranged with their centers forming a regular hexagon, which even Wikipedia snarkily notes is "Trivially optimal". Of course, we're not here for non-overlapping circles, but let's use this same configuration. Situate a unit circle at the origin, $x_0=(0,0),$ and then $6$ unit circles centered at $x_i = ( \cos \frac{2\pi (i-1)}{6}, \sin \frac{2\pi (i-1)}{6} ),$ for $i = 1, 2, \dots, 6.$ See a Desmos illustration of the configuration below:

First we note that $\| x_i - x_j \|_2 = 1,$ for $i \ne j,$ so none of the $7$ centers of the unit circles are inside any other circle. Next we note that the bounding circle around these $7$ circles has radius $$R = \max \{ \|x\|_2 \mid \min_{i = 0, 1, \dots, 6} \{ \|x - x_i \|_2 \} \leq 1 \} = 2,$$ which is (perhaps again trivially, per Wikipedia) optimal. However, we do not want the minimal bounding radius, but rather the shaded area. Let's use inclusion / exclusion and note that there are six regions between the bounding circle of radius two and the shaded area, so once we know the area of one of these sections, say A^\prime, then the shaded area is $A = 4\pi - 6A^\prime.$ Using symmetry, we can denote the area of one of those sections as $$A^\prime = 2 \int_0^1 \left( \sqrt{4-x^2} - \left(\sqrt{1 - (x-\frac{1}{2})^2} + \frac{\sqrt{3}}{2}\right) \right) \,dx = A_1 - A_2 - \sqrt{3},$$ where $$A_1 = 2 \int_0^1 \sqrt{4 - x^2} \,dx$$ and $$A_2 = 2 \int_0^1 \sqrt{1 - (x-\frac{1}{2})^2} \,dx.$$ Using trig substitution $x = 2 \cos \theta,$ we see that \begin{align*}A_1 = 2\int_0^1 \sqrt{4-x^2} \,dx &= -8 \int_{\pi/2}^{\pi/3} \sin^2 \theta \,d\theta \\ &= 4 \int_{\pi/3}^{\pi/2} 1 - \cos 2\theta \,d\theta \\ &= \frac{2\pi}{3} + 2 \sin \pi - 2\sin \frac{2\pi}{3} = \frac{2\pi}{3} + \sqrt{3}.\end{align*} Similarly, using the trig substitution $x = \frac{1}{2} + \cos \theta,$ we see that \begin{align*}A_2 = 2 \int_0^1 \sqrt{1 - (x-\frac{1}{2})^2} \,dx &= -2 \int_{2\pi/3}^{\pi/3} \sin^2 \theta \,d\theta \\ &= \int_{\pi / 3}^{2\pi/3} 1 - \cos 2 \theta\, d\theta \\ &= \frac{\pi}{3} + \frac{1}{2}\sin \frac{2\pi}{3} - \frac{1}{2}\sin \frac{4\pi}{3} = \frac{\pi}{3} + \frac{\sqrt{3}}{2}.\end{align*}

Therefore, we have $$A^\prime = \left( \frac{2\pi}{3} + \sqrt{3} \right) - \left( \frac{\pi}{3} + \frac{\sqrt{3}}{2} \right) - \sqrt{3} = \frac{\pi}{3} - \frac{\sqrt{3}}{2},$$ so we have the minimal area of the region that's inside at least one of the circles as $$A = 4\pi - 6A^\prime = 2\pi + 3\sqrt{3} \approx 11.4793377299\dots$$

Monday, May 26, 2025

Fiddlish space frequencies

Before getting to rivers, let’s figure out where spaces are likely to appear in the (fictional) Fiddlish language, which includes only three- and four-letter words. These words are separated by spaces, but there is no other punctuation. Suppose a line of Fiddlish text is generated such that each next word has a $50$ percent chance of being three letters and a $50$ percent chance of being four letters.

Suppose a line has many, many, many words. What is the probability that any given character deep into the line is a space?

Let's suppose that we have $N \gg 1$ words in a line. Then there would be $N-1$ spaces, whereas the total length of the line would be $L = 4F + 3T + N-1$ characters, where $F$ is the number of four-letter words and $T$ is the number of three-letter words. Since $F+T = N,$ we have $$L = 4F+3(N-F) + N-1 = 4N + F - 1.$$ Since F is binomially distributed with frequency $\frac{1}{2},$ the expected value of $F$ is $\mathbb{E}[F] = \frac{N}{2},$ so the expected length is $$\mathbb{E}[L] = \frac{9}{2}N - 1.$$

Therefore, the expected frequency of spaces in the line, which is equivalent to the probability that any given character deep into the line is a space, is then $$p = \frac{N-1}{\mathbb{E}[L]} = \frac{N - 1}{\frac{9}{2}N - 1} \to \frac{2}{9} = 22.222\dots\%$$ as $N \to \infty.$

Monday, May 19, 2025

Pyramidal permeation permutations

Consider the following figure, which shows $16$ points arranged in a rhombus shape and connected to their neighbors by edges. How many distinct paths are there from the top point to the bottom along the edges such that:

  • You never visit the same point twice.
  • You only move downward or sideways—never upward.

Let's number the nodes from top down and then from left to right, so that the top node is $1$, the nodes from left to right on the second level are $2$ and $3$, and so on. Let $N(k)$ be the number of paths from $1$ ending at node $k$ following the rules of never visiting the same point twice and only moving downward or sideways, never upward. For good measure, we can go ahead and assume that $N(1) = 1.$

It is straightforward to see that $N(2) = N(3) = 2,$ since either the path goes directly from $1$ to $k \in \{2, 3\}$ or the path first travels to the other node, $5-k$, and then sideways to $k$.

Now let's consider some $k \in \{4, 5, 6\}.$ Clearly, for any such $k,$ an acceptable path must last exist the row above at some $\ell \in \{2, 3\}.$ If the path left the higher row at $\ell = 2,$ then it either first goes from $2$ to $4$ and then (if necessary) sideways from $4$ to $k$, or it goes from $2$ to $5$ and then (if necessary) sideways from $5$ to $k.$ So there must be 2N(2) paths from $1$ to $k \in \{4,5,6\}$ that leave the first row at $\ell = 2.$ A similar argument can be made that there also must be $2N(3)$ paths from $1$ to $k \in \{4,5,6\}$ that leave the first row at $\ell = 3.$ Therefore, for each $k \in \{4,5,6\}$ we must have $$N(k) = 2N(2) + 2N(3) = 8.$$

Carrying this argument further, let $\mathcal{L}_i$ represent the $i$th row of the diagram. So for instance $\mathcal{L}_0 = \{1\},$ $\mathcal{L}_1 = \{2, 3\},$ etc. Additionally, let $I(k)$ be the downward index of node $k,$ that is how many acceptable paths downward are available from node $k$. Then extending the argument from the previous paragraph, we see that $$N(k) = \sum_{j \in \mathcal{L}_{i-1}} I(j) N(j), \,\,\forall k \in \mathcal{L}_i.$$ So, as previously seen, $N(2) = N(3) = 2$ and $N(4) = N(5) = N(6) = 8.$ Furthermore, \begin{align*} N(7) = N(8) = N(9) = N(10) &= \sum_{j=4}^6 I(j) N(j) = 2N(4) + 2N(5) + 2N(6) = 6 \cdot 8 = 48 \\ N(11) = N(12) = N(13) &= \sum_{j=7}^{10} I(j) N(j) = N(7) + 2 N(8) + 2 N(9) + N(10) = 6 \cdot 24 = 288 \\ N(14) = N(15) &= \sum_{j=11}^{13} I(j) N(j) = N(11) + 2N(12) + N(13) = 4 \cdot 288 = 1152 \\ N(16) &= \sum_{j=14}^{15} I(j)N(j) = 2 \cdot 1152 = 2234,\end{align*} so the total number of acceptable paths from the top vertex of the rhombus to the bottom vertex is $2,234.$

Monday, May 12, 2025

Guess we'll still never know ...

Now that you’ve determined the values of $a$ and $b$, let’s analyze the rest of Stephen’s statement. Is it true that losing in five games is “closer to a sweep than a seven-game series”? Let $p_4$ represent the probability that the Celtics sweep the Knicks in four games. And let $p_7$ represent the probability that the series goes to seven games (with either team winning).

Suppose $p$ is randomly and uniformly selected from the interval $(a, b),$ meaning we take it as a given that the most likely outcome is that the Knicks will lose the series in five games. How likely is it that $p_4$ is greater than $p_7$? In other words, how often will it be the case that losing in five games means a sweep is more likely than a seven-game series?

As we saw earlier, for any value of $p \in \left(\frac{3}{5}, \frac{3}{4}\right),$ we have $p_4 = p^4.$ Similarly, we have $$p_7 = P(\text{C},7\mid p) + P(\text{K}, 7\mid p) = 20p^3 (1-p)^3.$$ We can solve for the point at which we have $p_4(p) = p_7(p)$ and get the cubic equation $20(1-p)^3 - p = 0,$ or substituting $t = 1-p$ we get $$t^3 + \frac{1}{20} t - \frac{1}{20} = 0.$$ Using Cardano's formula, given that the discriminant when $p = \frac{1}{20}$ and $q = -\frac{1}{20}$ is $$\Delta = \frac{q^2}{4} + \frac{p^3}{27} = \frac{1}{1600} + \frac{1}{432000} = \frac{17}{2700} \gt 0,$$ we have the solution $$t^* = \sqrt[3]{\frac{1}{40} + \frac{1}{30} \sqrt{\frac{17}{30}}} + \sqrt[3]{\frac{1}{40} - \frac{1}{30}\sqrt{\frac{17}{30}}},$$ so the equilibrium point between $p_4$ and $p_7$ occurs at $$p^* = 1 - t^* = 1 - \sqrt[3]{\frac{1}{40} + \frac{1}{30} \sqrt{\frac{17}{30}}} - \sqrt[3]{\frac{1}{40} - \frac{1}{30}\sqrt{\frac{17}{30}}} \approx 0.676582453403\dots.$$ So if $p$ were uniformly samples from $U \left( \frac{3}{5}, \frac{3}{4} \right)$ then the probability that a sweep is more probable than a seven-game series is $$\frac{p^* - \frac{3}{5}}{\frac{3}{4} - \frac{3}{5}} = \frac{20p^* - 12}{3} \approx 0.510549689351\dots.$$