Finding the luckiest coin

I have in my possession 1 million fair coins. Before you ask, these are not legal tender. Among these, I want to find the “luckiest” coin.

I first flip all 1 million coins simultaneously (I’m great at multitasking like that), discarding any coins that come up tails. I flip all the coins that come up heads a second time, and I again discard any of these coins that come up tails. I repeat this process, over and over again. If at any point I am left with one coin, I declare that to be the “luckiest” coin.

But getting to one coin is no sure thing. For example, I might find myself with two coins, flip both of them and have both come up tails. Then I would have zero coins, never having had exactly one coin.

What is the probability that I will — at some point — have exactly one “luckiest” coin?

Let $N_t$ be the number of remaining coins after $t$ flips, removing any coins that were tails. We start with $N_0 = 1,000,000.$ We could set this entire problem up to be a Markov chain with binomial transition probabilities, however, since we will want to keep track of the “luckiest” we would be better served making both $N=0$ and $N=1$ into absorbing states. That is, let $P = \{ P_{ij} \}_{i,j=1}^{N_0}$ be the transition probability matrix then $$P_{ij} = \mathbb{P} \{ N_{t+1} = j \mid N_t = i \} = \begin{cases} 1, &\text{if $i=j=0$ or $i=j=1$;}\\ \binom{i}{j} 2^{-i}, &\text{if $j \geq 2$, $0 \leq i \leq j$;}\\ 0, &\text{otherwise.}\end{cases}$$

If we define the transient transition matrix $Q$ as the portion of the transition matrix associated with states $N \in \{2, \dots, N_0\},$ then the fundamental matrix of our Markov chain is given by $N=(I-Q)^{-1}.$ Further, letting $r = (P_{21},P_{31},\dots, P_{N_01})^T = (1/2, 3/2^3, \dots, N_0/2^{N_0})^T$, then the vector $b = \{b_i\}_{i=2}^{N_0}$ given by $b = Nr$ is gives the probability of starting at node $N=i \in \{2, \dots, N_0\}$ and ending up with a single luckiest coin. This is all nice in theory, but even though this just requires solving a triangular system of linear equations, given the space and time requirements of actually calculating the answer, it is somewhat prohibitive.

Instead, we can either (a) estimate the answer using simulations or (b) rely on estimates with some sufficiently large $N_0.$ Both of these methods give the same result of roughly $72\%$ that I will find a luckiest coin.

In [1]:

import numpy as np
from scipy.stats import binom

N0 = 1000000
def simulate(N0=N0):
    Niter = N0
    while Niter > 1:
        T = binom.rvs(Niter, 0.5, size=1)
        Niter -= T
    return Niter

num_sims = 10000
output = []
for i in range(num_sims):
    out = simulate()
    output.append(float(out))
print('{} simulations with N0={} yield an estimated probability of {}'.format(num_sims, N0, sum(output) / num_sims))


## Running matrix algebra with (N0-2) x (N0-2) matrices is dicey for N0 = 1e6, so let's
## scale it down and appeal to the fact that the answer should not change much for any N0
## as N0 -> inf
M = 5000
Q = np.eye(M-1)
for i in range(M-1):
    for j in range(i+1):
        Q[i,j] = binom.pmf(j+2, i+2, 0.5)
R = np.array([binom.pmf(1, i, 0.5) for i in range(2,M+1)])
B = np.linalg.solve(np.eye(M-1) - Q, R)
print('Using the fundamental matrix of the Markov chain gives a theoretical value of {}, for an initial number of coins of N0={}'.format(B[-1],M))

10000 simulations with N0=1000000 yield an estimated probability of 0.7181
Using the fundamental matrix of the Markov chain gives a theoretical value of 0.7213410794890949, for an initial number of coins of N0=5000

In [ ]:

Tramping randomly abroad

It’s time for a random number duel! You and I will both use random number generators, which should give you random real numbers between $0$ and $1.$ Whoever’s number is greater wins the duel!

There’s just one problem. I’ve hacked your random number generator. Instead of giving you a random number between $0$ and $1,$ it gives you a random number between $0.1$ and $0.8.$

What are your chances of winning the duel?

N.B. - Upon reading this question prompt, I was reminded by Twain's story in A Tramp Abroad of acting as a second in a French duel and suggesting the combatants use brick-bats at a distance of three-quarters of a mile. It seems to me, that if only black box random number generators were readily available at the time, that this would have served as a much more suitable sarcastic dueling method for Twain's predicament, but alas!

Anyway, since you seem to have the dastardly ability to tamper with my RNG, let's solve the general case that you have provided me with a uniform random number generator on some generic interval $(a,b) \subsetneq [0,1].$ In this case, let's say that my distribution is $X \sim U(a,b)$ and yours is $Y \sim U(0,1).$ Then, my survival probability (this is to the death, Schroedinger's cat-style, yes?) is \begin{align*}\mathbb{P} \{ X > Y \} &= \int_0^1 \mathbb{P} \{ X > y \mid Y = y \} \,dy \\ &= \int_0^a \mathbb\{ X > y \} \,dy + \int_a^b \mathbb{P} \{X > y \} \,dy + \int_b^1 \mathbb{P} \{ X > y \} \,dy \\ &= a + \int_a^b \frac{b-y}{b-a} \,dy + 0 = a + (b-a) \int_0^1 t \, dt \\ &= a + \frac{b-a}{2} = \frac{a+b}{2}.\end{align*}

So in this particular case, your subtle tampering has left me with only a $\frac{0.1 + 0.8}{2} = 45\%$ chance of winning our random number duel.

Polarized Express ... er, Classic

I have a light source that’s polarized in the vertical direction, but I want it to be polarized in the horizontal direction. To make that happen I need … polarizers! When light passes through a polarizer, only the light whose polarization aligns with the polarizer passes through. When they aren’t perfectly aligned, only the component of the light that’s in the direction of the polarizer passes through.

Unfortunately, that means I can’t turn vertically polarized light into horizontally polarized light with a single polarizer. But I can do it with two polarizers, as shown below.

A vector is vertical. Its component along a 45 degree angle is shown. That second vector's component along another 45 degree angle is also shown. The final vector has half the length of the original.

If the first polarizer is positioned at an acute angle with respect to the light, and then the second polarizer is positioned at a complementary angle with respect to the first polarizer, some light will be horizontally polarized in the end.

Now, I have tons of polarizers, and each one also reflects 1 percent of any light that hits it — no matter its polarization or orientation — while polarizing the remaining 99 percent of the light.

I’m interested in horizontally polarizing as much of the incoming light as possible. How many polarizers should I use?

Let's say that we have $N$ polarizers which are placed with polarizing angle $0 \lt \theta_1 \lt \theta_2 \leq \cdots \leq \theta_N = \frac{\pi}{2}$ (with respect to the vertical initial angle). Given the gain of $g = 0.01$ that is reflected at each polarizer, the ultimate amount of horizontally polarized light will be $$I_N(\theta_1, \dots, \theta_{N-1}, \theta_N \mid g) = (1-g)^N \cos \theta_1 \prod_{i=2}^N \cos (\theta_i - \theta_{i-1})$$

Either by happenstance or by base case, we will first show that if you only use two polarizers that the optimal positioning is to place one with angle $\theta_1^* = \frac{\pi}{4}.$ In this case, $$I_2(\theta_1, \theta_2 \mid g) = (1-g)^2 \cos \theta_1 \cos (\theta_2 - \theta_1),$$ which has derivative $$\frac{\partial}{\partial\theta_1} I_2(\theta_1, \theta_2 \mid g) = (1-g)^2 \left( -\sin \theta_1 \cos (\theta_2 - \theta_1) + \cos \theta_1 \sin (\theta_2 - \theta_1) \right),$$ or equivalently, $\tan \theta_1 = \tan (\theta_2 - \theta_1).$ Since $y = \tan x$ is a monotonically increasing function on $(-\pi/2, \pi/2)$ and has a period of $\pi,$ then we have $\tan \theta = \tan \phi$ if and only if $\theta - \phi \in \pi \mathbb{Z}.$ Thus, since we have $\theta_1, \theta_2 - \theta_1 \in [0, \pi / 2)$ if $\tan \theta_1 = \tan (\theta_2 - \theta_1)$ then we must have $\theta_1 = \theta_2 - \theta_1,$ or equivalently $\theta_1 = \frac{\theta_2}{2}.$ Note that when $\theta_2 = \pi/2,$ then $I_2^*(g) = \frac{(1-g)^2}{2}.$

Assume that for some $N-1$ and any $\theta_{N-1} \in (0, \pi/2),$ the optimally spaced polarizers have polarizing angles $\theta_i = \frac{i \theta_{N-1}}{(N-1)},$ for $i = 1, \dots, N-1.$ In this case, we would then have $$I_{N-1}^*(g) = \left( (1-g) \cos \frac{\pi}{2(N-1)} \right)^{N-1}.$$

Let's choose any arbitrary $\theta_1 \in (0,\pi/2).$ From our induction step, we would then place the remaining $N-1$ polarizers with angles equidistantly spaced out between $\theta_1$ and $\pi/2,$ that is $$\theta_i = \theta_1 + (i-1) \frac{\frac{\pi}{2} - \theta_1}{N-1},$$ for $i = 2, \dots, N.$ In this case, we have $$I_N(\theta_1 \mid g) = I_N(\theta_1, \theta_2, \dots, \theta_N \mid g) = (1-g)^N \cos \theta_1 \cos^{(N-1)} \left( \frac{\frac{\pi}{2} - \theta_1}{N-1} \right).$$ In this case, we see that the derivative is \begin{align*}\frac{d}{d\theta_1} I_N &= (1-g)^N \left( -\sin \theta_1 \cos^{(N-1)} \left( \frac{\frac{\pi}{2} - \theta_1}{N-1} \right) + \cos \theta_1 \sin \left( \frac{\frac{\pi}{2} - \theta_1}{N-1} \right) \cos^{(N-2)} \left( \frac{\frac{\pi}{2} - \theta_1}{N-1} \right) \right) \\ &= (1-g)^N \cos^{(N-2)} \left( \frac{\frac{\pi}{2} - \theta_1}{N-1} \right) \left( -\sin \theta_1 \cos \left( \frac{\frac{\pi}{2} - \theta_1}{N-1} \right) + \cos \theta_1 \sin \left( \frac{\frac{\pi}{2} - \theta_1}{N-1} \right) \right).\end{align*} Thus the derivative will be equal to zero if either $\theta_1 = \frac{\pi}{2}$ or $$\tan \theta_1 = \tan \left( \frac{\frac{\pi}{2} - \theta_1}{N-1} \right)$$ or equivalently $$\theta_1 = \frac{\frac{\pi}{2} - \theta_1}{N-1} \Rightarrow \theta_1 = \frac{\pi}{2N}.$$ In this case, we have again $\theta_i = \frac{i \pi}{2N}$ for $i = 1, \dots, N$ and $$I_N^*(g) = \left( (1-g) \cos \frac{\pi}{2N} \right)^N.$$

Therefore, by induction, for any number of polarizers $N,$ the optimal amount of horizontally polarized light is $$I_N^*(g) = \left( (1-g) \cos \frac{\pi}{2N} \right)$$ for any $N = 2, 3, \dots.$ The partial derivative with respect to $N$ is given by $$\frac{\partial}{\partial N} I_N^*(g) = I_N^*(g) \left( \ln(1-g) + \ln \cos \frac{\pi}{2N} + \frac{\pi}{2N} \tan \frac{\pi}{2N} \right).$$ While solving this $\frac{\partial}{\partial N} I_N^*(g) = 0$ analytically would be a pain, we see that $$\frac{\partial^2}{\partial N^2} \ln I_N^*(g) = - \frac{\pi^2}{4N^3} \sec^2 \frac{\pi}{2N} \leq 0,$$ so the logarithmic derivative is monotonically decreasing, and there is a unique global maximum in $N$ of $I_N^*(g).$ If we then start calculating $I_N^*(g)$ for $N = 2, 3, \dots$ until we see the sequence start to decrease, we can then stop with our search. Luckily, it does not take that long and see from the table below that the optimal solution occurs with $N = 11$ polarizers with polarization angles $\theta_i = \frac{i \pi}{22}$ for $i = 1, \dots, 11,$ as measured from the positive $y$-axis.

\[\begin{array}{|c|c|}\hline N & I_N^*(0.01) \\\hline 2 & 0.4901 \\\hline 3 & 0.6302 \\\hline 4 & 0.6998 \\\hline 5 & 0.7400 \\\hline 6 & 0.7647 \\\hline 7 & 0.7803 \\\hline 8 & 0.7901 \\\hline 9 & 0.7959 \\\hline 10 & 0.7990 \\\hline 11 & 0.8000 \\\hline 12 & 0.7995 \\\hline\end{array}\]

Mazels on your wedding

The larger regular hexagon in the diagram below has a side length of $1.$ What is the side length of the smaller regular hexagon?

So let's first note that if the side length of the larger hexagon is $1,$ then the diameter of the circumscribing circle must be $2,$ thus it has a radius of $R = 1.$ This can be seen by noting that a regular hexagon can be divided into six equilateral triangles.

Assuming that both the larger hexagon and the circumscribing circle are centered at the origin, the upper semicircle is then given by point of the form $y = \sqrt{1-x^2}.$ In particular, let's assume that the side length of the smaller hexagon is $s,$ then the points where the smaller hexagon and the circumscribing circle intersect are $(\pm \frac{s}{2}, \sqrt{1 - \frac{s^2}{4}}).$

Again, noting that the regular hexagon can be broken into size equilateral triangles, we see that the height of the smaller hexagon is $s\sqrt{3},$ while half of the height of the larger hexagon is $\frac{\sqrt{3}}{2}.$ Therefore, the upper boundary of the smaller regular hexagon is on the line $y = \frac{\sqrt{3}}{2} + s \sqrt{3}.$ So, in particular, we have $$\sqrt{1 - \frac{s^2}{4}} = \frac{\sqrt{3}}{2} + s \sqrt{3}.$$

Squaring both sides we get $$1 -\frac{s^2}{4} = 3 \left( s + \frac{1}{2} \right)^2 = 3s^2 + 3s + \frac{3}{4},$$ or equivalently $$0 = \frac{13}{4} s^2 + 3s - \frac{1}{4} = \frac{13}{4} \left( s^2 + \frac{12}{13} s - \frac{1}{13} \right) = \frac{13}{4} (s + 1) \left(s - \frac{1}{13}\right),$$ so choosing the positive solution, we must have that the smaller hexagon has side length $\hat{s} = \frac{1}{13}.$

Generically, we can solve for any arbitrary number of additional vanishingly small hexagons by setting $s_1 = \hat{s} = 1/13$ as above, and setting up the recurrence relationship $$\sqrt{1 - \frac{s_i^2}{4}} = \sqrt{3} \left( \frac{1}{2} + \sum_{k=1}^i s_k \right),$$ where the side length of the $i$th hexagon is denoted by $s_i.$ We can square and solve this relationship to find that the side lengths of the next two smaller hexagons are $s_2 = \frac{-90 + \sqrt{8113}}{169} = 4.27179\cdot 10^{-4}$ and $s_3 = 1.31695\cdot10^{-18},$ respectively.

Sure, but what's the probability that you call timeout in OT for no reason and miss the playoffs?

In the Riddler Football League, you are coaching the Arizona Ordinals against your opponent, the Detroit Lines, and your team is down by 14 points. You can assume that you have exactly two remaining possessions (i.e., opportunities to score), and that Detroit will score no more points.

For those unfamiliar with American football, a touchdown is worth $6$ points. After each touchdown, you can decide whether to go for $1$ extra point or $2$ extra points. You happen to have a great kicker on your team, and your chances of scoring $1$ extra point (should you go for it) are $100$ percent. Meanwhile, scoring $2$ extra points is no sure thing — suppose that your team’s probability of success is some value $p$.

If the teams are tied at the end of regulation, the game proceeds to overtime, which you have a $50$ percent chance of winning. (Assuming ties are not allowed.)

What is the minimum value of $p$ such that you’d go for $2$ extra points after your team’s first touchdown (i.e., when you’re down 8 points)?

Let's set up the problem. Say $S_i$ is the score after your $i$th touchdown and extra point(s), with $S_0 = -14.$ You are faced with two choices, $u_1$ and $u_2,$ each of which can be K (kick) or T (try for two-point conversion). So the transitional probabilities are $$\mathbb{P} \{ S_i = s \mid u_i \} = \begin{cases} 1, &\text{if $u_i = K$ and $s = S_{i-1} + 7$;} \\ p, &\text{if $u_i = T$ and $s = S_{i-1} + 8$;}\\ 1-p, &\text{if $u_i = T$ and $s= S_{i-1} + 6$;}\\ 0, &\text{otherwise.}\end{cases}$$

Here we assume that losing by any number of points, or winning by any number, while potentially valuable to degenerate gamblers who are following the RFL, is of no use to you the coach (so I guess there are no weird tie breakers or other such secondary incentives to score the most points possible). So the utility function that we are trying to maximize is $$V(S_2) = \begin{cases} 1, &\text{if $S_2 \gt 0$;}\\ 0.5, &\text{if $S_2 = 0$} \\ 0, &\text{if $S_2 \lt 0$}\end{cases}$$ and we have the following optimization problem $$\max \{ \mathbb{E}[V(S_2) \mid u_1, u_2 ] \mid u_1, u_2 \in \{K, T\}, S_0 = -14\}.$$

The boring strategy would be $u_1 = u_2 = K,$ essentially playing for a tie, which give $S_2 = 0$ w.p. $1$ and so $\mathbb{E}[V(S_2) \mid u_1 = u_2 = K] = V(0) = 0.5.$ We needn't really check due to the prompt, but the strategy $u_1 = K, u_2 = T$ would give $S_1 = -7$ w.p. $1$ and so $$\mathbb{E}[V(S_2) \mid u_2 = T, u_1 = K] = p V(1) + (1-p) V(-1) = p,$$ which would only be better than $u_1 = u_2 = K$ if $p \gt 0.5.$

If instead, we go for $2$ after the first touchdown, then there are two possible outcomes. If we succeed and $S_1 \mid u_1 = -6,$ then we can safely pick $u_2 = K,$ since this will give $S_2 = 1$ w.p. $1$, so $$\mathbb{E} [V(S_2) \mid S_1 = -6, u_1 = T, u_2 = K ]= 1$$ which is a better outcome for any value of $p \lt 1$ than $$\mathbb{E}[ V(S_2) \mid S_1 = -6, u_1 = u_2 = T ] = p V(2) + (1-p) V(0) = 0.5 (1 + p).$$ If on the other hand $S_1 \mid u_1 = -8$ because the intial $2$ point conversion try was unsuccessful, then we should also do $u_2 = T,$ since $S_2 \mid S_1 = -6, u_2 = K \lt 0$ w.p. $1.$ When we go for two a second time, we have $$\mathbb{E} [V(S_2) \mid S_1 = -8, u_1=u_2=T] = pV(0) + (1-p) V(-2) = 0.5 p.$$ Therefore, if $u_1 = T,$ then we have \begin{align*}\mathbb{E}[ V(S_2) \mid u_1 = T ] &= p \mathbb{E}[V(S_2) \mid S_1 = -6,u_2 = K] + (1-p) \mathbb{E} [V(S_2) \mid S_1 = -8, u_2=T]\\ &= p + 0.5 p(1-p) = \frac{3p - p^2}{2}.\end{align*} The choice to go for $2$ after your first touchdown will be optimal whenever $$\frac{3p - p^2}{2} > \frac{1}{2},$$ or $p^2 - 3p + 1 \lt 0,$ that is, whenever $$p > \frac{3 - \sqrt{9 - 4}}{2} = \frac{3 - \sqrt{5}}{2} = 0.381966\dots.$$

When the ant hits the line, ... that's Amare

Amare the ant is traveling within Triangle ABC, as shown below. Angle A measures $15$ degrees, and sides AB and AC both have length $1$.

Amare starts at point B and wants to ultimately arrive on side AC. However, the queen of his colony has asked him to make several stops along the way. Specifically, his path must:

$\cdot$ Start at point B.

$\cdot$ Second, touch a point — any point — on side AC.

$\cdot$ Third, touch a point — any point — back on side AB.

$\cdot$ Finally, proceed to a point — any point — on side AC (not necessarily the same point he touched earlier).

What is the shortest distance Amare can travel to complete the queen’s desired path?

Amare the evidently male ant knows that that his colony has to travel along the isoceles triagle ABC with smallest angle $15$ degrees, but he wants to solve the general problem knowing that almost all queens have the same obscure rules and if he cannot mate with his queen perhaps he can abscond to some other colony to mate with that queen dazzling her with an optimal route, or something, I'm not an myrmecologist. So instead, he will solve the case where the smallest angle is some $\theta \in [0, \frac{\pi}{3}).$

Amare decides to set up an optimization problem by labeling setting the point A as the origin and B at the point $(1,0),$ thus surmising that $C$ is the point $(\cos \theta, \sin \theta).$ He decides to model his first point on the AC side of the triangle by the variable $(\alpha \cos \theta, \alpha \sin \theta)$ then the point he visits along the AB side as $(\beta, 0)$ and finally returning to the AC side at $(\gamma \cos \theta, \gamma \sin \theta)$ for some $0 \leq \alpha, \beta, \gamma \leq 1.$ Let $d_1(\alpha) = \sqrt{\alpha^2 - 2 \cos \theta \alpha + 1}$ be the length of Amare's first transit from AB to AC, let $d_2(\alpha, \beta) = \sqrt{\alpha^2 - 2 \alpha \beta \cos \theta + \beta^2}$ be the length of his passage from AC back to AB and $d_3(\beta, \gamma) = \sqrt{\beta^2 - 2 \beta \gamma \cos \theta + \gamma^2}$ the length of the final leg of his journey. Then Amare's total distance traveled is \begin{align*} d(\alpha, \beta, \gamma) &= d_1(\alpha) + d_2(\alpha, \beta) + d_3(\beta, \gamma) \\ &=\sqrt{\alpha^2 - 2 \cos \theta \alpha + 1} + \sqrt{ \alpha^2 - 2 \alpha \beta \cos \theta + \beta^2} + \sqrt{ \beta^2 - 2 \beta \gamma \cos \theta + \gamma^2}.\end{align*}

Taking the gradient, Amare gets that $$\nabla d = \begin{pmatrix} \frac{\alpha - \cos \theta}{d_1(\alpha)} + \frac{\alpha - \beta \cos \theta}{d_2(\alpha, \beta)} \\ \frac{\beta - \alpha \cos \theta}{d_2(\alpha, \beta)} + \frac{\beta - \gamma \cos \theta}{d_3(\beta, \gamma)} \\ \frac{\gamma - \beta \cos \theta }{d_3(\beta, \gamma)} \end{pmatrix}.$$ For the time being, Amare just wants to find when $\nabla d = 0,$ so he first notices that if this is the case then $\gamma = \beta \cos \theta,$ which in turn means that $$d_3(\beta, \gamma) = \sqrt{ \beta^2 - 2 \beta \gamma \cos \theta + \gamma^2} = \beta \sin \theta.$$

Therefore, if $\nabla d = 0,$ then $\gamma = \beta \cos \theta$ and plugging back into $\frac{\partial}{\partial \beta} d=0,$ we also have the equation $$\frac{\beta - \alpha \cos \theta}{d_2(\alpha, \beta)} + \frac{\beta - \gamma \cos \theta}{d_3(\beta, \gamma)} = \frac{\beta - \alpha \cos \theta}{d_2(\alpha, \beta)} + \sin \theta = 0,$$ or equivalently, $$\beta = -d_2 \sin \theta + \alpha \cos \theta.$$ Plugging this value of $\beta,$ back into $d_2(\alpha, \beta)^2$, we get \begin{align*} d_2^2 &= \alpha^2 - 2 \alpha (-d_2\sin \theta + \alpha \cos \theta) \cos \theta + (- d_2 \sin \theta + \alpha \cos \theta)^2 \\ &= \alpha^2 - 2 \alpha^2 \cos^2 \theta + 2 \alpha d_2 \sin \theta \cos \theta + d_2^2 \sin^2 \theta - 2 \alpha d_2 \sin \theta \cos \theta + \alpha^2 \cos^2 \theta \\ &= (1- \cos^2 \theta) \alpha^2 + d_2^2 \sin^2 \theta\end{align*} or equivalently $$d_2(\alpha, \beta) = \alpha \tan \theta.$$ Plugging this value back into the formula for $\beta,$ we get $$\beta = -d_2 \sin \theta + \alpha \cos \theta = \alpha \bigl( \cos \theta - \sin \theta \tan \theta\bigr) = \alpha \frac{\cos 2\theta}{\cos \theta}.$$

So finally, plugging back into $\frac{\partial}{\partial \alpha} d = 0$ we get \begin{align*}0 &= \frac{\alpha - \cos \theta}{d_1} + \frac{\alpha - \beta \cos \theta}{d_2}\\ &= \frac{\alpha - \cos \theta}{d_1} + \frac{ \alpha - \alpha \frac{\cos 2 \theta}{\cos \theta} \cos \theta }{ \alpha \tan \theta}\\ &= \frac{\alpha - \cos \theta}{d_1} + \frac{1 - \cos 2\theta}{\tan \theta}\\ &= \frac{\alpha - \cos \theta}{d_1} + \sin 2\theta\end{align*} or equivalently $$d_1 = \frac{\cos \theta - \alpha}{ \sin 2\theta}.$$ Plugging this back into $d_1^2$ we get $$\alpha^2 - 2 \alpha \cos \theta + 1 = \frac{ \cos^2 \theta - 2 \alpha \cos \theta + \alpha^2 }{ \sin^2 2\theta }$$ or equivalently $$\cos^2 2\theta \alpha^2 - 2 \cos \theta \cos^2 2\theta \alpha + \cos^2 \theta - \sin^2 2\theta = 0.$$ Solving the quadratic equation we get \begin{align*}\alpha &= \frac{2 \cos \theta \cos^2 2\theta \pm \sqrt{ 4 \cos^2 \theta \cos^4 2\theta -4 (\cos^2 2\theta) (\cos^2 \theta - \sin^2 2\theta)}}{2 \cos^2 2\theta}\\ &= \cos \theta \pm \frac{ 2 \cos 2\theta \sqrt{\cos^2 \theta \cos^2 2\theta - \cos^2 \theta + \sin^2 2\theta}}{2\cos^2 2\theta} \\ &= \cos \theta \pm \frac{\sqrt{\cos^2 \theta ( \cos^2 2\theta - 1) + \sin^2 2\theta}}{\cos 2\theta} = \cos \theta \pm \frac{ \sqrt{ \sin^2 2\theta (1 - \cos^2 \theta) }}{\cos 2\theta} \\ &= \cos \theta \pm \frac{ \sin 2\theta \sin \theta }{\cos 2\theta} = \cos \theta \pm \sin \theta \tan 2\theta = \frac{\cos \theta \cos 2\theta \pm \sin \theta \sin 2\theta}{\cos 2\theta}\end{align*} that is either $$\alpha = \frac{\cos \theta}{\cos 2\theta} \,\,\, \text{ or } \,\,\, \alpha = \frac{\cos 3\theta}{\cos 2\theta}.$$ Since $\frac{\cos \theta}{\cos 2\theta} \not \in [0,1]$ for any $\theta \in [0,\frac{\pi}{3}),$ Amare will go with $$\alpha = \frac{\cos 3\theta}{\cos 2\theta}$$ whenever $\theta \in [0, \frac{\pi}{6})$ and in this case, $$d_1 = \frac{\cos \theta - \frac{\cos 3\theta}{\cos 2\theta}}{\sin 2\theta} = \frac{\sin \theta}{\cos 2\theta}.$$ Note that when $\theta \in [\frac{\pi}{6}, \frac{\pi}{3})$ we have $\alpha = 0$ and $d_1 = 1.$

So if $\theta \in [0, \frac{\pi}{6}),$ then \begin{align*}\hat{\alpha} &= \frac{\cos 3\theta}{\cos 2\theta}, \\\hat{\beta} &= \hat{\alpha} \frac{\cos 2\theta}{\cos \theta} = \frac{\cos 3\theta}{\cos \theta} \\ \hat{\gamma} &= \hat{\beta} \cos \theta = \cos 3\theta\end{align*} and the shortest distance is \begin{align*}\hat{d} &= d(\hat{\alpha}, \hat{\beta}, \hat{\gamma}) = d_1 + d_2 + d_3 = \\ &= \frac{\sin \theta}{\cos 2\theta} + \frac{\cos 3\theta}{\cos 2\theta} \tan \theta + \frac{\cos 3\theta}{\cos \theta} \sin \theta\\ &= \sin \theta \left( \frac{\cos \theta + \cos 3\theta + \cos 2\theta \cos 3\theta}{\cos \theta \cos 2\theta} \right) \\ &= \sin \theta \left( \frac{ \cos \theta + 2 \cos^2 \theta \cos 3\theta }{\cos \theta \cos 2\theta } \right) \\ &= \sin \theta \left( \frac{1 + 2 \cos \theta \cos 3\theta}{\cos 2 \theta} \right) \\ &= \sin \theta \left( \frac{1 + \cos 4\theta + \cos 2\theta}{\cos 2\theta} \right) \\ &= \sin \theta \left( \frac{2 \cos^2 2\theta + \cos 2\theta }{\cos 2\theta} \right)\\ &= \sin \theta ( 2 \cos 2\theta + 1 ) = \sin \theta (2 \cos^2 \theta + \cos 2\theta) \\ &= \sin 2\theta \cos \theta + \sin \theta \cos 2\theta = \sin 3\theta. \end{align*} In particular, when $\theta = \frac{\pi}{12},$ we get that Amare's shortest path for his home colony's queen is $\hat{d} = \sin \frac{\pi}{4} = \frac{\sqrt{2}}{2}.$ Whenever $\theta \in [\frac{\pi}{6}, \frac{\pi}{3})$ then $\hat{\alpha}=\hat{\beta}=\hat{\gamma} = 0$ and $\hat{d} = 1.$

Infinitesimal sticks, or adventures in making things complicated and wrong

One day you stumble across a magic genie, who says that if you play a simple game with him, you could win fabulous riches. You take the genie up on his offer, and he hands you a stick of length 1. He says that behind his back is another stick, with a random length between 0 and 1 (chosen uniformly over that interval).

Next, you must break your stick into two pieces and present one of those pieces to the genie. If that piece is longer than the genie’s hidden stick, then you win a prize of $\$1$ million times the length of your remaining piece. For example, if you present to the genie a length of $0.4,$ and that’s longer than the genie’s stick, then you win $\$1$ million times $0.6,$ or $\$600,000.$ However, if the genie’s stick is longer, then you win nothing.

Being a regular reader of The Riddler, you crunch some numbers and prepare to break your stick in half. But then you have a thought. You ask the genie if you can have more than one turn. For example, if you present the genie with a length of $0.4,$ but the genie’s stick is longer, can you break off a piece of the remaining length of $0.6$ — say, a length of $0.5$ — and then present that to the genie? To keep things fair, your winnings will still be proportional to the leftover length. So had the genie’s length indeed been between $0.4$ and $0.5,$ your first and second guesses, then the remaining length would have been $0.1,$ and you would have won $\$100,000$.

The genie doesn’t think any of this really matters and says you can have as many turns as you desire. If your goal is to maximize your expected winnings, what will your strategy be? And how much money would you expect to win on average?

Mea culpa .... I had a "fundamental misunderstanding of the material" moment and proceeded with the following answer, which only works if you can then also glue all of your tiny stick pieces back together, which I suppose is a bit of a stretch interpretation of the prompt.

Assume that you want to make $n \geq 1$ breaks in the stick, let's say at $0 \leq x_1 \leq x_2 \leq \cdots \leq x_n \leq 1.$ If the genie's stick has length $G \sim U[0,1]$, then the payoff would be $$V_n(G \mid x) = \begin{cases} 1-x_1, &\text{if $G \leq x_1$ }\\ 1-x_2, &\text{if $x_1 \lt G \leq x_2$}\\ \cdots & \\ 1-x_n, &\text{if $x_{n-1} \lt G \leq x_n$}\\ 0, &\text{if $G \gt x_n$}\end{cases}$$ therefore the expected payoff (as a fraction of the genie's $\$1$ million) is $$Q_n(x) = \mathbb{E}_G \Big[ V_n(G \mid x) \Big] = \sum_{i=1}^n (1-x_i) (x_i - x_{i-1}),$$ where we assume that $x_0 = 0.$

Therefore, the optimal selection of breakpoints satisfies the maximization problem \begin{align*}\max_x \,\, & \sum_{i=1}^n (1-x_i) (x_i - x_{i-1}) \\ \text{such that} \,\, & 0 = x_0 \leq x_1 \leq \cdots \leq x_n \leq 1\end{align*} First note that $$\Delta Q_n = \begin{pmatrix} -2 & 1 & 0 & 0 & \cdots & 0 \\ 1 & -2 & 1 & 0 & \cdots & 0 \\ 0 & 1 & -2 & 1 & \cdots & 0 \\ \vdots & \ddots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & -2 \end{pmatrix} \leq 0$$ is negative semi-definite and hence concave. Further, Slater's condition holds for the set of inequalities $0 = x_0 \leq x_1 \leq \cdots \leq x_n \leq 1,$ so we have the necessary and sufficient conditions that if $\hat{x}$ satisfies $0 \lt \hat{x}_1 \lt \hat{x}_2 \lt \cdots \lt \hat{x}_n \lt 1$ and $\nabla Q_n(\hat{x}) = 0$ then is an optimal solution of the maximization problem.

For $i = 2, \dots, n-1,$ we have $$\frac{\partial}{\partial x_i} Q_n(x) = \frac{\partial}{\partial x_i} \left( (1-x_i) (x_i - x_{i-1} ) + (1 - x_{i+1}) (x_{i+1} - x_i) \right) = x_{i-1} + x_{i+1} - 2x_i.$$ We additionally have $$\frac{\partial}{\partial x_1} Q_n(x) = \frac{\partial}{\partial x_1} \left( (1-x_1) x_1 + (1 - x_2) (x_2 - x_1) \right) = x_2 - 2x_1$$ and $$\frac{\partial}{\partial x_n} Q_n(x) = \frac{\partial}{\partial x_n} (1-x_n) (x_n - x_{n-1}) = 1 + x_{n-1} - 2x_n.$$ Therefore, if we define $\hat{x}^{(n)} = (\hat{x}^{(n)}_1, \dots, \hat{x}^{(n)}_n )$ with $\hat{x}^{(n)}_i = \frac{i}{n+1},$ then we see that $\nabla Q_n(\hat{x}^{(n)}) = 0$ and hence $$Q_n(\hat{x}^{(n)}) = \sum_{i=1}^n (1-\frac{i}{n+1}) \frac{1}{n+1} = \frac{1}{(n+1)^2} \frac{n(n+1)}{2} = \frac{n}{2(n+1)}$$ is the optimal fraction of the $\$1$ million that can be won from the genie when making $n$ cuts. As $n \uparrow \infty,$ we get $\lim_{n\to \infty} Q_n(\hat{x}^{(n)}) = \lim_{n \to \infty} \frac{n}{2(n+1)} = \frac{1}{2},$ so you can win as close to $\$500,000$ as desired.