Monday, July 28, 2025

Tour de Fiddler 2025 - Extra Credit

Instead of one opponent, now you have two—meaning three riders in total. As luck would have it, the managers for both other riders proclaimed that they’d sprint for the finish as long as their legs were feeling 50 percent or better. Note that your opponents’ feelings are independent of each other.

As the three of you near the finish, your own team manager radios you the following message: “If your legs feel <garbled> percent or better, sprint for the finish!”

You can’t make out what the garbled part of the message is, and you’re too tired to radio back for confirmation. Instead, you somehow muster the energy to randomly, uniformly pick a number between 0 and 100 to fill in the blank from your manager’s message, thereby determining your racing strategy—optimization be damned!

Right before you choose your random strategy and test your legs, what are your chances of winning the stage against both opponents?

Similar to the classic answer, we want to let your legs be $X \sim U(0,1),$ and your two opponents be $Y, Z \sim^{\text{i.i.d.}} U(0,1).$ Let your strategy be $U_a$ such that you will sprint if and only if $X \geq a.$ Here you again will win with $100\%$ probability if you are the only one sprinting. You will never win if you are not sprinting and at least one of opponents is sprinting. Here if no one is sprinting then your win probability drops to $\frac{1}{3}$ since you each have equal probability of winning. It gets a little more complicated here if multiple people are sprinting. Obviously, if only one opponent is sprinting, then your win probability is equivalent to case where both you and your single opponent from the Classic question are sprinting, that is, $\frac{1}{2} \left(p(a) - \frac{1}{2} - \frac{a}{4}\right).$ Leaving only the more complicated problem of what happens when all of the racers are sprinting. So to summarize we have \begin{align*}\tilde{p}(a) &= \mathbb{P} \{ X \geq a, \max\{Y,Z\} \lt \frac{1}{2} \} + 0 \mathbb{P} \{ X \lt a, \max \{Y,Z\} \geq \frac{1}{2} \} \\ &\quad\quad\quad +\frac{1}{3} \mathbb{P} \{ X \lt a, \max \{Y,Z\} \lt \frac{1}{2} \} + 2 \mathbb{P} \{ X \lt a, Y \geq \frac{1}{2}, X \geq Y, Z \lt \frac{1}{2} \} \\ &\quad\quad\quad\quad +\mathbb{P} \{ X \geq a, \min \{Y, Z \} \geq \frac{1}{2}, X \geq \max\{Y, Z\} \} \\ &= \frac{1-a}{4} + 0 + \frac{a}{12} + \frac{1}{8} - \frac{1}{2}\left( \max\{a-\frac{1}{2},0\}\right)^2 + \int_a^1 \left( \int_{\frac{1}{2}}^{\max\{\frac{1}{2},x\}} \,dy \right) \left( \int_{\frac{1}{2}}^{\max\{\frac{1}{2},x\}} \,dz \right) \,dx \\ &= \frac{3}{8} - \frac{a}{6} - \frac{1}{2} \left(\max \{a-\frac{1}{2},0\}\right)^2 + \int_a^1 \left(\max{x-\frac{1}{2},0} \right)^2 \,dx \\ &= \frac{5}{12} - \frac{a}{6} - \frac{1}{2} \left( \max \{ a - \frac{1}{2}, 0 \} \right)^2 + \frac{1}{24} - \frac{1}{3} \left( \max\{a - \frac{1}{2}, 0\}\right)^3 \\ &= \begin{cases} \frac{5}{12} - \frac{a}{6}, &\text{if $0 \leq a \leq \frac{1}{2}$;}\\ \frac{1}{3} + \frac{a}{12} - \frac{a^3}{3}, &\text{if $\frac{1}{2} \lt a \leq 1$.} \end{cases}\end{align*}

Therefore, the probability of winning just before choosing the value of $a$ for your strategy is \begin{align*}\Pi = \int_0^a \tilde{p}(a) \,da &= \int_0^{\frac{1}{2}} \left(\frac{5}{12} - \frac{a}{6}\right) \,da + \int_{\frac{1}{2}}^1 \left(\frac{1}{3} + \frac{a}{12} - \frac{a^3}{3}\right) \,da \\ &= \left[ \frac{5a}{12} - \frac{a^2}{12} \right]_{a=0}^{a= \frac{1}{2}} + \left[ \frac{a}{3} + \frac{a^2}{24} - \frac{a^4}{12} \right]^{a=1}_{a = \frac{1}{2}} \\ &= \left( \frac{5}{24} - \frac{1}{48} \right) - 0 + \left( \frac{1}{3} + \frac{1}{24} - \frac{1}{12} \right) - \left( \frac{1}{6} + \frac{1}{96} - \frac{1}{192} \right) \\ &= \frac{3}{16} + \frac{7}{24} - \frac{33}{192} = \frac{36 + 56 - 33}{192} = \frac{59}{192} = 0.3072916666\dots \end{align*}

Tour de Fiddler 2025

This time around, you and a competitor are approaching the finish of a grueling stage of the Tour de Fiddler. One of you will win the stage, the other will come in second. As you approach the finish, each of you will test the feeling of your legs, which will be somewhere between 0 percent (“I can barely go on!”) and 100 percent (“I can do this all day!”). For the purposes of this puzzle, these values are chosen randomly, uniformly, and independently.

Immediately after feeling your legs, you and your opponent each have a decision to make. Do you maintain your current pace, or do you sprint to the finish? Among those who sprint for the finish, whoever’s legs are feeling the best will win the stage. But if no one sprints for the finish, everyone has an equal chance of winning the stage. In the Tour de Fiddler, you must each decide independently whether to sprint for the finish based on your legs—you don’t have time to react to your opponent’s decision.

Normally, teams at the Tour de Fiddler keep their strategy and tactics close to the vest. But earlier today, your opponent’s manager declared on international television that if your opponent’s legs were feeling 50 percent or better, they’d sprint for the finish.

As you are about to test your legs for the final sprint and see how they feel, what are your chances of winning the stage, assuming an optimal strategy?

Let's explore possible strategies that mirror our opponent. Let $U_a$ represent the strategy that if when you check your legs and sprint whenever our legs are over the level $a \in [0,1].$ Let's assume that your legs are represented by $X \sim U(0,1)$ and your opponent's legs are represented by $Y \sim U(0,1)$ and that $X$ and $Y$ are independent. Note that your win probability is $100\%$ if you sprint but your opponent does not, $0\%$ if you do not sprint but your opponent does, and $50\%$ if neither of you sprint. The only rather complicated calculation is when you both sprint. If you have chosen the strategy $U_a,$ then your win probability is given by \begin{align*}p(a) &= \mathbb{P} \{ X \geq a, Y \lt \frac{1}{2} \} + 0 \mathbb{P} \{ X \lt a, Y \geq \frac{1}{2} \} \\ &\quad\quad\quad\quad +\frac{1}{2} \mathbb{P} \{ X \lt a, Y \lt \frac{1}{2} \} + \mathbb{P} \{ X \geq a, Y \geq \frac{1}{2}, X \geq Y \}\\ &= \frac{1-a}{2} + 0 + \frac{a}{4} + \int_a^1 \int_{\frac{1}{2}}^{\max\{x,\frac{1}{2}\}} \,dy \,dx \\ &= \frac{1}{2} - \frac{a}{4} + \int_a^1 \max \{x - \frac{1}{2}, 0\} \,dx \\ &= \frac{1}{2} - \frac{a}{4} + \int_{\max\{a-\frac{1}{2},0\}}^{\frac{1}{2}} t\,dt \\ &= \frac{1}{2} - \frac{a}{4} + \frac{1}{8} - \frac{1}{2} \left( \max \{ a - \frac{1}{2}, 0 \} \right)^2 \\ &= \begin{cases} \frac{5}{8} - \frac{a}{4}, &\text{if $0 \leq a \leq \frac{1}{2}$;}\\ \frac{1}{2} + \frac{a}{4} - \frac{a^2}{2}, &\text{if $\frac{1}{2} \lt a \leq 1$.}\end{cases}\end{align*} Therefore, the optimal strategy (choice of $a \in [0,1]$) will given the maximal value of $p(a)$, which since $p$ is uniformly decreasing, occurs when $a^* = 0,$ and gives an optimal win probability of $$p^* = \max_{a \in [0,1]} p(a) = p(0) = \frac{5}{8}.$$

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 $W \sim U(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 $$\tilde{N} = \tilde{N}(W,X,Y,Z) = \max_{t \in [0,3/4]} \# \left\{ s \in \{W,X,Y,Z\} \mid t \leq s \leq t + \frac{1}{4} \right\}.$$

Here I will resort to just coding up the function $\tilde{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 $\tilde{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 $m_f = 2.4752$ with sample standard deviation of $s_f = 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 \pm 1.96 \cdot 0.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 $\mathbb{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) = \begin{cases} 3, &\text{if $\max \{ |X-Y|, |X-Z|, |Y-Z| \} \leq \frac{1}{4}$;}\\ 1, &\text{if $\min \{ |X-Y|, |X-Z|, |Y-Z| \} \gt \frac{1}{4}$;}\\ 2, &\text{otherwise.}\end{cases}$$ One method for solving this problem would be to just throw some Monte Carlo simulations at this distribution, to get $\mathbb{E}[N]$; however, let's see if we can't find an analytical answer first.

Let's define $E(x,y) = \mathbb{E} [ N(X,Y,Z) \mid X=x, Y=y ].$ If we understand $E(x,y),$ then we see that $$\mathbb{E}[N] = \int_0^1 \int_0^1 E(x,y) \, dx \, dy.$$ From the symmetry of $N$ we have $$\mathbb{E}[N] = 2 \int_0^1 \int_0^x E(x,y) \, dy\, dx.$$ Now let's study the following cases:

  • $A = \{ (x,y) \in [0,1]^2 \mid 0 \leq x \leq 1, \max\{0,x-\frac{1}{4}\} \leq y \leq x \};$
  • $B = \{ (x,y) \in [0,1]^2 \mid \frac{1}{4} \leq x \leq 1, \max\{0, x - \frac{1}{2} \} \leq y \leq x - \frac{1}{4} \};$
  • $C = \{ (x,y) \in [0,1]^2 \mid \frac{1}{2} \leq x \leq 1, 0 \leq y \leq x - \frac{1}{2}\}.$

In case A, we have that $|x-y| \leq \frac{1}{4}$ already, so at the very least we have $N \geq 2$ regardless of the value of $Z \sim U(0,1)$. Furthermore, whenever $\max{0,x-\frac{1}{4}} \leq Z \leq \min \{ 1, y + \frac{1}{4} \}$ we have $N=3,$ so we must have \begin{align*}E_A(x,y) &= \mathbb{P} \{ N \geq 1 \} + \mathbb{P} \{ N \geq 2\} + \mathbb{P} \{ N \geq 3 \} \\ &= 2 + \min \{ 1, y + \frac{1}{4} \} - \max \{ 0, x - \frac{1}{4} \}.\end{align*} So let \begin{align*}I_A &= \iint_A E_A(x,y) \,dx \,dy \\ &= \int_0^1 \int_{\max \{ 0, x - \frac{1}{4} \}}^x \left( 2 + \min \{ 1, y + \frac{1}{4} \} - \max \{0, x - \frac{1}{4} \} \right) \,dy \,dx\\ &= \frac{33}{64}\end{align*}

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