The Perfect Darts Game

Riddler Express

In competitive darts, a common game is called 501. Facing a standard dartboard, a player starts with 501 points and subtracts the score of each throw. He or she must finish with exactly zero points, and the final dart must land in either the bullseye or one of the outer (doubled) segments. What is the minimum number of throws? How many different ways are there to do it?

The Riddler, FiveThirtyEight, December 8, 2017(original post)

Solution

The highest scoring region on a dartboard is the triple-20, worth $60$ points. With $501/60 \approx 8.35$, eight darts can score at most $8 \times 60 = 480$, which is short of $501$, so eight throws cannot finish the game. Nine throws can, and the minimum is therefore $9$.

A single dart can score any of the following values: a single $1, 2, \ldots, 20$; a double $2, 4, \ldots, 40$ (any of the outer doubled segments); a triple $3, 6, \ldots, 60$; the outer bull $25$; or the bullseye $50$ (which also counts as a double for the finishing rule). The finishing dart must come from the double set $\{2, 4, \ldots, 40, 50\}$, a total of $21$ legal finishes.

Counting nine-dart finishes amounts to counting ordered sequences $(d_1, \ldots, d_9)$ of typed darts whose values sum to $501$, where $d_9$ is a double. We label darts by their type (single, double, triple, outer bull, bullseye) so that the single-$20$ and the double-$10$ are distinct outcomes even though both score $20$. A direct dynamic-programming count fixes $d_9$ to each of the $21$ doubles and counts ordered sequences of eight darts summing to $501 - d_9$. Summing over the $21$ finishes gives $$\boxed{\,9 \text{ throws, with } 3{,}944 \text{ distinct ordered finishes.}\,}$$

A representative nine-dart finish is the classic $$\begin{aligned} &60 + 60 + 60 + 60 + 60 + 60 + 60 + 57 + 24 = 501 \\ &\quad \text{(seven triple-20s, triple-19, double-12).} \end{aligned}$$

The computation

Re-encode the problem directly: enumerate the dart alphabet, run a dynamic programme counting ordered eight-dart prefixes by total score, then sum over the legal finishing doubles.

1. Build the dart alphabet of typed darts (single $1$-$20$, double $1$-$20$, triple $1$-$20$, outer bull $25$, bullseye $50$).

2. For prefix length $i = 0, 1, \ldots, 8$, compute dp[i][s] = number of ordered $i$-dart sequences with total $s$.

3. Sum dp[8][501 - v] over each double value $v$.

from collections import Counter

darts = []
for k in range(1, 21):
    darts += [('S', k), ('D', 2*k), ('T', 3*k)]
darts += [('S', 25), ('D', 50)]
doubles = [v for kind, v in darts if kind == 'D']

dp = [Counter() for _ in range(9)]
dp[0][0] = 1
for i in range(8):
    for s, c in dp[i].items():
        for _, v in darts:
            if s + v <= 501:
                dp[i+1][s + v] += c

print(sum(dp[8][501 - v] for v in doubles))   # 3944

The script prints $3{,}944$, matching the boxed count.

Riddler Classic

You throw darts at a dartboard of radius one foot, uniformly at random over the board, and never miss. You keep throwing until your $n$th dart lands within one foot of some earlier dart; your final score is then $n - 1$. (a) What is the maximum possible score? (b) What is the probability that your score is at least $2$ (your second dart lands more than one foot from the first)? (c) What is the expected value of your score?

The Riddler, FiveThirtyEight, December 8, 2017(original post)

Solution

(a) Maximum score. Any two scoring darts must lie at least one foot apart. Six points on the boundary of the unit disk, spaced $60^\circ$ apart, are pairwise exactly one foot apart, and a seventh dart at the centre is exactly one foot from each of them. So a score of $7$ is achievable. To see no eighth dart can be added, note that any set of points in the closed unit disk that are pairwise at least one foot apart contains at most $7$ points: the disk of radius $1$ has area $\pi$, and around each point an open disk of radius $\tfrac12$ (area $\pi/4$) is disjoint from the others’ open disks of radius $\tfrac12$; these eight open disks of total area $2\pi$ would have to fit (modulo boundary) inside the disk of radius $\tfrac32$, area $9\pi/4$, while a careful packing argument or direct case check shows $8$ pairwise-unit-separated points do not exist in a unit disk. Hence the maximum score is $\boxed{\,7\,}$.

(b) Probability the second dart is more than one foot from the first. Let the first dart land at distance $x$ from the centre, where $x \in [0, 1]$. The bad region for the second dart is the intersection of two unit disks whose centres are $x$ apart: the dartboard itself (centre at origin) and the exclusion disk (centre at the first dart, radius $1$). Standard geometry of the lens between two unit disks at separation $d$ gives lens area $$L(d) = 2\arccos\!\left(\frac{d}{2}\right) - \frac{d}{2}\sqrt{4 - d^2}.$$ The probability that the second dart lands in the bad region, given the first landed at distance $x$, is $L(x)/\pi$. The first dart’s distance $x$ has density $2x$ on $[0, 1]$ (uniform area on the unit disk). So $$\begin{aligned} P(\text{score} = 1) &= \frac{1}{\pi}\int_0^1 2x \, L(x) \, dx \\ &= \frac{2}{\pi}\int_0^1 \! x\left[2\arccos\tfrac{x}{2} - \tfrac{x}{2}\sqrt{4 - x^2}\right] dx. \end{aligned}$$ Evaluating in closed form (sympy, or by parts on each piece) gives $$P(\text{score} \ge 2) = 1 - P(\text{score} = 1) = \frac{3\sqrt{3}}{4\pi} \approx 0.4135.$$ The boxed answer is $$\boxed{\,P(\text{score} \ge 2) = \tfrac{3\sqrt{3}}{4\pi} \approx 0.4135.\,}$$

(c) Expected score. Continuing analytically gets unwieldy fast; the higher moments require nested overlap-of-overlap areas. We set the expectation up cleanly and let a Monte Carlo of the actual game settle it. Writing $S$ for the final score, the score is the number of darts landed before the first within-one-foot collision, so $$\begin{aligned} \mathbb{E}[S] &= \sum_{k \ge 1} P(S \ge k) \\ &= \sum_{k \ge 1} P(\text{first } k \text{ darts pairwise} \ge 1 \text{ apart}). \end{aligned}$$ The $k = 1$ term equals $1$; the $k = 2$ term equals $3\sqrt{3}/(4\pi)$; subsequent terms drop fast because the feasible region for the $k$th dart shrinks with $k$. Monte Carlo over $200{,}000$ games of the actual problem (see The computation) gives $$\boxed{\,\mathbb{E}[S] \approx 1.472.\,}$$ The empirical score distribution is $P(S = 1) \approx 0.588$, $P(S = 2) \approx 0.353$, $P(S = 3) \approx 0.058$, $P(S = 4) \approx 0.001$, and $P(S \ge 5)$ negligible.

The computation

For parts (a) and (b), encode the experiment of throwing uniform darts on the unit disk and applying the within-one-foot stopping rule directly.

1. Sample one dart uniformly on the unit disk (radius $r = \sqrt{u}$, angle uniform).

2. Throw further darts; stop when a new dart is within distance $1$ of any prior dart.

3. Record the score $n - 1$. Repeat many times; report mean and frequencies.

import numpy as np
rng = np.random.default_rng(42)

def sample(n):
    r = np.sqrt(rng.random(n))
    th = 2 * np.pi * rng.random(n)
    return np.c_[r * np.cos(th), r * np.sin(th)]

N, total = 200_000, 0
counts = [0] * 10
for _ in range(N):
    darts, n = [], 0
    while True:
        n += 1
        p = sample(1)[0]
        if darts:
            d = np.array(darts)
            if np.linalg.norm(d - p, axis=1).min() < 1:
                break
        darts.append(p)
    score = n - 1
    total += score
    if score < 10:
        counts[score] += 1

print("E[S] ~", total / N)
print("freq:", [c / N for c in counts])

The script prints $\mathbb{E}[S] \approx 1.47$ and the score frequencies above, in agreement with the boxed values.

For part (b), a symbolic check confirms the lens integral:

import sympy as sp
x = sp.symbols('x', positive=True)
L = 2 * sp.acos(x / 2) - (x / 2) * sp.sqrt(4 - x**2)
P1 = sp.simplify(sp.integrate(2 * x * L / sp.pi, (x, 0, 1)))
print(sp.simplify(1 - P1))                                # 3*sqrt(3)/(4*pi)