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.

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.

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$$

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.$

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.$

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.$$

Guess we'll never know ...

In a recent First Take episode, co-host Stephen A. Smith said:

I got [the Knicks] losing this in five games, which means they’re closer to a sweep than a seven-game series. That’s how I’m looking at it right now.

Let’s look at the first part of Stephen’s statement, that he believed the Knicks would lose to the Celtics in five games.

Let $p$ represent the probability the Celtics win any given game in the series. You should assume that $p$ is constant (which means there’s no home-court advantage) and that games are independent.

For certain values of $p$, the likeliest outcome is indeed that the Celtics will win the series in exactly five games. While this probability is always less than $50$ percent, this outcome is more likely than the Celtics winning or losing in some other specific number of games. In particular, this range can be specified as $a \lt p \lt b.$

Determine the values of $a$ and $b$.

Let $P(t, n \mid p)$ be the probability of team $t \in \{ \text{C}, \text{K} \}$ winning the series in $n$ games, given that the probability of the Celtics winning any individual game is $p.$ Then since team $t$ would have to win the final game of the series, the probability is given by $$P(t, n \mid p) = \begin{cases}\binom{n-1}{3} p^4 (1-p)^{n-4}, &\text{if $t = \text{C}$;}\\ \binom{n-1}{3} p^{n-4}(1-p)^4, &\text{if $t = \text{K}.$}\end{cases}$$

We are trying to find the maximal interval $(a,b) \subseteq [0,1],$ such that $$P(\text{C}, 5 \mid p ) = \max_{t \in \{\text{C}, \text{K}\}, n \in \{4,5,6,7\}} P(t, n \mid p),$$ for all $p \in (a,b).$ Let's just brute force this thing: \begin{align*} P(\text{C}, 5 \mid p) = 4p^4(1-p) \gt P(\text{C}, 4 \mid p) = p^4 &\Rightarrow p \in \left(0,\frac{3}{4}\right) \\ P(\text{C}, 5 \mid p) = 4p^4(1-p) \gt P(\text{C}, 6 \mid p) = 10p^4(1-p)^2 &\Rightarrow p \in \left(\frac{3}{5},1\right) \\ P(\text{C}, 5 \mid p) = 4p^4(1-p) \gt P(\text{C}, 7 \mid p) = 20p^4(1-p)^3 &\Rightarrow p \in \left(1 - \frac{1}{\sqrt{5}},1\right), \end{align*} so since as long as $p \gt \frac{1}{2}$ we have $P(\text{C}, n \mid p) \gt P(\text{K}, n \mid p)$ for each $n \in \{4,5,6,7\},$ we see that the region where a Celtics win in five games is the most probable occurs when $p \in \left(\frac{3}{5}, \frac{3}{4}\right).$

Leeloo Disney, Multi-Pass, Extra Credit

This time around, after you complete the first ride on your Multi Pass, you can reserve a fourth ride at any time slot after your first ride (rather than after your third ride). Similarly, after you have completed your second ride, you can reserve a fifth ride at any time slot after your second, and so on, until there are no available time slots remaining.

As before, the first three rides of the day are equally likely to be in any of the 12 time slots, whereas subsequent rides are equally likely to occur in any remaining available slots for the day.

On average, how many rides can you expect to “Lightning Lane” your way through today at Magic Kingdom?

As we say in the previous Classic answer, I encoded an "extra credit" version of the Lightning Pass program, where now as opposed to only adding new rides after your last scheduled ride, you add another ride uniformly distributed over all of the remaining, not already scheduled time slots. This distribution should be, and indeed turns out to be, much more centrally distributed, though here I was unable to come up with a semi-analytical solution and will just rely on the simulations.

Here again, I used $N=1,000,000$ simulations and arrived at the following histogram, which gives a mean of $m = 6.809379,$ standard deviation of $s = 1.404456,$ which implies that the true mean $95\%$ confidence interval is $R \in [6.8066, 6.8121].$ Therefore, let's comfortably round so that under the Extra Credit Lightning Lane rules, you can expect approximately $6.81$ rides.

Leeloo Disney, Multi-Pass

By purchasing “Lightning Lane Multi Pass,” you can reserve three of the many rides in a park, with each ride occurring at a different hourlong time slot. For simplicity, suppose the park you’re visiting (let’s say it’s Magic Kingdom) has $12$ such time slots, from $9$ a.m. to $9$ p.m. So if you have the $3$ p.m. time slot for a ride, then you can skip the “standby lane” and board the much shorter “Lightning Lane” at any point between $3$ and $4$ p.m. Assume you can complete at most one ride within each hourlong time slot.

Once you have completed the first ride on your Multi Pass, you can reserve a fourth ride at any time slot after your third ride. This way, you always have at most three reservations. Similarly, after you have completed your second ride, you can reserve a fifth ride at any time slot after your fourth, and so on, up until you are assigned a ride at the $9$ p.m. time slot. That will be your final ride of the day.

Magic Kingdom happens to be very busy at the moment, and so each ride is randomly assigned a valid time slot when you request it. The first three rides of the day are equally likely to be in any of the $12$ time slots, whereas subsequent rides are equally likely to occur in any slot after your currently latest scheduled ride.

On average, how many rides can you expect to “Lightning Lane” your way through today at Magic Kingdom?

Let's denote the slots that I get as $S \subseteq \{1, 2, 3, \dots, 12 \}$. Since after each ride I take, the probability distribution of what additional slots I add to $S$ only depend on $m = \max S.$ Additionally, since we care about the total ending size of $S,$ let's keep track of $n = |S|.$

Define $R(n,m)$ to be the expected total number of rides I take given that I currently have $n$ slots and the a maximum time slot is $m$. Since once the $12$th time slot is filled, you do not end up adding any more rides, we have $R(n,12) = n$ for $n = 3, 4, \dots, 12.$ Otherwise, we have the following recursion formula $$R(n,m) = \frac{ \sum_{j=m+1}^{12} R(n+1,j)}{12 - m}, \,\,\,\ m \lt 12.$$

Using the recursion formula, we see that $$R(n,11) = R(n+1,12) = n+1, \,\,\,n = 3, 4, \dots, 11.$$ Similarly, we get $$R(n,10) = \frac{R(n + 1, 11) + R(n + 1, 12)}{2} = \frac{2n+3}{2} = n + \frac{3}{2}, \,\,\,n = 3, 4, \dots, 10.$$ Once more, we get $$R(n,9) = \frac{R(n+1,10) + R(n+1,11) + R(n+1, 12)}{3} = n + \frac{11}{6}, \,\,\, n = 3, 4, \dots, 9.$$ Another time, we get $$R(n,8) = \frac{\sum_{i=9}^{12} R(n+1,i)}{4} = n + \frac{25}{12}, \,\,\, n = 3, 4, \dots, 8.$$ Further, we get $$R(n,7) = \frac{\sum_{i=8}^{12} R(n+1,i)}{5} = n + \frac{137}{60}, \,\,\, n = 3, 4, \dots, 7.$$ Continuing onward, we get \begin{align*} R(n,6) &= n + \frac{49}{20}, \,\,\, n = 3, 4, 5, 6; \\ R(n,5) &= n + \frac{363}{140}, \,\,\, n = 3, 4, 5; \\ R(n,4) &= n + \frac{761}{280}, \,\,\, n = 3, 4; \\ R(n,3) &= n + \frac{7129}{2520}, \,\,\, n = 3.\end{align*}

Let's pause to define $p_m$ as the probability that in your first three randomly assigned timeslots, the maximum time slot is $m,$ That is, $$p_m = \frac{ \binom{m-1}{2} }{ \binom{12}{3} } = \frac{ (m-1)(m-2) }{ 440 }.$$ So using the law of total expectation, we get that the total average number of rides that you expect to go on using the Lightning Lane Multi Pass is $$R = \sum_{m=3}^{12} p_m R(3,m) = \sum_{m=3}^{12} \frac{(m-1)(m-2)}{440} R(3,m) = \frac{118361}{27720} \approx 4.2698773\dots$$

To confirm the calculations here, I put together a small Python code for testing purposes (as well as for working on the Extra Credit problem that will be featured in a later post). Below find the code:

import numpy as np
rng = np.random.default_rng()

def lightning_classic(rng):
    slots = sorted(list(rng.choice(12,size=3, replace=False)))
    last = slots[-1]
    while last < 11:
        new = rng.integers(last+1, high=12)
        slots.append(new)
        last = new
    return slots

def lightning_xc(rng):
    slots = sorted(list(rng.choice(12,size=3, replace=False)))
    for i in range(12):
        if i in slots:
            open_slots = [j for j in range(i+1, 12) if j not in slots] ## figure out which ones are still open
            if open_slots:
                new = open_slots[rng.integers(len(open_slots))] ## get new slot
                slots.append(new)
    return slots

After running the code with $N = 1,000,000,$ we get the following histogram, which gives a mean of $m = 4.269231,$ standard deviation of $s = 1.032058,$ which implies that the true mean $95\%$ confidence interval is $R \in [4.2672, 4.2713].$

More large gaps in Euclid's orchard

The fifth largest pair of adjacent gaps in this range are on either side of what angle up from the x-axis?

If use the same Python script shown earlier in the Classic answer, using the value of $k=6$ in the Python code, we get that for large enough values of $R,$ the next few largest pair of adjacent gaps occur at the following bearings, respectively: \begin{align*}\theta_2^* &= \tan^{-1} \left(\frac{1}{3} \right) \approx 18.434948823\dots^\circ \\ \theta^*_3 &= \tan^{-1} \left(\frac{2}{3}\right) \approx 33.690067526\dots^\circ \\ \theta^*_4 &= \tan^{-1} \left(\frac{1}{4}\right) \approx 14.036243468\dots^\circ.\end{align*} Through now, we still maintain that these are corresponding to the next highest peaks of Thomae's function at $x^*_2 = \frac{3}{4}, x^*_3 = \frac{3}{5}$ and $x^*_4 = \frac{4}{5},$ respectively. However, continuing one step further, we see that for sufficiently large values of $R$, the fifth largest pair of adjacent gaps occurs at $$\theta^*_5 = \tan^{-1} \left(\frac{3}{4}\right) \approx 36.869897649\dots^\circ,$$ which in fact skips over the next highest Thomae's function value of $\tilde{x} = \frac{5}{6}$ in favor of $x^*_5 = \frac{4}{7}.$ Don't feel too bad for $\tilde{x} = \frac{5}{6},$ since it is equivalent to the bearing $\theta^*_6 = \tan^{-1} \left(\frac{1}{5}\right) \approx 11.309932474\dots^\circ,$ which is in fact the bearing around which you can find the next largest adjacent pair gaps. Perhaps you could still feel bad for Thomae's function's explanatory powers, though.

Searching for large pairs of adjacent gaps in Euclid's orchard

You are at the point $(0, 0)$ on the coordinate plane. There is a tree at each point with nonnegative integer coordinates, such as $(5, 6)$, $(0, 7)$, and $(9, 1)$. The trees are very thin, so that they only obstruct trees that are directly behind them. For example, the tree at $(2, 2)$ is not visible, as it is obscured by the tree at $(1, 1).$

Now, you can’t see infinitely far in this forest. You’re not sure exactly how far you can see, but it’s pretty dang far. As you look around, you can make out very narrow angular gaps between the trees. The largest gaps are near the positive $x$-axis and the positive $y$-axis. After those, the next largest pair of gaps is on either side of the tree at $(1, 1)$, $45$ degrees up from the $x$-axis.

Consider the view between $0$ and $45$ degrees up from the $x$-axis. The next largest pair of adjacent gaps in this range are on either side of what angle up from the $x$-axis?

First, let's note that our forest is akin to what's known as Euclid's orchard, which assumes that each tree is the three dimensional line segment from $(m, n, 0)$ to $(m, n, 1)$ for $(m,n) \in \mathbb{N}^2.$ Well, it turns out that if you as an observer at $(0,0)$ are viewing this orchard along the line $y = x,$ that either the tree whose base is at $(m,n)$ is blocked by another tree if $\textsf{gcd}(m,n) \gt 1$, or the height of the tree will appear to be at height $\frac{1}{m+n}$ if $\textsf{gcd}(m,n) = 1.$ Therefore, we can associate any visible tree at $(m,n)$ with the point $x = x(m,n) = \frac{m}{m+n} \in (0,1)$ and then its height will be given by Thomae's function defined by $$T(x) = \begin{cases} \frac{1}{q}, &\text{if $x = \frac{p}{q}$ for $p \in \mathbb{Z},$ $q \in \mathbb{N}$ and $\textsf{gcd}(p,q) = 1$;}\\ 0, &\text{otherwise.}\end{cases}$$ Since we cannot actually see infinitely far into Euclid's orchard, let's assume that we can only see a tree if its base is at $(m,n) \in \mathbb{N}^2$ and $m^2 + n^2 \leq R^2$ for some $R \gg 1.$ Therefore, since $R\sqrt{2} = \max \{ x+y \mid x^2 + y^2 \leq R^2 \},$ the corresponding approximated Thomae's function is $$T_R(x) = \begin{cases} \frac{1}{q}, &\text{if $x = \frac{p}{q}$ for $p \in \mathbb{Z},$ $q \in \mathbb{N}$, $\textsf{gcd}(p,q) = 1$ and $q \leq R\sqrt{2}$;}\\ 0, &\text{otherwise.}\end{cases}.$$

Now Thomae's function is fascinating with lots of pathology (e.g., integrable, nowhere differentiable, continuous at each irrational, discountinuous at each rational, etc.). However, here we are interested in using adjacent discontinuities of the approximate Thomae's function but measuring the distances between them in some completely different way, since ultimately we are measuring the angle between the $x$-axis and the point $(m,n),$ which has much more to do with $\frac{n}{m}$ than $\frac{m}{m+n}.$ So, though I would love to have this problem yield a deep dive into Thomae's function, instead, let's just brute force throw a computer at this problem and see what comes out, since

We need to just implement the following pseudocode procedure: (1) enumerate all of the visible trees, for instance, $$\textsf{trees} = \left[ (m,n) \mid n \in \{1, \dots, R\}, m \in \{n, \dots, R \}, \textsf{gcd}(m,n) = 1, m^2 + n^2 \leq R^2 \right];$$ (2) convert each tree to its bearing (angle above the $x$-axis), that is $$ \textsf{bearings} = \left[ \textsf{arctan2(n,m)} \mid (m,n) \in \textsf{trees} \right];$$ (3) order the values of $\textsf{bearings}$ in ascending order and let $\textsf{gaps}$ be the corresponding gaps between adjacent trees; and (4) take an $\textsf{argsort}$ of $\textsf{gaps}$ to pull out the location of the largest gaps.

Below is a Python implementation of this pseudocode:

import numpy as np

def get_trees(R):
    return [ (m, n) for n in range(R) for m in range(n, R) if np.gcd(m,n) == 1 and m*m + n*n <= R*R ]

def get_tree_bearings(R):
    bearings = [ np.arctan2(n, m) for (m, n) in get_trees(R) ]
    return sorted(bearings), np.argsort(bearings)

def get_big_gap_bearings(R,k=7):
    trees = get_trees(R)
    bearings, orders = get_tree_bearings(R)
    gaps = [ x - y for x, y in zip(bearings[1:], bearings[:-1])]
    big_gaps = np.argsort(gaps)[-2*k:]
    return [(trees[orders[i]], trees[orders[i+1]]) for i in big_gaps]

For the Classic problem we notice that for $k=2$ and various values of $R = 10, 20, 50, 100, 200, 500, 1000,$ that we confirm that the largest gap always is next to the $x$-axis, followed by the gap nearest to the tree at $(1,1),$ then the next largest pair of adjacent gaps is on either side of the tree at $(2,1),$ that is, with bearing $$\theta^* = \tan^{-1} \left(\frac{1}{2}\right) \approx 26.565051177\dots^\circ.$$ This interestingly, though still mysteriously since I'm not totally sold on the ability to directly infer much of anything from Thomae's function, is equivalent to the second tallest peak of Thomae's function at $x^* = 2/3.$

Extra credit hammer throwing

Instead of playing to $3$ points, now the first player to $5$ points wins the match.

Good news (again)! You have won the first hole, and now lead $1-0.$ What is your probability of winning the match?

This game will have the same recurrence relationship, but the initial conditions will be $$\tilde{w}(s_1, s_2) = \begin{cases} 1, &\text{if $s_1 \geq 5 \gt s_2;$}\\ 0, &\text{if $s_1 \lt 5 \leq s_2.$}\end{cases}$$ Since $\tilde{w}(s_1,s_2) = w(s_1-2,s_2-2),$ we automatically have $\tilde{w}(4,4) = \tilde{w}(4,3) = \tilde{w}(3,4) = \tilde{w}(3,3) = \frac{1}{2}$ along with $\tilde{w}(4,2) = \tilde{w}(3,2) = \frac{3}{4}$ and $\tilde{w}(2,3) = \tilde{w}(2,4) = \frac{1}{4}.$ We also have $\tilde{w}(4,1) = \tilde{w}(3,1) = \frac{3}{4},$ $\tilde{w}(1,4) = \tilde{w}(1,3) = \frac{1}{4},$ $\tilde{w}(4,0) = \tilde{w}(3,0) = \frac{7}{8},$ $\tilde{w}(1,1) = \tilde{w}(2,2) = \tilde{w}(1,2) = \tilde{w}(2,1) = \frac{1}{2},$ and $\tilde{w}(2,0) = \frac{11}{16}.$

Finally, we arrive at the probability of winning the match to $5$ points if you each are playing optimally as \begin{align*} \tilde{w}(1,0) &= \max_u \min_v \left[ uv \frac{\frac{7}{8} + \frac{1}{2}}{2} + (1-u)(1-v) \frac{\frac{11}{16} + \frac{1}{2}}{2} \right. \\ &\quad\quad\quad\quad\quad\left. + u(1-v) \min \left\{ \frac{\frac{7}{8} + \frac{1}{2}}{2}, \frac{11}{16} \right\} + (1-u)v \max \left\{\frac{\frac{11}{16} + \frac{1}{2}}{2}, \frac{11}{16} \right\} \right] \\ &= \max_u \min_v \left[ \frac{11}{16} uv + \frac{19}{32} (1-u)(1-v) + \frac{11}{16} u(1-v) + \frac{11}{16} (1-u)v \right] \\ &= \max_u \min_v \left[ \frac{19}{32} + \frac{3}{32} u + \frac{3}{32} v - \frac{3}{32} uv \right] = \frac{11}{16},\end{align*} with optimizers $u^* = 1,$ $v^* = 0.$

Isn't hammer throw was a field sport?

You and your opponent are competing in a golf match. On any given hole you play, each of you has a $50$ percent chance of winning the hole (and a zero percent chance of tying). That said, scorekeeping in this match is a little different from the norm.

Each hole is worth $1$ point. Before starting each hole, either you or your opponent can “throw the hammer.” When the hammer has been thrown, whoever did not throw the hammer must either accept the hammer or reject it. If they accept the hammer, the hole is worth $2$ points. If they reject the hammer, they concede the hole and its $1$ point to their opponent. Both players can throw the hammer on as many holes as they wish. (Should both players decide to throw the hammer at the exact same time—something that can’t be planned in advance—the hole is worth $2$ points.)

The first player to reach $3$ points wins the match. Suppose all players always make rational decisions to maximize their own chances of winning.

Good news! You have won the first hole, and now lead $1-0$. What is your probability of winning the match?

Let's define your win probability as the function $w : \mathbb{N}^2 \to [0,1],$ so that $w(s_1, s_2)$ is the probability of winning the match given that the current score is $s_1$ points for you and $s_2$ points for your opponent, assuming that you are both playing perfectly rationally, maximizing you own chances of winning. Let $u$ be the indicator of whether or not you throw the hammer when the score is $(s_1, s_2).$ Let $v$ be the indicator of whether or not your opponent throws the hammer when the score is $(s_1,s_2).$ Then we can define the recursion formula \begin{align*} w(s_1,s_2) &= \max_{u \in \{0,1\}} \min_{v \in \{0,1\}} \left[uv \frac{ w(s_1+2, s_2) + w(s_1, s_2 + 2) }{2} \right. \\ &\quad\quad\quad + (1-u)(1-v) \frac{ w(s_1 + 1,s_2) + w(s_1, s_2 + 1)}{2} \\ &\quad\quad\quad\quad + u(1-v) \min \left\{ \frac{w(s_1+2, s_2) + w(s_1, s_2 + 2)}{2}, w(s_1+1,s_2) \right\} \\ &\quad\quad\quad\quad\quad \left.+(1-u)v \max \left\{ \frac{w(s_1+2, s_2) + w(s_1, s_2+2)}{2}, w(s_1, s_2+1) \right\} \right],\end{align*} where the coefficients of $u(1-v)$ and $(1-u)v,$ represent the optimal choice of whether or not to accept or reject the hammer, by your opponent and you, respectively. As boundary conditions, we have $$w(s_1,s_2) = \begin{cases} 1, &\text{if $s_1 \geq 3 \gt s_2$;}\\ 0, &\text{if $s_1 \lt 3 \leq s_2.$}\end{cases}$$

In particular, we see that for instance \begin{align*}w(2,2) &= \max_u \min_v \left[ uv \frac{ 1 + 0}{2} + (1-u)(1-v) \frac{1 + 0}{2} + u(1-v) \min \left\{ \frac{1+0}{2}, 1 \right\} + (1-u)v \max \left\{ \frac{1+0}{2}, 0 \right\}\right] \\ &= \max_u \min_v \frac{1}{2} = \frac{1}{2}.\end{align*} We also find that \begin{align*}w(1,2) &= \max_u \min_v \left[ uv \frac{1+0}{2} + (1-u)(1-v) \frac{\frac{1}{2} + 0}{2} + u(1-v) \min \left\{ \frac{1+0}{2}, \frac{1}{2} \right\} + (1-u)v \max \left\{ \frac{1+0}{2}, 0 \right\} \right] \\ &= \max_u \min_v \left[\frac{1}{4} + \frac{1}{4}u + \frac{1}{4}v - \frac{1}{4}uv\right] = \frac{1}{2},\end{align*} with optimizers $u^*=1$ and $v^*=0.$ Similarly, $w(2,1) = \frac{1}{2},$ as well.

Working our way backward we see that $w(2,0) = \frac{3}{4}$, $w(1,1) = \frac{1}{2}$ and $w(0,2) = \frac{1}{4}.$ Therefore, we can finally arrive at the probability of winning given that you and your opponent play optimally and that the current score is $1-0$ is \begin{align*}w(1,0) &= \max_u \min_v \left[ uv \frac{1 + \frac{1}{2}}{2} + (1-u)(1-v) \frac{\frac{3}{4} + \frac{1}{2}}{2} + u(1-v) \min \left\{ \frac{1+\frac{1}{2}}{2}, \frac{3}{4} \right\} + (1-u) v \max \left\{ \frac{1 + \frac{1}{2}}{2}, \frac{1}{2} \right\} \right] \\ &= \max_u \min_v \left[ \frac{5}{8} + \frac{1}{8} u + \frac{1}{8} v - \frac{1}{8} uv \right] = \frac{3}{4},\end{align*} with optimizers $u^*=1$ and $v^*=0.$

Paying attention to the hints

Dean has three colors of the hibiscus: red, orange, and yellow. He wants to plant them in a straight hedge of shrubs (each of which is one color) so that the order appears somewhat random, but not truly random. More specifically, he wants the following to be true:

• No two adjacent shrubs have the same color.
• No ordering of three consecutive shrubs appears more than once in the hedge.

What is the greatest number of shrubs Dean’s hedge can contain?

I should have picked up on the otherwise extraneous information regarding Rivka Lipkovitz's interest in the base-$7$ Doomsday algorithm to divine that my Ore's theorem base upper bound was not exactly the sharpest bound in the shed. Well, you can't fool me again! I know that since I did indeed like the previous week's Fiddler involved Hamiltonian cycles, that somehow this one will too ....

So let's design Dean's hedge instructions as a directional graph. Let $O$ denotes an orange hibiscus, $R$ a red one, and $Y$ a yellow one. Then a triplet $v = (v_1,v_2,v_3)$ with $v_i \in \{O,R,Y\}$ with $v_2 \ne v_1$ and $v_3 \ne v_2$ is one of the possible orderings of three consecutive shrubs that satisfies both of the conditions. Let $$V = \{ ORO, ORY, OYO, OYR, ROR, ROY, RYO, RYR, YOR, YOY, YRO, YRY \}$$ be the set of vertices. We can draw a directional edge between $v_1$ and $v_2$ if the first two characters of $v_2$ are the last two characters of $v_1,$ so for instance, there is an edge from $RYR$ to $YRO$ but not one that starts at $YRO$ and ends at $RYR.$ Thus all possible edges are $$E = \{ (v_1, v_2) \mid v_{12} = v_{21}, v_{13} = v_{22} \}.$$

Sure enough, there is a Hamiltonian cycle on the graph $G = (V,E)$ covering all $12$ possible vertices, which gives a maximal Dean-approved hibiscus hedge length of 14 shurbs (count the first three shrubs of the initial vertex, then each subsequent vertex only adds one new shrub so $3 + 11 = 14$). One possible instance of this Hamiltonian cylce is given by \begin{align*} ORO \to ROY \to OYO &\to YOR \to ORY \to RYO \to YOY\\ &\to OYR \to YRY \to RYR \to YRO \to ROR \to ORO,\end{align*} which when put altogether gives a hedge denoted as $OROYORYOYRYROR.$

Striking Ore while digging into Lipkovitz's Hamiltonian puzzle

A teacher is handing out candy to his students. He abides by the following rules:

• He hands out candy to groups of three students (i.e., “trios”) at a time. Each member of the trio gets one piece of candy.
• Each unique trio can ask for candy, but that same trio can’t come back for seconds. If students in the trio want more candy, they must return as part of a different trio.
• When a trio gets candy, the next trio can’t contain any students from that previous trio.

It turns out that every possible trio can get a helping of candy together. What is the smallest class size for which this is possible?

Obviously, I assume that we are not talking about the trivial case of $N=3$ students, because, ... lame!

So let's assume that there are $N \gt 3$ students. Then there will be $$M = \binom{N}{3} = \frac{1}{6}N(N-1)(N-2)$$ possible trios in the class. Let's assume that the set $V = \{ v_1, v_2, \dots, v_M \}$ enumerates all such trios. Based on the teacher's final condition, we can see that if $v_i$ and $v_j$ share a common student, then $v_j$ cannot be the next trio to ask if $v_i$ has just received candy. Let's define a set of edges on the vertex set $$E = \{ (v_i, v_j) \in V \times V \mid j \gt i, v_i \cap v_j = \emptyset \},$$ that is, if the trio $v_i$ could immediately follow the trio $v_j$ (or vice versa), then there is an edge between $v_i$ and $v_j.$ We will call vertices $v_i$ and $v_j$ adjacent if there is an edge $e \in E$ connecting $v_i$ and $v_j.$ Let's define the graph $\mathcal{G} = (V, E).$ Note that we define the degree of a vertex, denoted $\delta(v)$, to be the number of vertices $w \in V$ that are adjacent to $v,$ that is, $$\delta(v) = \# \{ w \in V \mid e = (v,w) \in E \}.$$

Since it turns out that every possible trio can get a helping of candy together, but based on the second condition each trio can only ask for candy once, then there must be some path that on $\mathcal{G}$ that visits each vertex exactly once. This type of path is known in graph theory as a Hamiltonian path. A graph is called Hamiltonian if it admits a Hamiltonian path starts and ends at adjacent vertices. The Norwegian graph theorist Øystein Ore provided the following sufficient condition for a graph to Hamiltonian based on the degrees of its vertices:

Ore's Theorem: A graph $\mathcal{G} = (V, E)$ with $|V| = n$ is Hamiltonian if for every pair of non-adjacent vertices $v, w \in V,$ $$\delta(v) + \delta(w) \geq n.$$

Let's note that for our graph $\mathcal{G}_N$, since any vertex $v$ is adjacent to any other trio made up of distinct students, we have $$\delta(v) = \binom{N-3}{3} = \frac{1}{6} (N-3)(N-4)(N-5) = \frac{N^3 -12N^2 + 47N - 60}{6}.$$ So from an application of Ore's theorem, whenever $$M = \frac{N^3-3N^2+2N}{6} \leq 2 \frac{N^3 -12N^2 +47N - 60}{6}$$ or equivalently, whenever $$N^3 - 21N^2 +92N -120 \geq 0,$$ then $\mathcal{G}$ is Hamiltonian. Since the real root of the polynomial $p(t) = t^3 -21t^2 +92t -120$ is at $t^* \approx 15.59....$ we have that whenever $N \geq 16,$ then every possible trio can have a helping of candy together.

Boosting busts more seeds in bigger tourneys

Instead of four teams, now there are $2^6$, or $64,$ seeded from $1$ through $64$. The power index of each team is equal to $65$ minus that team’s seed.

The teams play in a traditional seeded tournament format. That is, in the first round, the sum of opponents’ seeds is $2^6+1,$ or $65.$ If the stronger team always advances, then the sum of opponents’ seeds in the second round is $2^5+1$, or $33$, and so on.

Once again, the underdog in every match gets a power index boost $B$, where $B$ is some positive non-integer. Depending on the value of $B,$ different teams will win the tournament. Of the $64$ teams, how many can never win, regardless of the value of $B$?

After setting up the $64$ team bracket, we can choose various values for $B$ and then compute the winners directly. Since the outcome will remain the same for all non-integer values in $(\lfloor B \rfloor, \lceil B \rceil)$, we need only select a total of $64$ values, e.g., $b+0.5,$ for $b = 0, 1, \dots, 63.$ The summary of the outcomes of the $64$ team tournament bracket are in the table below. We note that there are $27$ seeds (namely, $7$, $13$-$15$, and $25$-$47$) who never win the tournament. Most unlucky out of each of them are $7$, $15$ and $47$, each of which have sets of $B$ of measure $3$ for which they will end up the runner up of the tournament, though they will never win it.

$B$	Winning Seed	Runner Up
(0,1)	1	2
(1,2)	1	3
(2,3)	3	1
(3,4)	2	1
(4,5)	6	5
(5,6)	5	3
(6,7)	5	3
(7,8)	4	3
(8,9)	12	11
(9,10)	11	9
(10,11)	11	9
(11,12)	10	9
(12,13)	10	9
(13,14)	9	7
(14,15)	9	7
(15,16)	8	7
(16,17)	24	23
(17,18)	23	21
(18,19)	23	21
(19,20)	22	21
(20,21)	22	21
(21,22)	21	19
(22,23)	21	19
(23,24)	20	19
(24,25)	20	19
(25,26)	19	17
(26,27)	19	17
(27,28)	18	17
(28,29)	18	17
(29,30)	17	15
(30,31)	17	15
(31,32)	16	15
(32,33)	48	47
(33,34)	49	47
(34,35)	49	47
(35,36)	50	49
(36,37)	50	49
(37,38)	51	49
(38,39)	51	49
(39,40)	52	51
(40,41)	52	51
(41,42)	53	51
(42,43)	53	51
(43,44)	54	53
(44,45)	54	53
(45,46)	55	53
(46,47)	55	53
(47,48)	56	55
(48,49)	56	55
(49,50)	57	55
(50,51)	57	55
(51,52)	58	57
(52,53)	58	57
(53,54)	59	57
(54,55)	59	57
(55,56)	60	59
(56,57)	60	59
(57,58)	61	59
(58,59)	61	59
(59,60)	62	61
(60,61)	62	61
(61,62)	63	61
(62,63)	63	61
$\gt 63$	64	63

Boosting will cause the $2$ seed to always bust

Once again, there are four teams remaining in a bracket: the $1$-seed, the $2$-seed, the $3$-seed, and the $4$-seed. In the first round, the $1$-seed faces the $4$-seed, while the $2$-seed faces the $3$-seed. The winners of these two matches then face each other in the regional final.

Also, each team possesses a “power index” equal to $5$ minus that team’s seed. In other words:

• The $1$-seed has a power index of $4.$
• The $2$-seed has a power index of $3.$
• The $3$-seed has a power index of $2.$
• The $4$-seed has a power index of $1.$

In any given matchup, the team with the greater power index would emerge victorious. However, March Madness fans love to root for the underdog. As a result, the team with the lower power index gets an effective “boost” $B,$ where $B$ is some positive non-integer. For example, $B$ could be $0.5$, $133.7,$ or $2\pi,$ but not $1$ or $42.$

As an illustration, consider the matchup between the $2$- and $3$-seeds. The favored $2$-seed has a power index of $3,$ while the underdog $3$-seed has a power index of $2+B.$ When $B$ is greater than $1,$ the $3$-seed will defeat the $2$-seed in an upset.

Depending on the value of $B$, different teams will win the tournament. Of the four teams, how many can never win, regardless of the value of $B$?

As shown in the prompt, if $B \lt 1$ then $2$ will beat $3$ in the first round. On the other side of the bracket, $1$ will beat $4,$ since $4 \gt B+1$ in this case, so in the final round we have $1$ beating $2$ since again $4 \gt 3 + B$ when $B \lt 1.$ So, since whenever $B \lt 1,$ $1$ will win the championship. On the other hand, whenever $B \gt 1$, $2$ will lose to $3$ in the first round. Therefore, $2$ will never win the championship.

Whenever $B \in (2,3),$ $3$ will beat $1$ for the championship, since $2 + B \gt 4.$ Whenver $B \gt 3,$ $4$ will beat $1$ in the first round and then go on to beat $3$ for the championship. Thus, there are values of $B$ for which $1$, $3$ and $4$ will win the championship. So out of the four remaining teams, only one of them (the $2$ seed) will never win.

An Extra Credit $\pi$ day $\pi$-cnic in $\pi$-land

Suppose the island of $\pi$-land, as described above, has a radius of $1$ mile. That is, Diametric Beach has a length of $2$ miles. Again, you are picking a random point on the island for a picnic. On average, what will be the expected shortest distance to shore?

Here we want to calculate the average, minimum distance to shore $$E = \frac{1}{A} \int_{-R}^R \int_0^{\sqrt{R^2 - x^2}} \min \{ d_D (x,y), d_S (x,y) \} \,dy \,dx,$$ where $d_D$ and $d_S$ were defined as above in the Classic Fiddler answer. As we saw in the Classic Fiddler answer, the region where $d_D \leq d_S$ is given by $\Omega,$ so we can break the integral above into two sections $$E = \frac{1}{A} \int_{-R}^R \int_0^{\frac{R^2 - x^2}{2R}} y \,dy\,dx + \frac{1}{A} \int_{-R}^R \int_{\frac{R^2-x^2}{2R}}^{\sqrt{R^2 - x^2}} \left(R - \sqrt{x^2+y^2}\right) \,dy \,dx := E_1 + E_2.$$ The first integral, $E_1,$ is relatively straightforward to do, \begin{align*}E_1 = \frac{1}{A} \int_{-R}^R \int_0^{\frac{R^2 - x^2}{2R}} y \, dy \,dx &= \frac{4}{\pi R^2} \int_0^R \left( \frac{y^2}{2} \right)_{y=0}^{y= \frac{R^2 - x^2}{2R}} \,dx\\ &= \frac{4}{\pi R^2} \int_0^R \frac{1}{2} \left( \frac{R^2 - x^2 }{2R} \right)^2 \,dx \\ &= \frac{4}{\pi R^2} \int_0^R \frac{1}{8R^2} \left( x^4 - 2R^2 x^2 + R^4 \right) \,dx \\ &= \frac{1}{2\pi R^4} \left[ \frac{x^5}{5} - \frac{2R^2x^3}{3} + R^4 x \right]_{x=0}^{x=R} \\ &= \frac{1}{2\pi R^4} \left( \frac{R^5}{5} - \frac{2R^5}{3} + R^5 \right) \\ &= \frac{R}{2\pi} \left( \frac{1}{5} - \frac{2}{3} + 1 \right) \\ &= \frac{R}{2\pi} \frac{3 - 10 + 15}{15} = \frac{4R}{15 \pi} \end{align*}

For the second integral, it will be easier to switch to polar coordinates, then do some trig-substitutions to get a handle on the resulting integral. The curve $y = \frac{R^2 - x^2}{2R}$ is equivalent to the equation $x^2 + 2R y - R^2 = 0$ which is given by $r^2 \cos^2 \theta + 2R r \sin \theta - R^2 = 0$ in polar coordinates. Solving the quadratic in terms of $r$ and choosing the positive solution when $\sin \theta \geq 0$ since $\theta \in [0,\pi]$, we get \begin{align*}r &= \frac{ -2R \sin \theta + \sqrt{ 4R^2 \sin^2 \theta + 4R^2 \cos^2 \theta} }{2 \cos^2 \theta} \\ &= \frac{-2R \sin \theta + 2R}{2 \cos^2 \theta} \\ &= \frac{ R \left( 1 - \sin \theta \right) }{ \cos^2 \theta } \\ &= \frac{R}{1 + \sin \theta},\end{align*} since $\cos^2 \theta = 1 - \sin^2 \theta = (1 - \sin \theta) (1 + \sin \theta).$ Therefore, we have \begin{align*}E_2 &= \frac{1}{A} \int_{-R}^R \int_{\frac{R^2 - x^2}{2R}}^{\sqrt{R^2 - x^2}} \left( R - \sqrt{x^2 + y^2} \right) \,dy \,dx \\ &= \frac{2}{\pi R^2} \int_0^\pi \int_{\frac{R}{1 + \sin \theta}}^R (R - r) r \,dr \, d\theta \\ &= \frac{2}{\pi R^2} \int_0^\pi \left[ \frac{Rr^2}{2} - \frac{r^3}{3} \right]^{r=R}_{r = \frac{R}{1 + \sin \theta}} \, d\theta \\ &= \frac{2}{\pi R^2} \int_0^\pi \left( \frac{R^3}{2} - \frac{R^3}{3} \right) - \left( \frac{R^3}{2(1 + \sin \theta)^2} - \frac{R^3}{3(1 + \sin \theta)^3} \right) \,d\theta \\ &= \frac{R}{3} - \frac{R}{3\pi} \int_0^\pi \frac{3 \sin \theta + 1}{(1 + \sin \theta)^3} \,d\theta = \frac{R}{3} - I.\end{align*} In order to calculate the last integral $I$, we need to do a trigonometric half-angle substitution with $u = \tan \frac{\theta}{2}.$ Here we see that $$du = \frac{1}{2} \sec^2 \frac{\theta}{2} \,d\theta = \frac{1}{2} \left(1 + \tan^2 \frac{\theta}{2} \right) \,d\theta = \frac{1 + u^2}{2} \,d\theta$$ and further that $$\sin \theta = 2 \sin \frac{\theta}{2} \cos \frac{\theta}{2} = 2 \tan \frac{\theta}{2} \cos^2 \frac{\theta}{2} = \frac{2 \tan \frac{\theta}{2}}{1 + \tan^2 \frac{\theta}{2}} = \frac{2u}{1+u^2}.$$ We additionally see that when $\theta = 0,$ then $u = 0,$ whereas when $\theta = \pi,$ then $u = \tan \frac{\pi}{2} = \infty.$ Therefore we get \begin{align*} I &= \frac{R}{3\pi} \int_0^\pi \frac{3 \sin \theta + 1}{(1 + \sin \theta)^3} \,d\theta \\ &= \frac{2R}{3\pi} \int_0^\infty \frac{ 3 \frac{2u}{1+u^2} + 1 }{\left(1 + \frac{2u}{1 + u^2}\right)^3} \frac{2 \,du}{1 + u^2} \\ &= \frac{2R}{3\pi} \int_0^\infty \frac{ (1 + 6u + u^2) ( 1 + u^2 ) }{ (1 + u)^6 } \, du.\end{align*} Making a further substitution of $v = 1 + u,$ we then get \begin{align*} I = \frac{R}{3\pi} \int_0^\infty \frac{ (1 + 6u + u^2) ( 1 + u^2 ) }{ (1 + u)^6 } \, du &= \frac{2R}{3\pi} \int_1^\infty \frac{ (1 + 6(v-1) + (v-1)^2) ( 1 + (v-1)^2 ) }{v^6} \, dv \\ &= \frac{2R}{3\pi} \int_1^\infty \frac{ (v^2 + 4v - 4)(v^2 - 2v + 2) }{v^6} \,dv \\ &= \frac{2R}{3\pi} \int_1^\infty v^{-2} + 2v^{-3} - 10v^{-4} + 16v^{-5} -8v^{-6} \,dv \\ &= \frac{2R}{3\pi} \left[ -\frac{1}{v} -\frac{1}{v^2} + \frac{10}{3v^3} -\frac{4}{v^4} + \frac{8}{5v^5} \right]_{v=1}^{v=\infty} \\ &= -\frac{2R}{3\pi} \left( -1 -1 + \frac{10}{3} -4 + \frac{8}{5} \right) = \frac{32R}{45\pi} \end{align*} Putting this altogether we get $$E_2 = \frac{R}{3} - \frac{32R}{45\pi} = \frac{R(15\pi - 32)}{45 \pi}.$$

Therefore, the average minimal distance to the beach on $\pi$-land if the picnic spot is uniformly randomly chosen over the area of $\pi$-land is $$E = E_1 + E_2 = \frac{4R}{15\pi} + \frac{R(15 \pi - 32)}{45 \pi} = \frac{R(15\pi -20)}{45 \pi} = \frac{R(3\pi - 4)}{9\pi}.$$ So in particular, if $R = 1,$ then we get an average distance to the beach of $$E = \frac{3 \pi - 4}{9\pi} \approx 0.191862272807\dots.$$

A $\pi$ day $\pi$cnic on $\pi$-land

You are planning a picnic on the remote tropical island of $\pi$-land. The island’s shape is a perfect semi-disk with two beaches, as illustrated below: Semicircular Beach (along the northern semicircular edge of the disk) and Diametric Beach (along the southern diameter of the disk).

If you pick a random spot on $\pi$-land for your picnic, what is the probability that it will be closer to Diametric Beach than to Semicircular Beach? (Unlike the illustrative diagram above, assume the beaches have zero width.)

The local $\pi$-landers typically measure everything from the midpoint of the Diametric Beach, so let's assume that point is the origin of our $xy$-plane, with Diametric Beach coinciding with the $x$-axis. In this case, assuming that $\pi$-land has a radius of $R,$ then the entire area of $\pi$-land is $A = \frac{1}{2} \pi R^2.$ At any point $(x,y)$ on the $\pi$-land the distance to the Diametric Beach is given by $d_D (x,y) = y,$ while the distance to the Semicircular Beach is $d_S (x,y) = R - \sqrt{x^2 + y^2}.$ So the region of $\pi$-land that is closer to Diametric Beach than to Semicircular Beach is given by \begin{align*} \Omega &= \left\{ (x,y) \in \mathbb{R}^2_+ \mid x^2 + y^2 \leq R^2, d_D(x,y) \leq d_S(x,y) \right\} \\ &= \left\{ (x,y) \in \mathbb{R}_+^2 \mid y \leq R - \sqrt{x^2+ y^2} \right\} \\ &= \left\{ (x,y) \in \mathbb{R}^2_+ \mid x^2 + y^2 \leq (R-y)^2 \right\} \\ &= \left\{ (x,y) \in \mathbb{R}^2_+ \mid x^2 \leq R^2 -2Ry \right\} \\ &= \left\{ (x,y) \in \mathbb{R}^2_+ \mid y \leq \frac{R^2 - x^2}{2R} \right\} \end{align*}

The area of $\Omega$ is given by the integral $$A_\Omega = \int_{-R}^R \frac{R^2 - x^2}{2R} \,dx = 2 \left[ \frac{Rx}{2} - \frac{x^3}{6R} \right]^{x=R}_{x=0} = 2 \left( \frac{R^2}{2} - \frac{R^2}{6} \right) = \frac{2R^2}{3}.$$ Therefore, the probability of randomly choosing a $\pi$-land picnic spot closer to Diametric Beach than to Semicircular Beach, that is, in $\Omega,$ is given by $$p = \frac{A_\Omega}{A} = \frac{ \frac{2R^2}{3} }{ \frac{\pi R^2}{2} } = \frac{4}{3\pi} \approx 0.424413181578....$$

Well below average domino placement

You are placing many, many dominoes in a straight line, one at a time. However, each time you place a domino, there is a $1$ percent chance that you accidentally tip it over, causing a chain reaction that tips over all dominoes you’ve placed. After a chain reaction, you start over again.

If you do this many, many times, what can you expect the median (note: not the average) number of dominoes placed when a chain reaction occurs (including the domino that causes the chain reaction)?

Let's abstract to using a generic probability of accidentally tipping all of the dominoes over at $p\gt 0.$ Let $D_p$ be the random number representing the total number of dominoes (including the domino that you originally tip over) when the probability of accidentally tipping the dominoes over for any individual domino is $p \gt 0$, then we have $$\mathbb{P} \left[ D_p = d \right] = p (1-p)^{d-1},$$ since in order for you to tip over the $d$th domino you must first not have knocked over the first $(d-1)$ dominoes, each with a probability of $(1-p),$ and then knock over the $d$th domino, with probability $p.$

So for any $d \gt 0,$ the probability of $D \leq d$ is equal to $$\mathbb{P} \left[ D_p \leq d \right] = \sum_{m=1}^{d} \mathbb{P} \left[ D_p = m \right] = \sum_{m=1}^d p(1-p)^{m-1} = p \cdot \frac{1 - (1-p)^d}{1-(1-p)} = 1 - (1-p)^d.$$ Alternatively, we have $$\mathbb{P} \left[ D_p \gt d \right] = 1 - \mathbb{P} \left[ D_p \leq d \right] = (1-p)^d.$$ The integer $M_p$ is the median of the distribution of $D_p$ if and only if we have $$\mathbb{P} \left[ D_p \leq M_p \right] = 1 - (1 - p)^{M_p} \geq \frac{1}{2}$$ and $$\mathbb{P} \left[ D_p \geq M_p \right] = \mathbb{P} \left[ D_p \gt M_p \right] + \mathbb{P} \left[ D_p = M_p \right] = (1-p)^{M_p-1} \geq \frac{1}{2}.$$ Therefore, combining these two equations we need $$(1-p)^{M_p} \leq \frac{1}{2} \lt (1-p)^{M_p - 1}.$$ Taking natural logarithms of all sides we get $$M_p \ln (1-p) \leq -\ln 2 \lt (M_p - 1) \ln(1-p),$$ or equivalently $$M_p - 1 \lt -\frac{\ln 2}{\ln (1-p)} \leq M_p,$$ or equivalently $$M_p = \Big\lceil -\frac{\ln 2}{\ln (1-p)} \Big\rceil.$$

Therefore, if $p = 0.01,$ then we get $$M_{0.01} = \Big\lceil -\frac{\ln 2}{0.99} \Big\rceil = \lceil 68.9675639365\dots \rceil = 69$$ is the median number of dominoes that you will have placed when they all get knocked down. For further confirmation we see we get $$\mathbb{P} \left[ D_p \leq 68 \right] = 0.495114111213 \lt \frac{1}{2} \lt \mathbb{P} \left[ D_p \leq 69 \right] = 0.500162970101.$$

Though the note said to explicitly ignore the expectation, we see that \begin{align*}E_p = \mathbb{E} \left[ D_p \right] &= \sum_{m=1}^\infty m \mathbb{P} \left[ D_p = m \right]\\ &= \sum_{m=1}^\infty m p (1-p)^{m-1} \\ &= p \sum_{m=1}^\infty m (1-p)^{m-1} \\ &= p \left[ \frac{d}{dt} \left( \frac{1}{1-t} \right) \right|_{t=1-p} \\ &= p \left[ \frac{1}{(1-t)^2} \right|_{t = 1-p} \\ &= p \frac{1}{(1 - (1-p))^2} = p \frac{1}{p^2} = \frac{1}{p}.\end{align*} In particular, we see that for the Classic question, we have $E_{0.01} = 100 \gt M_{0.01} = 69.$

The Extra Credit question looks at the limit of $M_p / E_p = p M_p$ as $p \downarrow 0.$ Given the formulae above, we see that the limit of the ratio of the median to the average number of dominos placed is given by $$\lim_{p \to 0} p M_p = \lim_{p \to 0} p \cdot - \frac{\ln 2}{\ln ( 1- p) } = \lim_{p \to 0} \frac{ p\ln 2}{ - \ln (1-p) } = \lim_{p \to 0} \frac{ \ln 2 }{1 - p} = \ln 2,$$ where the first equal sign comes from the squeeze theorem and the second to last equal sign is an application of L'Hôpital's Rule. So not only do we have $M_p \lt E_p$ in the case of $p = 0.01,$ but for all small $p \approx 0.$

Magical Rabbit Pulling

I have a hat with six small toy rabbits: two are orange, two are green, and two purple. I shuffle the rabbits around and randomly draw them out one at a time without replacement (i.e., once I draw a rabbit out, I never put it back in again).

Your job is to guess the color of each rabbit I draw out. For each guess, you know the history of the rabbits I’ve already drawn. So if we’re down to the final rabbit in the hat, you should be able to predict its color with certainty.

Every time you correctly predict the color of the rabbit I draw, you earn a point. If you play optimally (i.e., to maximize how many points you get), how many points can you expect to earn on average?

Let's define the Markov chain on $\mathbb{N}^4$ with states $X = (g, o, p, s),$ where $g$ is the number of green rabbits, $o$ is the number orange rabbits, $p$ is the number of purple rabbits and $s$ is the current score. The state $X = (g, o, p, s)$ in this magical rabbit pulling Markov chain is adjacent to the following states: $(g-1, o, p, s)$, $(g-1, o, p, s+1)$, $(g, o-1, p, s)$, $(g, o-1, p, s+1)$, $(g, o, p-1, s)$ and $(g,o, p-1, s+1),$ provided that the resulting quadruple remains in $\mathbb{N}^4.$ The transition probabilities are given by the following: \begin{align*} p( X^{n+1} = (g-1,o,p,s) \mid X^n = (g,o,p,s) ) &= \begin{cases} \frac{g}{g+o+p} \left( 1 - \frac{1}{\arg\max \{g, o, p\}} \right), & \text{if $g = \max \{ g, o, p \};$}\\ \frac{g}{g+o+p}, &\text{if $g \lt \max \{ g, o, p \}$}\end{cases}\\ p( X^{n+1} = (g-1,o,p,s+1) \mid X^n = (g,o,p,s) ) &= \begin{cases} \frac{g}{g+o+p} \frac{1}{\arg\max \{g, o, p\}}, & \text{if $g = \max \{ g, o, p \};$}\\ 0, &\text{if $g \lt \max \{ g, o, p \}$}\end{cases} \\ p( X^{n+1} = (g,o-1,p,s) \mid X^n = (g,o,p,s) ) &= \begin{cases} \frac{o}{g+o+p} \left( 1 - \frac{1}{\arg\max \{g, o, p\}} \right), & \text{if $o = \max \{ g, o, p \};$}\\ \frac{g}{g+o+p}, &\text{if $o \lt \max \{ g, o, p \}$}\end{cases}\\ p( X^{n+1} = (g,o-1,p,s+1) \mid X^n = (g,o,p,s) ) &= \begin{cases} \frac{o}{g+o+p} \frac{1}{\arg\max \{g, o, p\}}, & \text{if $o = \max \{ g, o, p \};$}\\ 0, &\text{if $o \lt \max \{ g, o, p \}$}\end{cases} \\ p( X^{n+1} = (g,o,p-1,s) \mid X^n = (g,o,p,s) ) &= \begin{cases} \frac{p}{g+o+p} \left( 1 - \frac{1}{\arg\max \{g, o, p\}} \right), & \text{if $p = \max \{ g, o, p \};$}\\ \frac{g}{g+o+p}, &\text{if $p \lt \max \{ g, o, p \}$}\end{cases}\\ p( X^{n+1} = (g,o,p-1,s+1) \mid X^n = (g,o,p,s) ) &= \begin{cases} \frac{p}{g+o+p} \frac{1}{\arg\max \{g, o, p\}}, & \text{if $p = \max \{ g, o, p \};$}\\ 0, &\text{if $p \lt \max \{ g, o, p \}$}\end{cases} \end{align*} Here again we are only going to define the probabilities to the extend that these states remain in $\mathbb{N}^4.$ In order to fully specify this as a Markov chain, let's assert that $p( X^{n+1} = (0,0,0,s) \mid X^n = (0,0,0,s) ) = 1$ for each $s \in \mathbb{N}$ and that all other not explicitly stated transitions have a probability of zero.

Using these transition probabilities we can define the function $f : \mathbb{N}^4 \to \mathbb{N}$ to be the expected total score when there are no more rabbits left in the hat conditional on starting at say $X^0 = (g, o, p, s),$ or for instance we can have $f(g, o, p, s) = \mathbb{E} \left[ e_4^T X^\infty \right]$ where $\{ X^n \}_{n \in \mathbb{N}}$ is the Markov chain specified above. Given the transition probabilities, we can define the boundary conditions $f(0,0,0,s) = s,$ for all $s \in \mathbb{N},$ with the recursion formula \begin{align*}f(g,o,p,s) &= I ( g \geq 1 ) \left( p( (g,o,p,s) \to (g-1, o, p, s) ) f(g-1, o, p, s) + p( (g, o, p, s) \to (g-1, o, p, s+1) ) f(g-1,o,p,s+1) \right) \\ & \quad + I ( o \geq 1 ) \left( p( (g,o,p,s) \to (g, o-1, p, s) ) f(g, o-1, p, s) + p( (g, o, p, s) \to (g, o-1, p, s+1) ) f(g,o-1,p,s+1) \right) \\ & \quad + I(p \geq 1) \left( p( (g,o,p,s) \to (g, o, p-1, s) ) f(g, o, p-1, s) + p( (g, o, p, s) \to (g, o, p-1, s+1) ) f(g,o,p-1,s+1) \right) \end{align*}

For the case of where we start out $g = o = p = 2$ rabbits and $s =0$ initial score, we can use this formula by hand repeatedly and eventually work out that we get the an average score of $f(2,2,2,0) = \frac{101}{30} = 3.3666666666666666\dots$ if playing optimally.

For the case of starting with $g=o=p=10$ rabbits and $s = 0$, there are too many cases for many (or at least me) to keep track of, so we can appeal to a quick recursive function with memoization to make it relatively fast. For instance see the quick Python implementation below. This then gives the average score in the Extra Credit case of $f(10,10,10,0) = 13.703132371084621\dots$ if playing optimally.

cache = {}

def func(g, o, p, s):

    if max(g, o, p) == 0:

        return s

    if (g, o, p, s) in cache.keys():

        return cache[(g,o,p,s)]

    else:

        out = 0

        count = sum([1 for i in [g, o, p] if i == max(g, o, p)])

        if g > 0:

            prob = 1. / count if g == max(g, o, p) else 0

            out += func(g-1, o, p, s) * g / float(g + o + p) * (1-prob)

            out += func(g-1, o, p, s+1) * g / float(g + o + p) * prob

        if o > 0:

            prob = 1. / count if o == max(g, o, p) else 0

            out += func(g, o-1, p, s) * o / float(g + o + p) * (1-prob)

            out += func(g, o-1, p, s+1) * o / float(g + o + p) * prob

        if p > 0:

            prob = 1. / count if p == max(g, o, p) else 0

            out += func(g, o, p-1, s) * p / float(g + o + p) * (1-prob)

            out += func(g, o, p-1, s+1) * p / float(g + o + p) * prob

        cache[(g,o,p,s)] = out

    return out