Loading [MathJax]/jax/element/mml/optable/MathOperators.js

Monday, July 21, 2025

Was this what life was like before cell phones? Extra Credit

Instead of three total friends, now suppose there are four total friends (yourself included). As before, you all arrive at random times during the hour and each stay for 15 minutes. On average, what would you expect the maximum number of friends meeting up to be?

OK, well now your other friend Wenceslas, whose arrival time is modeled by WU(0,1), joins in on the "plan" to randomly meet up at the mall. In this case, we can still calculate the maximum number of friends based on W,X,Y,Z to be ˜N=˜N(W,X,Y,Z)=maxt[0,3/4]#{s{W,X,Y,Z}tst+14}.

Here I will resort to just coding up the function ˜N and throwing a Monte Carlo simulator at the problem. In particular, let's define the following two functions, since we might as well also code up and confirm our earlier function N, while we're at it.

import numpy as np
def max_num_friends3(x,y,z):
    sort = np.sort(np.array([x,y,z]))
    d1 = sort[1]-sort[0]
    d2 = sort[2]-sort[1]
    if d1+d2 <= 0.25:
        return 3
    elif min(d1,d2) <= 0.25:
        return 2
    else:
        return 1
    
def max_num_friends4(w,x,y,z):
    sort = np.sort(np.array([w,x,y,z]))
    d1 = sort[1]-sort[0]
    d2 = sort[2]-sort[1]
    d3 = sort[3]-sort[2]
    if d1+d2+d3 <= 0.25:
        return 4
    elif (d1+d2 <=0.25) or (d2+d3 <= 0.25):
        return 3
    elif min(d1,d2,d3) <= 0.25:
        return 2
    else:
        return 1

The following Monte Carlo setup was run, generating S=100000 simulations for ˜N and 4S simulations for N (since we can take 4 selections of three from among W,X,Y, and Z).

sims = 100000
t = []
f = []
x = np.random.uniform(size=(sims,))
y = np.random.uniform(size=(sims,))
z = np.random.uniform(size=(sims,))
u = np.random.uniform(size=(sims,))
for i in range(sims):
    mn4 = max_num_friends4(x[i], y[i], z[i], u[i])
    f.append(mn4)
    mn3 = max_num_friends3(x[i], y[i], z[i])
    t.append(mn3)
    mn3 = max_num_friends3(u[i], y[i], z[i])
    t.append(mn3)
    mn3 = max_num_friends3(x[i], u[i], z[i])
    t.append(mn3)
    mn3 = max_num_friends3(x[i], y[i], u[i])
    t.append(mn3)

The sample average of f was mf=2.4752 with sample standard deviation of sf=0.59770, meaning that the SEM is 0.00189. Therefore, when there are a total of four friends randomly showing up at the mall, the 95% confidence interval on the expected maximum number of friends meeting up at one time is 2.4752±1.960.00189=[2.4715,2.4789].

For comparison, when there are three friends randomly showing up at the mall, the 95% confidence interval on the expected maximum number of friends meeting up at one time is [2.029059,2.032336], which contains the theoretical answer of E[N]=65/32=2.03125.

Sunday, July 20, 2025

Was this what life was like before cell phones? I don't remember anymore

You and two friends have arranged to meet at a popular downtown mall between 3 p.m. and 4 p.m. one afternoon. However, you neglected to specify a time within that one-hour window. Therefore, the three of you will be arriving at randomly selected times between 3 p.m. and 4 p.m. Once each of you arrives at the mall, you will be there for exactly 15 minutes. When the 15 minutes are up, you leave.

At some point (or points) during the hour, there will be a maximum number of friends at the mall. This maximum could be one (sad!), two, or three. On average, what would you expect this maximum number of friends to be?

Let's abstract a bit and assume that your buddy Xena, you, and second buddy Zevulon each arrive at random times X, Y, Z which are i.i.d. U(0,1). The maximum number of friends at any one time between 3 and 4 p.m. is N=N(X,Y,Z)={3,if max{|XY|,|XZ|,|YZ|}14;1,if min{|XY|,|XZ|,|YZ|}>14;2,otherwise. One method for solving this problem would be to just throw some Monte Carlo simulations at this distribution, to get E[N]; however, let's see if we can't find an analytical answer first.

Let's define E(x,y)=E[N(X,Y,Z)X=x,Y=y]. If we understand E(x,y), then we see that E[N]=1010E(x,y)dxdy. From the symmetry of N we have E[N]=210x0E(x,y)dydx. Now let's study the following cases:

  • A={(x,y)[0,1]20x1,max{0,x14}yx};
  • B={(x,y)[0,1]214x1,max{0,x12}yx14};
  • C={(x,y)[0,1]212x1,0yx12}.

In case A, we have that |xy|14 already, so at the very least we have N2 regardless of the value of ZU(0,1). Furthermore, whenever max0,x14Zmin{1,y+14} we have N=3, so we must have EA(x,y)=P{N1}+P{N2}+P{N3}=2+min{1,y+14}max{0,x14}. So let IA=

In case B, we cannot have N = 3, but depending on the value of Z \sim U(0,1) we can have either N=1 or N=2. Furthermore, we see that for (x,y) \in B we have x -\frac{1}{4} \lt y + \frac{1}{4} so we have N = 2 whenever \max\{0, y - \frac{1}{4}\} \leq Z \leq \min \{ 1, x + \frac{1}{4} \}, so we must have \begin{align*}E_B(x,y) &= \mathbb{P} \{ N \geq 1 \} + \mathbb{P} \{ N \geq 2\} + \mathbb{P} \{ N \geq 3 \} \\ &= 1 + \min \{ 1, x + \frac{1}{4} \} - \max \{ 0, y - \frac{1}{4} \}.\end{align*} So let \begin{align*}I_B &= \iint_B E_B(x,y) \,dx \,dy \\ &= \int_{\frac{1}{4}}^1 \int_{\max \{ 0, x - \frac{1}{2} \}}^{x-\frac{1}{4}} \left( 1 + \min \{ 1, x + \frac{1}{4} \} - \max \{0, y - \frac{1}{4} \} \right) \,dy \,dx\\ &= \frac{53}{192}\end{align*}

In case C, we cannot have N = 3, but depending on the value of Z \sim U(0,1) we can have either N=1 or N=2. Furthermore, we see that for (x,y) \in B we have x -\frac{1}{4} \gt y + \frac{1}{4} so we have N = 2 whenever \max\{0, y - \frac{1}{4}\} \leq Z \leq y + \frac{1}{4}, which has probability \min \{ \frac{1}{2}, y + \frac{1}{4} \}, or x - \frac{1}{4} \leq Z \leq \min \{1, x+ \frac{1}{4}\}, which has probability \min \{ \frac{1}{2}, \frac{5}{4} - x \}, so we must have \begin{align*}E_C(x,y) &= \mathbb{P} \{ N \geq 1 \} + \mathbb{P} \{ N \geq 2\} + \mathbb{P} \{ N \geq 3 \} \\ &= 1 + \min \{ \frac{1}{2}, y + \frac{1}{4} \} + \min \{ \frac{1}{2}, \frac{5}{4}-x \}.\end{align*} So let \begin{align*}I_C &= \iint_C E_C(x,y) \,dx \,dy \\ &= \int_{\frac{1}{2}}^1 \int_{0}^{x-\frac{1}{2}} \left( 1 + \min \{ \frac{1}{2}, y + \frac{1}{4} \} + \min \{\frac{1}{2}, \frac{5}{4} -x \} \right) \,dy \,dx\\ &= \frac{43}{192}\end{align*}

So we have that the expected nmaximum number of friends is \begin{align*}\mathbb{E}[N] &= 2 \left( I_A + I_B + I_C \right)\\ &= 2 \left( \frac{33}{64} + \frac{53}{192} + \frac{43}{192} \right)\\ &= \frac{65}{32} = 2.03125\end{align*}

Sunday, July 13, 2025

Efficient bowling

If you knock down 100 pins over the course of a game, you are guaranteed to have a score that’s at least 100. But what’s the minimum total number of pins you need to knock down such that you can attain a score of at least 100?

Indeed, you can in fact obtain a score of just 100 by knocking down exactly 100 pins, for instance, by getting a total of 9 pins in each of the first 9 frames, for a score of 81, then doing ever so slightly better and bowling a 9, 1, and 9 in the 10th frame. Note that in the last frame you don't really end up getting any "bonus" points than the number of pins that you knock down (you knocked down a total of 19 pins and your score went up by 19 points).

On the other hand, consecutive strikes gives you the most amount of bonus points, so let's look at how much points you end up with by hitting n \leq 10 strikes in a row and then getting all gutterballs (0's) for the rest of the game. With the trailing gutterballs the last strike is score as just 10 points. The second-to-last strike (if applicable) gets only 10 points of bonus from the last strike and then a gutterball, so it's score is 20 points. Any strike before the second to last one receives a full 30 points since it is followed by two trailing strikes. So the score of n consecutive strikes followed by gutterballs is \begin{align*}X_n &= 10 + 20 \min \{ 1, \max \{ n- 1, 0 \} \} + 30 \max \{ n-2, 0 \} \\ &= \begin{cases} 10, &\text{if $n=1$}\\ 30(n-1), &\text{if $n = 2, 3, \dots, 10.$}\end{cases}\end{align*} At this point we can stop for the purpose of the Classic Fiddler, but just for completeness, if we have 11 strikes in a row followed by a gutterball, we have X_{11} = 290, and a perfect 12 strikes yields X_{12} = 300. So we see that we can certainly get more than 100 by getting 5 consecutive strikes, but probably need 4 consecutive strikes plus some other trailing pins to most efficiently get to 100.

Let's assume that our first 4 frames were strikes, and let's assume that we are being efficient and want to take frames 6 through 10 off by devising ever more childish ways of gutterballing or foot faulting or other bowling alley hijinx. In this case the outcome of our total score depends on the values of our two balls in frame 5, say b_1 and b_2. In particular, the final score for frame 3 will be 20+b_1, while the final score for frame 4 will be 10+b_1+b_2, and the score for frame 5 will be b_1+b_2, so the overal final score of your entire round is S(b_1,b_2) = 60 + (20+b_1) + (10+b_1+b_2) + (b_1+b_2) = 90 + 3b_1 + 2b_2, since the first two frames will have already been scored at their maximal values of 30, each. Here we want to then solve the integer linear program \begin{align*}\min \,\, & b_1+b_2 \\ \text{s.t.} \,\, & 3b_1 + 2b_2 = 10 \\ & b_1, b_2 \in \{0,1,2,3,4,5,6,7,8,9\}.\end{align*} There are really only two possible feasible integer solutions to choose from b_1 = b_2 = 2 and b_1 = 0, b_2 = 5, so it is easy to determine that in fact \hat{b}_1=\hat{b}_2=2 is the optimal solution so that the minimum number of pins you need to knock down to attain a score of 100 is 44 pins.

Dominant bowling

You and your opponent each play a single game in which you both knock down the same number of pins. However, your scores are quite different.

Your opponent remarks, “Given only the information that we knocked down the same number of pins in our two games, there’s no way the difference between our scores could have been any greater!” What is this difference between your two scores?

As we saw in the Classic Fiddler, there is a way to knock down exactly 100 pins and get a final score of exactly 100 points. As part of that we saw that any pins knocked down in the 10th frame incur no bonus points, and we can attain any number from 0 up to 30 total pins knocked down in the 10th frame.

We will extend the result of getting a score equal to the total number of pins knocked down to all values 0 to 119. For any number less than 90, it should be relatively trivial to find some combination with no strikes or spares, so that there would be no way of getting any bonus points. For any score S \in \{91, 92, \dots, 111\}, you will need your extra ball in the 10th frame, so you can for instance get 81 points in the first 9 frames and then score S-81 in the 10th frame.

For any score S \in \{112, 113, \dots, 119\}, we have to get a bit trickier and layer on consecutive frames of gutterball then spare (-/). The fact that the spare is followed by a gutterball means that the spared frame still receives no bonus points. So for instance you can get a score of S=119 by 8 consecutive gutterball then spare frames, followed by gutterball then 9 in the 9th frame, then three strikes in the 10th frame.

The minimum score for hitting all 120 pins down is 130, since if you gutterball then spare the 9th frame, then the first of the three strikes in the 10th frame will be added to the score in the 9th frame. So at a certain point, you must engage accrue some bonus points, but thankfully that is not until you get to 120 pins. So we have established the minimum score per number of pins knocked down as m(P) = \begin{cases} P, &\text{if $P \leq 119$;} \\ P+10, &\text{if $P = 120.$}\end{cases}

Now it is time to establish the highest score possible to attain given a certain number of pins knocked down. Here again we will look to the Classic Fiddler where we observed that the total score of n consecutive strikes followed by all gutterballs is X_n = \begin{cases} 10, &\text{if $n=1$;}\\ 30(n-1), &\text{if $n=2,\dots, 10$;}\\ 180+10n, &\text{if $n=11, 12.$}\end{cases} So just by observation we see that if we only focus on multiples of 10, we get the maximum score per number of pins knocked down as M(P) = X_{P/10} whenever 10 \mid P. For completeness, we can fill in the gaps and note similar to the solution for the Classic Fiddler that if 20 \leq P \leq 100 and the next two balls are b_1 and b_2 that we are trying to find \begin{align*}M(P) = \max \,\, & X_{\lfloor P / 10 \rfloor} + 3b_1 + 2b_2 \\ \text{s.t.}\,\, & b_1 + b_2 = P - 10 \lfloor P / 10 \rfloor \\ & b_1, b_2 \in \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}\end{align*}, which has optimal solution \hat{b}_1 = P - 10 \lfloor P/10 \rfloor and \hat{b}_2 = 0, that is, M(P) = X_{\lfloor P / 10 \rfloor} + 3\left(P - 10 \lfloor P / 10 \rfloor\right) = 3P-30, \,\, 20 \leq P \leq 100.

Now let's go back and clean up the corner cases when P \lt 20 and P \gt 100. For P \leq 10, we have M(P) = P. If we have 10 \lt P \lt 20, then the optimization problem becomes \begin{align*}M(P) = \max \,\, & 10 + 2b_1 + 2b_2 \\ \text{s.t.}\,\, & b_1 + b_2 = P - 10 \\ & b_1, b_2 \in \{0,1,2,3,4,5,6,7,8,9\},\end{align*} which for all feasible solutions gives M(P) = 10 + 2(P-10) = 2P-10, \,\, 10 \lt P \lt 20. Whenever 100 \lt P \lt 110, then the optimization problem becomes \begin{align*}M(P) = \max \,\, & 270 + 2b_1 + b_2 \\ \text{s.t.}\,\, & b_1 + b_2 = P - 100 \\ & b_1, b_2 \in \{0,1,2,3,4,5,6,7,8,9, 10\},\end{align*} which for all feasible solutions give M(P) = 270 + 2(P-100) = 70 + 2P, \,\, 100 \lt P \lt 110. And finally, it is clear that M(P) = 290+(P-110) = 180+P, for 110 \lt P \leq 120. So putting this altogether we get the maximum score per number of pins knocked down is M(P) = \begin{cases} P, &\text{if $0\leq P \lt 10;$}\\ 2P-10, &\text{if $10 \leq P \lt 20$;}\\ 3P-30, &\text{if $20 \leq P \lt 100$;}\\ 2P + 70, &\text{if $100 \leq P \lt 110$;} \\ P + 180, &\text{if $110 \leq P \leq 120$.}\end{cases}

So having exhaustive determined the minimum and maximum scores for a given number of pins knocked down the only thing left to do is to determine that largest possible margin of victory given that the two bowlers knocked down the same number of pins, that is V(P) = M(P) - m(P) = \begin{cases} 0, &\text{if $0 \leq P \lt 10;$} \\ P-10, &\text{if $10 \leq P \lt 20$;} \\ 2P-30, &\text{if $20 \leq P \lt 100;$} \\ P+70, &\text{if $100 \leq P \lt 110;$} \\ 180, &\text{if $110 \leq P \leq 119$;} \\ 170, &\text{if $P = 120.$}\end{cases} Scrutinizing the margin of victory function, we see that the largest possible margin of victory is 180 points, which can be attained P \in \{110, 111, \dots, 119\}.

Monday, July 7, 2025

Or maybe the 5,918th one?

In celebration of America’s birthday, let’s count more shapes—not in a board game, but in the American flag:

In particular, consider the centers of the 50 stars depicted on the flag. How many distinct parallelograms can you find whose vertices are all centers of stars? (If two parallelograms are congruent but have different vertices, they should still be counted as distinct.)

Here we will code everything up directly and let the same nice computer that helped us find those extra equilateral triangles hiding in plain sight find all of the parallelograms in the vertices. One note, just as we ignored the degenerate, length 0 equilateral triangles in the classic Fiddler, let's ignore degenerate parallelograms that have zero area. Let's establish the vertices as \mathcal{V} = \{ (x,y) \in \mathbb{N}^2 \mid x+y \mod 2 \equiv 0, x \leq 10, y \leq 8 \}, which will give us the distinctive 6-5-6-5-6-5-6-5-6 pattern on the American flag.

We could loop through all possible 4-ples of distinct vertices in \mathcal{V} and test for both being a parallelogram and having nonzero area. However, this would require testing over 5 million possible 4-ples (=50 \cdot 49 \cdot 48 \cdot 47). Let's instead take a somewhat more reasonable approach and take triples of points (meaning only about 100,000 tests) and first determine the area of the resulting parallelogram using the determinant formulation. That is the area of a parallelogram with three vertices X = (x_1,x_2), Y=(y_1, y_2), and Z=(z_1,z_2) is given by A = \left| \det \begin{pmatrix} x_1 & x_2 & 1 \\ y_1 & y_2 & 1 \\ z_1 & z_2 & 1 \end{pmatrix} \right|.

If the resulting area is nonzero, then we can test whether the fourth vertex of a parallelogram with vertices X, Y, and Z is in \mathcal{V}. To do this, we see that if X, Y and Z are three vertices of a parallelogram, then the fourth vertex is given by either U_1 = X + Y - Z, U_2 = X + Z - Y or U_3 = Y + Z - X. If U_i \in \mathcal{V}, for some i = 1, 2, 3, then we can add the parallelogram with vertices X, Y, Z and U_i to the list of parallelograms.

Looping through all possible distinct triples in \mathcal{V}, we find that there are 5,918 non-degenerate parallelograms that can be made using the centers of the stars on the American flag.

Sunday, July 6, 2025

Are you sure it's not the 126th Fiddler?

Dozo is a strategy game with a rather distinctive board:

The board features 28 holes in which players place markers, with the goal of making an equilateral triangle of any size with one color. How many distinct equilateral triangles can you find whose vertices are the centers of holes on the board? (If two triangles are congruent but have different vertices, they should still be counted as distinct.)

Let me first say that this is one of those Fiddlers that I wish I had not programmed up to try to verify my scratch work. I had a bunch of lovely handwritten work that mistakenly classified the only possible equilateral triangles on the Dozo board as those that had up, down, left or right orientation, with respect to an xy-plane that chose one side of the triangular board as the x-axis. Examples of up-, down-, left-, and right-oriented equilateral triangles are shown below in red, blue, orange and green, respectively. If I had stuck with the combinatorial work I had done with these up, down, left and right oriented equilateral triangles, then the ultimate answer would have be .... 100, oh the delightful, thoughtful deliberate work to get an answer that aligns with the official tally of how many of these we have ever done.

But alas, to confirm, I outsourced the work to some nice computer by defining the coordinates of the holes on the Dozo board and then running through all triplets of holes to find cases where the distances between each vertex are identical. Let's first define the coordinates. Let the top of the Dozo board, as shown, be the x-axis, with the seven holes located at (-3,0), (-2, 0), \dots, (2,0), (3,0). This means that the distance between each vertex with have unit length, and means that the second row should then be (-2.5, -\frac{\sqrt{3}}{2}), (-1.5, -\frac{\sqrt{3}}{2}), \dots, (1.5, -\frac{\sqrt{3}}{2}), (2.5, -\frac{\sqrt{3}}{2}), and so on and so forth until we get to the final lowest vertex at (0, -3\sqrt{3}).

As described above, once all 28 of the vertices were coded up, the search for all possible equilateral triangles loops through all possible unique triplets (i, j, k) \in \{1,2,\dots,28\}^3 with i \lt j \lt k and tests whether \|v_i - v_j\|_2 = \|v_j-v_k\|_2 = \|v_i - v_k\|_2. In this case, it yields all 100 of the up, down, left and right oriented equilateral triangles along with 26 additional ones for a total of 126 equilateral triangles on the Dozo board. Some examples of the equilateral triangles that do not have one of the four orientations given above are shown in the chart below, with the fuschia triangle having side lengths of \sqrt{7}, the yellow triangle having side lenghts of \sqrt{13}, and the purple triangle having side lengths of \sqrt{21}. There are a total 18 possible equialteral triangles with side lengths of \sqrt{7}, 6 with side lengths of \sqrt{13} and 2 with side lenghts \sqrt{21}.

Monday, June 30, 2025

Would a comma have hurt anyone? Extra Credit

Having successfully hacked your way through the first keypad, the door opens to reveal a second door with yet another keypad that has six numerical inputs: “I,” “II,” “III,” “IV,” “V,” “VI,” “VII,” and “VIII.”

You were expecting this, which is why your accomplice had handed you a second scroll of paper. You unfurl this one as well, hoping they remembered to add spaces between the numbers.

No such luck. This paper reads: “IIIVIIIVIIIVIII.” That’s 15 characters in total. How many distinct combinations are possible for this second door?

Since there are three V characters, let's iterate on the various possibilities for these characters. Let's write the code word as C = R(w_1)R(x_1)R(w_2)R(x_2)R(w_3)R(x_3)R(w_4), where R(t) be the Roman numeral of the number t, where we see that w_i \in \{1, 2, 3\} and x_i \in \{ 4, 5, 6, 7, 8 \}. In order for the our word C to match the code provided, we would need to make sure that if x_i = 4 then x_{i-1} \leq 7, for i = 2, 3. Let \mathcal{X} = \{ (x_1, x_2, x_3) \in \{4, 5, 6, 7, 8 \}^3 \mid x_i = 4 \Rightarrow x_{i-1} \leq 7, i = 2, 3 \} be the solution set for the values of the V characters.

Let's define the indicator function \delta(t) = \begin{cases} 1, &\text{if $t=1$}\\ 0, &\text{if $t=0$.}\end{cases} Additionally let N(t) be the number of possible combinations of numerals that in "I", "II", and "III" that can be found in R(t). In particular, N(0)=N(1)=1, N(2)=2 and N(3)=4. For any (x_1, x_2, x_3) \in \mathcal{X}, we would also need to have the following conditions be met in order for our word C to match the code provided: \begin{align*}w_1 = w_1(x_1) &= 3 - \delta(x_1-4) \\ w_2 = w_2(x_1,x_2) &= \min \{ 3, 8 - x_1 \} - \delta(x_2 - 4) \\ w_3 = w_3(x_2,x_3) &= \min \{ 3, 8 - x_2 \} - \delta (x_3-4) \\ w_4 = w_4(x_3) &= \min \{3, 8 - x_3 \}\end{align*} Then, the total number of distinct code combinations where the V characters are assigned to the numbers (x_1,x_2,x_3) is given by N(w_1(x_1))N(w_2(x_1,x_2))N(w_3(x_2,x_3))N(w_4(x_3)).

Therefore, the total possible number of distinct combinations for the second door is \hat{N} = \sum_{(x_1,x_2,x_3) \in \mathcal{X}} N(w_1(x_1))N(w_2(x_1,x_2))N(w_3(x_2,x_3))N(w_4(x_3)) = 4000.

Would a comma have hurt anyone?

You are breaking into a vault that contains ancient Roman treasure. The vault is locked, and can be opened via a modern-day keypad. The keypad contains three numerical inputs, which are (of course) expressed using Roman numerals: “I,” “II,” and “III.”

It’s a good thing your accomplice was able to steal the numerical key code to the vault. Earlier in the day, they handed you this code on a scroll of paper. Once at the keypad, you remove the scroll from your pocket and unfurl it. It reads: “IIIIIIIIII.” That’s ten vertical marks, without any clear spacing between them.

With some quick mental arithmetic, you realize the combination to unlock the door could be anywhere from four digits long to 10 digits long. (Or is it IV digits to X digits?) How many distinct combinations are possible? If two combinations use the same numbers but in a different order, they are considered distinct.

Let n_1 be the number of "I" numerals, n_2 the number of "II" numerals and n_3 the number of "III" numerals. Since there are total of ten vertical marks, we must have n_1 + 2n_2 + 3n_3 = 10. If we have a nonnegative solution to this Diophantine equation, then since any order of the different numbers is a distinct combination, then for any solution there are a total of \frac{(n_1+n_2+n_3)!}{n_1! n_2! n_3!} possible combinations associated with the solution (n_1, n_2, n_3).

We can solve this Diophantine equation by iterating through the possible cases for n_3 \in \{0,1,2,3\}. When n_3 = 0, the remaining equation is n_1 + 2n_2 = 10, which has nonnegative solutions n_1 = 10 - 2k, n_2 = k, k = 0, 1, 2, 3, 4, 5. When n_3 = 1, the remaining equation is n_1 + 2n_2 = 7, which has nonnegative solutions n_1 = 7-2k, n_2 = k, k = 0, 1, 2, 3. When n_3 = 2, the remaining equation is n_1 + 2n_2 = 4, which has nonnegative solutions n_1 = 4-2k, n_2 = k, k = 0, 1, 2. Finally, when n_3 = 3, the remaining equation is n_1 + 2n_2 = 1, which has only a single nonnegative solution n_1 = 1, n_2 = 0. So overall, the solution set is \begin{align*}\mathcal{N} &= \{ (0,2,2), (0,5,0), (1,0,3), (1,3,1), (2,1,2), (2,4,0), (3,2,1), \\ &\quad\quad (4,0,2), (4,3,0), (5,1,1), (6,2,0), (7,0,1), (8,1,0), (10,0,0) \}\end{align*} So, the total number of possible combinations is \begin{align*}N &= \sum_{(n_1,n_2,n_3) \in \mathcal{N}} \frac{(n_1+n_2+n_3)!}{n_1! n_2! n_3!} \\ &= \frac{4!}{0!2!2!} + \frac{5!}{0!5!0!} + \frac{4!}{1!0!3!} + \frac{5!}{1!3!1!} + \frac{5!}{2!1!2!} + \frac{6!}{3!2!1!} \\ & \quad\quad +\frac{6!}{4!0!2!} + \frac{7!}{4!3!0!} + \frac{7!}{5!1!1!} + \frac{8!}{6!2!0!} + \frac{8!}{7!0!1!} + \frac{9!}{8!1!0!} + \frac{10!}{10!0!0!} \\ &= 6+1+4+20+30+15+60+15+35+42+28+8+9+1 \\ &=274\end{align*}

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

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

Sunday, May 4, 2025

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 12th 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].

Sunday, April 27, 2025

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.

Sunday, April 20, 2025

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.

Monday, April 14, 2025

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.