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.

Centered triangles

Suppose you have an equilateral triangle. You pick three random points, one along each of its three edges, uniformly along the length of each edge — that is, each point along each edge has the same probability of being selected.

With those three randomly selected points, you can form a new triangle inside the original one. What is the probability that the center of the larger triangle also lies inside the smaller one?

Let's assume that the original triangle is the equilateral triangle with side lengths whose center is at the origin of the $xy$-plane. Thus the vertices of the original triangle are at $A(-1/2, -\sqrt{3}/4)$, $B(0,\sqrt{3}/4)$, and $C(1/2, -\sqrt{3}/4).$ Let's say that $t, u, v \sim U(0,1)$ are i.i.d. uniformly distributed, then the random points along the edges of \Delta ABC can be modeled as $$\begin{align*} X &= \left(t - \frac{1}{2}, -\frac{\sqrt{3}}{4}\right) \\ Y &= \left(-\frac{1-u}{2}, \frac{\sqrt{3}(2u-1)}{4}\right) \\ Z &= \left(\frac{1-v}{2}, \frac{\sqrt{3}(2v-1)}{4} \right).\end{align*}$$

If we wanted to just brute force our way into the solution, we could just use the test that $O = (0,0) \in \Delta XYZ$ if and only if $$A_{\Delta OXY} + A_{\Delta OXZ} + A_{\Delta OYZ} = A_{\Delta XYZ}.$$ However, we can also create the appropriate integral to calculate the theoretical answer. In this case, we will actually do both to make sure both are roughly on the right track.

Let's first focus on the siutation when $t \in \left[0,\frac{1}{2}\right],$ or equivalently when $X \in \mathbb{R}_- \times \{ -\frac{\sqrt{3}}{4} \}.$ In this case, we can drawn a line from $X$ through the origin $O$ and see that if $O$ is in the $\Delta XYZ$ then we must have $Z = (z_1, z_2)$ located such that $$\frac{\sqrt{3}}{4} z_1 + \left( t - \frac{1}{2}\right) z_2 \geq 0.$$ Therefore, in terms of $t$ and $v,$ we have $$\begin{align*} 0 & \leq \frac{\sqrt{3}}{4} \frac{1-v}{2} + \left(t-\frac{1}{2}\right) \frac{\sqrt{3} (2v-1)}{4}\\ &= \frac{\sqrt{3}}{8} \Big( 1- v + (2t-1) (2v - 1) \Big)\\ &= \frac{\sqrt{3}}{8} \left( (4t-3) v + 2(1 - t)\right),\end{align*}$$ or equivalently $$v \leq \frac{2(1-t)}{3-4t}.$$ See the figure below for context.

Similarly, we can draw a line from $Y$ through the origin $O$ and see that if $O$ is in the triangle $\Delta XYZ$ then we must have $Z = (z_1, z_2)$ located such that $$\frac{\sqrt{3}}{4} (2u-1) z_1 + \frac{1-u}{2} z_2 \geq 0.$$ Therefore, in terms of $u$ and $v,$ we have $$\begin{align*} 0 &\leq \frac{\sqrt{3} (2u-1)}{4} \frac{1-v}{2} + \frac{1-u}{2} \frac{\sqrt{3} (2v-1)}{4} \\ &= \frac{\sqrt{3}}{8} \Big( (2u-1) (1-v) + (1-u) (2v-1) \Big) \\ &= \frac{\sqrt{3}}{8} \Big( (3u - 2) + (3 - 4u) v \Big),\end{align*}$$ or equivalently $$v \geq \frac{2 - 3u}{3-4u}.$$ Since we naturally have $v \in [0,1],$ we see that if $t \in \left[ 0, \frac{1}{2} \right]$ and $u \in [0,1]$ that O is in the triangle $\Delta XYZ$ if and only if $$v \in \left[ 0 \vee \frac{2-3u}{3-4u}, \frac{2(1-t)}{3-4t} \right].$$ So $$\begin{align*}\mathbb{P} \left\{ O \in \Delta XYZ \Big| X \in \mathbb{R}_- \times \{ -\frac{\sqrt{3}}{4} \} \right\} &= \int_0^{\frac{1}{2}} \int_0^1 \frac{2(1-t)}{3-4t} - \max \{ 0, \frac{2-3u}{3-4u} \} \,du \,dt \\ &= \int_0^{\frac{1}{2}} \left(\frac{2(1-t)}{3-4t} - \int_0^{\frac{2}{3}} \frac{2-3u}{3-4u} \,du\right) \,\, dt.\end{align*}$$ Using partial fractions, we get $$\int_0^{\frac{2}{3}} \frac{2-3u}{3-4u} \,du = \int_0^{\frac{2}{3}} \frac{3}{4} - \frac{1}{4(3-4u)} \,du = \left[ \frac{3}{4} u + \frac{1}{16} \ln \left| 3 - 4u \right| \right]^{\frac{2}{3}}_0 = \frac{1}{2} - \frac{1}{8} \ln 3.$$ So, again by applying the partial fractions technique we get that the probability is $$\begin{align*}\mathbb{P} \left\{ O \in \Delta XYZ \Big| X \in \mathbb{R}_- \times \{ -\frac{\sqrt{3}}{4} \} \right\} &= \int_0^{\frac{1}{2}} \frac{2(1-t)}{3-4t} - \frac{1}{2} + \frac{1}{8} \ln 3 \,dt \\ &= \int_0^{\frac{1}{2}} \frac{1}{2} + \frac{1}{2(3-4t)} - \frac{1}{2} + \frac{1}{8} \ln 3 \,dt\\ &= \left[ -\frac{1}{8} \ln \left| 3 - 4t \right| + \frac{t}{8} \ln 3 \right]^{\frac{1}{2}}_0 = \frac{3 \ln 3}{16}.\end{align*}$$

From symmetry (by switching the restrictions of $Y$ and $Z$ whenever $t \in \left[\frac{1}{2}, 1\right]$), we see that $$\mathbb{P} \left\{ O \in \Delta XYZ \Big| X \in \mathbb{R}_+ \times \{ -\frac{\sqrt{3}}{4} \} \right\} = \mathbb{P} \left\{ O \in \Delta XYZ \Big| X \in \mathbb{R}_- \times \{ -\frac{\sqrt{3}}{4} \} \right\} = \frac{3 \ln 3}{16},$$ so we are left with the probability that the origin is in the randomly selected triangle $\Delta XYZ$ as $$\begin{align*}\mathbb{P} \left\{ O \in \Delta XYZ \right\} &= \mathbb{P} \left\{ O \in \Delta XYZ \Big| X \in \mathbb{R}_-\times \{ -\frac{\sqrt{3}}{4} \} \right\} + \mathbb{P} \left\{ O \in \Delta XYZ \Big| X \in \mathbb{R}_+ \times \{ -\frac{\sqrt{3}}{4} \} \right\}\\ &= \frac{3 \ln 3}{8} \approx 0.41197960825.... .\end{align*}$$

As indicated, we can also use brute force to arrive at / verify this conclusion using the short python script shown below.

In [1]:

import numpy as np
from numpy.random import uniform

def area_triangle(A, B, C):
    cross = (B[0] - A[0]) * (C[1] - A[1]) - (C[0] - A[0]) * (B[1] - A[1])
    return 0.5 * np.abs(cross)

num_samples = 1000
num_runs = 1000
O = np.array([0.,0.])
success = np.zeros(shape=(num_samples, num_runs))
for k in range(num_runs):
    U = uniform(size=(num_samples, 3))
    for i in range(num_samples):
        u = U[i,:]
        X = np.array([-0.5, -0.25*np.sqrt(3)]) + u[0] * np.array([ 1.0, 0.0])
        Y = np.array([-0.5, -0.25*np.sqrt(3)]) + u[1] * np.array([ 0.5, 0.5 * np.sqrt(3)])
        Z = np.array([ 0.5, -0.25*np.sqrt(3)]) + u[2] * np.array([-0.5, 0.5 * np.sqrt(3)])
        a1 = area_triangle(O, X, Y)
        a2 = area_triangle(O, X, Z)
        a3 = area_triangle(O, Y, Z)
        a = area_triangle(X, Y, Z)
        if np.abs(a - a1 - a2 - a3) < 1e-6:
            success[i,k] += 1
print('Over %d successive tests, each using %d samples, the probability of having the origin within ' % (num_runs, num_samples))
print('the random triangle is %f with SEM of %f.' % (success.mean(), success.mean(axis=0).std()/np.sqrt(num_runs)))
print('This compares favorably to the theoretical answer 3 * ln(3) / 8 = %f' %  (3. * np.log(3) / 8.))

Over 1000 successive tests, each using 1000 samples, the probability of having the origin within 
the random triangle is 0.411384 with SEM of 0.000495.
This compares favorably to the theoretical answer 3 * ln(3) / 8 = 0.411980