IOAI Training: Learn AI by solving problems

The problem in brief

Pick a point $M$ uniformly at random inside an equilateral triangle $ABC$ whose area is 1. What is the average area of the smaller triangle $ABM$ ? The answer must be given as an exact fraction $a/b$ . It is a short exercise in expected values, with a neat symmetry shortcut and a direct integral that confirm each other.

How you are scored

The judge compares your fraction with the exact answer. There is no partial credit, so we check the result in two independent ways and with a Monte Carlo simulation.

The key idea

Reduce the area to a single random number. Take $AB$ as the base. Then

\text{area}(ABM) = \tfrac12\,\lvert AB\rvert \cdot d(M, AB), \qquad 1 = \text{area}(ABC) = \tfrac12\,\lvert AB\rvert \cdot h,

where $h$ is the height from $C$ . Dividing the two,

\text{area}(ABM) = \frac{d(M, AB)}{h} =: s \in [0, 1].

So we need the expected distance from a uniform point to the side $AB$ , measured in units of the height.

Shortcut by symmetry. For every point $M$ inside the triangle, the three small triangles $ABM$ , $BCM$ and $CAM$ tile $ABC$ , so

\text{area}(ABM) + \text{area}(BCM) + \text{area}(CAM) = 1 .

Take expectations. By linearity, $E[\text{area}(ABM)] + E[\text{area}(BCM)] + E[\text{area}(CAM)] = 1$ . The triangle is equilateral and $M$ is uniform, so a rotation by $120°$ maps the distribution of $M$ to itself and swaps the three small triangles: the three expectations are equal. Hence

E[\text{area}(ABM)] = \frac13 .

(Notice that only the symmetry between the three sides is used. For a non-equilateral triangle the answer is still $1/3$ : the computation below works for any triangle.)

Direct computation. The event $s > t$ means that $M$ lies above the line parallel to $AB$ at height $t h$ , that is inside a small triangle at the top, similar to $ABC$ with ratio $1-t$ . Its area is $(1-t)^2$ , so

P(s > t) = (1-t)^2, \qquad f_s(t) = 2(1-t) \ \text{ on } [0,1].

Then

E[s] = \int_0^1 P(s > t)\,dt = \int_0^1 (1-t)^2\,dt = \frac13 .

Equivalently, $E[s]$ is the height of the triangle's centroid above $AB$ divided by $h$ , which is the familiar $1/3$ : the mean of a uniform point is the centroid.

Left: uniform points coloured by the area of ABM, with the centroid's height h/3. Right: the area's distribution, density 2(1 - s), mean 1/3

The density is largest near 0: most of the triangle's surface lies close to its base, so small areas are the most likely, and the mean $1/3$ is well below the midpoint $1/2$ .

The full solution

The answer to print is

1/3

solution.py checks it in exact arithmetic ( $\int_0^1 2s(1-s)\,ds = 2(\tfrac12 - \tfrac13)$ with Python fractions) and by Monte Carlo. It samples 2 million uniform points in the triangle with the reflection trick: draw $u, v \sim U(0,1)$ , and if $u + v > 1$ replace them by $(1-u, 1-v)$ ; then $M = uB + vC$ (with $A$ at the origin) is uniform in $ABC$ .

Results

method	value
symmetry argument	$1/3$
integral of the tail $\int_0^1 (1-t)^2\,dt$	$1/3$
exact fractions in Python	`1/3`
Monte Carlo, $2\cdot 10^6$ points	$0.33362 \pm 0.00017$

What to remember

Linearity of expectation plus symmetry often gives the answer with no integral at all: split the quantity into pieces that add up to something known.
The tail formula $E[X] = \int_0^\infty P(X > t)\,dt$ for a non-negative $X$ is often easier than integrating against the density.
The mean of a uniform point is the centroid, so expected linear quantities (distances to a line, coordinates) are those of the centroid.
Check with Monte Carlo, and sample uniformly in a triangle with the reflection trick, not by rejection from a square.

"""FAIO 2024 qualification, problem B: Expected Value.

M uniform in an equilateral triangle ABC of area 1; E[area(ABM)] = ?   Answer: 1/3.

area(ABM) = |AB| * dist(M, AB) / 2 = dist(M, AB) / h  (because |AB| h / 2 = 1), so we need
E[dist(M, AB)] = h/3: the distance to a side is maximal (h) at C and the triangle's "mass" sits
near AB. Exactly: P(dist > t h) = (1 - t)^2 (similar triangle near C), density 2(1 - t), mean 1/3.

Run: python solution.py            (prints the answer, exact check and Monte Carlo check)
     python solution.py --figure
"""
import sys
from fractions import Fraction
import numpy as np


def exact():
    # E[s] with density 2(1 - s) on [0, 1]:  int_0^1 2 s (1 - s) ds = 2 (1/2 - 1/3) = 1/3
    return 2 * (Fraction(1, 2) - Fraction(1, 3))


def sample_triangle(n, rng):
    """Uniform points in the triangle A=(0,0), B=(side,0), C=(side/2, h) of area 1 (reflection trick)."""
    side = np.sqrt(4 / np.sqrt(3)); h = np.sqrt(3) / 2 * side
    u, v = rng.random(n), rng.random(n)
    flip = u + v > 1
    u[flip], v[flip] = 1 - u[flip], 1 - v[flip]
    B, C = np.array([side, 0.0]), np.array([side / 2, h])
    P = u[:, None] * B + v[:, None] * C
    return P, side, h


def monte_carlo(n=2_000_000, seed=0):
    rng = np.random.default_rng(seed)
    P, side, h = sample_triangle(n, rng)
    area = side * P[:, 1] / 2              # base AB on the x-axis, height = y
    return area.mean(), area.std() / np.sqrt(n), area


if __name__ == "__main__":
    print(exact())
    m, se, area = monte_carlo()
    print(f"Monte Carlo: {m:.5f} +- {se:.5f}  (exact {float(exact()):.5f})", file=sys.stderr)
    if "--figure" in sys.argv:
        import matplotlib
        matplotlib.use("Agg")
        import matplotlib.pyplot as plt
        rng = np.random.default_rng(1)
        P, side, h = sample_triangle(3000, rng)
        fig, ax = plt.subplots(1, 2, figsize=(12, 4.6))
        a = side * P[:, 1] / 2
        sc = ax[0].scatter(P[:, 0], P[:, 1], c=a, s=6, cmap="viridis")
        ax[0].plot([0, side, side / 2, 0], [0, 0, h, 0], "k-", lw=1.5)
        ax[0].axhline(h / 3, color="crimson", ls="--", lw=1.5)
        ax[0].text(side * 0.78, h / 3 + 0.03, "y = h/3\n(centroid)", color="crimson", fontsize=9)
        for nm, (x, y) in {"A": (0, 0), "B": (side, 0), "C": (side / 2, h)}.items():
            ax[0].annotate(nm, (x, y), textcoords="offset points", xytext=(-12 if nm == "A" else 6, -12 if nm != "C" else 4))
        ax[0].set_aspect("equal"); ax[0].set_title("3000 uniform points M, coloured by area(ABM)")
        fig.colorbar(sc, ax=ax[0], fraction=0.04, label="area(ABM)")
        ax[1].hist(area, bins=60, density=True, color="#9ecae1", label="Monte Carlo, 2 million points")
        t = np.linspace(0, 1, 100)
        ax[1].plot(t, 2 * (1 - t), "k-", lw=2, label="density 2(1 - s)")
        ax[1].axvline(1 / 3, color="crimson", ls="--", label="mean = 1/3")
        ax[1].set_xlabel("s = area(ABM)"); ax[1].set_ylabel("density"); ax[1].legend()
        ax[1].set_title("Small areas are the most likely")
        fig.tight_layout(); fig.savefig("figures/expected_area.png", dpi=150, facecolor="white")