Robot Swimming Trials: Technical Note

Source repository: github.com/andrewikovic/robot-swimming-trials

Executive summary

This repository contains a notebook solution to Jane Street's first Robot Swimming Trials puzzle:

• Puzzle page: https://www.janestreet.com/puzzles/robot-swimming-trials-index/
• Published solution: https://www.janestreet.com/puzzles/robot-swimming-trials-solution/
• Local notebook: ../2021_10_RobotSwimmingTrials.ipynb

The answer is:

First exploitable number of races: N = 8
Qualification probability at N = 8: 0.334578325799579...
Benchmark probability: 1/3 = 0.333333333333333...
Advantage: 0.001244992466246...

To six significant digits, the exploit probability is:

p = 0.334578

The key strategy is simple. If the other 3N - 1 robots all use the old discrete strategy, meaning each opponent chooses one race uniformly at random and bids all fuel on that race, then our robot should spread fuel positively across every race. Under the original puzzle's exact-budget model, a clean legal choice is:

bid 1/N in every race

For N > 1, every one of our bids is strictly between 0 and 1. That means we lose any race that at least one opponent chose, because an opponent has bid 1 there. But in any race that no opponent chose, all opponents have bid 0, while our robot has bid 1/N > 0, so our robot wins that race outright.

Therefore the exploit succeeds exactly when the opponents leave at least one race empty. This turns the puzzle into a standard occupancy problem:

Throw m = 3N - 1 balls into N bins.
What is the first N for which at least one bin is empty with probability > 1/3?

The first such N is 8.

Problem restatement

There are:

• 3N robots.
• N swimming races.
• N final spots, one per race.
• One distinguished robot, "our robot".
• 3N - 1 opponents.

The historical strategy is discrete:

Choose one race uniformly at random.
Bid the entire fuel budget, 1, on that race.
Bid 0 on every other race.

The puzzle asks for the first value of N where our robot can do better than the symmetric benchmark by using a different strategy while all opponents continue using the discrete strategy.

The symmetric benchmark is:

This benchmark follows from exchangeability. If all robots use the same strategy, then each robot has the same probability of qualifying, and exactly N robots qualify. Hence the sum of all qualification probabilities is N, so each of the 3N identical robots qualifies with probability N / (3N) = 1/3.

The goal is therefore to find the smallest N such that a unilateral deviation gives:

Important legality note

The notebook describes the exploit as bidding a tiny positive epsilon in every race with:

That captures the essential idea: positive bids beat zero bids in empty races. However, the original puzzle states that a robot's submitted fuel allocation sums to exactly 1. Under that exact-budget model, the clean legal version is:

For every N >= 2, this allocation satisfies:

The same event controls success: our robot qualifies if and only if at least one race receives no all-in opponent.

More generally, any allocation with:

has the same success event against all-in opponents. The exact magnitudes do not matter, only the facts that every bid is positive and no bid is large enough to beat an opponent's all-in bid of 1.

Strategy behavior

Let C_i be the number of opponents who chose race i. Under the discrete strategy:

Our all-positive spread strategy bids:

There are two cases.

Case 1: Every race has at least one opponent

If C_i >= 1 for every race i, then every race has an opponent bid of 1. Since our bid is only 1/N < 1, our robot cannot win any race.

No empty race -> no qualification under the spread strategy

Case 2: At least one race has no opponents

If C_i = 0 for at least one race i, then every opponent bid in race i is 0. Our robot bid is 1/N > 0, so our robot wins that race outright.

At least one empty race -> qualification under the spread strategy

Tie-breaking is irrelevant for this exploit. In an empty race our robot does not tie opponents; it strictly beats their zero bids.

The qualification event is therefore:

and the exploit probability is:

Event diagram

An ASCII occupancy picture for N = 8:

Race:              1   2   3   4   5   6   7   8
Opponent count:    4   1   0   2   3   5   6   2
Our bid:          1/8 1/8 1/8 1/8 1/8 1/8 1/8 1/8

Race 3 is empty of all-in opponents.
All opponent bids in race 3 are 0.
Our bid in race 3 is 1/8.
Therefore our robot qualifies.

Why this is the right exploit

Against the opponents' all-in strategy, each opponent bid in any race is either 1 or 0.

For a non-discrete allocation where all of our bids are less than 1:

• We can never beat an occupied race, because an occupied race has a bid of 1.
• We can always beat an empty race if our bid in that race is positive.
• The exact positive value is irrelevant as long as it is below 1.

So, within the class of non-discrete strategies, it is best to bid positively on as many races as possible. Since a legal exact-budget allocation can make every race positive while keeping every bid below 1, the natural best spread strategy puts positive fuel on all N races.

This strategy guarantees qualification on the largest possible favorable event:

at least one of the N races is empty

For comparison, if our robot itself uses the old discrete strategy, then by symmetry its qualification probability is exactly 1/3. Therefore a profitable deviation exists exactly when:

Occupancy model

The opponents' random choices can be modeled as throwing:

independent labeled balls into:

labeled bins, where:

• each ball is one opponent;
• each bin is one race;
• a race is empty if no ball lands in its bin.

There are:

total assignments of opponents to races.

The desired probability is:

It is often easier to compute the complement:

Then:

Inclusion-exclusion derivation

Define:

We want:

For any fixed set S of j races, the event that every race in S is empty means all m opponents must choose among only the remaining N - j races. The probability of that event is:

There are:

sets S of size j.

By inclusion-exclusion:

Equivalently, the all-nonempty probability is:

and:

where:

Inclusion-exclusion diagram

The alternating signs are necessary because an assignment with multiple empty races is counted multiple times if we only subtract one-empty-race events.

Exact Python implementation

The notebook uses exact rational arithmetic through fractions.Fraction. That is the right choice because the threshold is close: for N = 8, the advantage over 1/3 is only about 0.001245.

from fractions import Fraction
from math import comb


def probability_at_least_one_empty(n_races: int) -> Fraction:
    """Exact probability that 3N - 1 all-in opponents leave a race empty."""
    balls = 3 * n_races - 1
    denominator = n_races ** balls

    all_nonempty = sum(
        Fraction(
            (-1) ** j * comb(n_races, j) * (n_races - j) ** balls,
            denominator,
        )
        for j in range(n_races + 1)
    )

    return 1 - all_nonempty

A compact threshold search:

from fractions import Fraction


def first_n_beating_one_third(limit: int = 100) -> tuple[int, Fraction]:
    benchmark = Fraction(1, 3)

    for n_races in range(1, limit + 1):
        p_empty = probability_at_least_one_empty(n_races)
        if p_empty > benchmark:
            return n_races, p_empty

    raise ValueError(f"No exploitable N found up to {limit}")


n_star, p_star = first_n_beating_one_third()
print(n_star)
print(float(p_star))

Expected output:

8
0.334578325799579

Complete standalone solver

This script is equivalent to the core notebook calculation, but can be run outside Jupyter.

#!/usr/bin/env python3

from fractions import Fraction
from math import comb


def probability_at_least_one_empty(n_races: int) -> Fraction:
    if n_races < 1:
        raise ValueError("n_races must be positive")

    balls = 3 * n_races - 1
    denominator = n_races ** balls

    all_nonempty = sum(
        Fraction(
            (-1) ** j * comb(n_races, j) * (n_races - j) ** balls,
            denominator,
        )
        for j in range(n_races + 1)
    )

    return 1 - all_nonempty


def first_exploitable_n(limit: int = 100) -> tuple[int, Fraction]:
    benchmark = Fraction(1, 3)

    for n_races in range(1, limit + 1):
        p = probability_at_least_one_empty(n_races)
        if p > benchmark:
            return n_races, p

    raise RuntimeError(f"No answer found through N={limit}")


def main() -> None:
    benchmark = Fraction(1, 3)

    print("N   P(empty)           P(empty) - 1/3")
    print("--  -----------------  ----------------")

    for n_races in range(1, 11):
        p = probability_at_least_one_empty(n_races)
        print(
            f"{n_races:2d}  "
            f"{float(p):.15f}  "
            f"{float(p - benchmark): .15f}"
        )

    n_star, p_star = first_exploitable_n()
    print()
    print(f"First exploitable N: {n_star}")
    print(f"Probability: {float(p_star):.15f}")
    print(f"Exact probability: {p_star}")
    print(f"Excess over 1/3: {float(p_star - benchmark):.15f}")


if __name__ == "__main__":
    main()

Exact threshold values

The threshold occurs between N = 7 and N = 8.

So:

and the first exploitable number of races is:

Numerical table

The following table shows the exact occupancy probability converted to decimal form.

N   opponents m=3N-1   q_N = P(at least one empty)   q_N - 1/3
--  ----------------   ---------------------------   -----------
 1          2           0.000000000000000            -0.333333333333333
 2          5           0.062500000000000            -0.270833333333333
 3          8           0.116598079561043            -0.216735253772291
 4         11           0.166011810302734            -0.167321523030599
 5         14           0.212092751872000            -0.121240581461333
 6         17           0.255367547996616            -0.077965785336717
 7         20           0.296128371882490            -0.037204961450843
 8         23           0.334578325799579             0.001244992466246
 9         26           0.370878363846351             0.037545030513017
10         29           0.405165722331272             0.071832388997938
11         32           0.437562285923272             0.104228952589939
12         35           0.468178850945680             0.134845517612346

This table is not a floating-point proof by itself. The proof comes from the exact rational comparisons:

from fractions import Fraction

benchmark = Fraction(1, 3)

p7 = probability_at_least_one_empty(7)
p8 = probability_at_least_one_empty(8)

assert p7 < benchmark
assert benchmark < p8
assert first_n_beating_one_third()[0] == 8

Alternative dynamic-programming check

Inclusion-exclusion is the shortest exact method, but an independent dynamic-programming count is a useful verification.

Let:

be the number of ways to place b labeled balls into k labeled bins with every bin nonempty.

The recurrence is:

Reason:

• If the last ball goes into a bin that was already nonempty, then the first b - 1 balls already occupied all k bins, and the last ball has k choices.
• If the last ball is the first ball in its bin, choose that bin in k ways, and the first b - 1 balls must occupy the other k - 1 bins.

Code:

from functools import cache
from fractions import Fraction


@cache
def onto_count(balls: int, bins: int) -> int:
    if balls == 0 and bins == 0:
        return 1
    if balls == 0 or bins == 0:
        return 0
    if balls < bins:
        return 0

    return bins * onto_count(balls - 1, bins) + bins * onto_count(balls - 1, bins - 1)


def probability_at_least_one_empty_dp(n_races: int) -> Fraction:
    balls = 3 * n_races - 1
    all_assignments = n_races ** balls
    all_nonempty_assignments = onto_count(balls, n_races)
    return 1 - Fraction(all_nonempty_assignments, all_assignments)

Verification against inclusion-exclusion:

for n_races in range(1, 20):
    assert probability_at_least_one_empty(n_races) == probability_at_least_one_empty_dp(n_races)

Stirling-number formulation

The same count can also be expressed with Stirling numbers of the second kind. The number of ways to place m labeled opponents into N labeled races with every race nonempty is:

where S(m, N) is the number of ways to partition m labeled objects into N nonempty unlabeled groups.

Thus:

and:

This is mathematically equivalent to the inclusion-exclusion formula because:

Monte Carlo sanity check

Simulation is not needed for the proof, but it is a useful check that the occupancy interpretation matches the intended event.

from random import Random


def simulate_empty_race_probability(
    n_races: int,
    trials: int = 100_000,
    seed: int = 202110,
) -> float:
    rng = Random(seed)
    balls = 3 * n_races - 1
    empty_count = 0

    for _ in range(trials):
        occupied = {rng.randrange(n_races) for _ in range(balls)}
        if len(occupied) < n_races:
            empty_count += 1

    return empty_count / trials


for n_races in (7, 8):
    simulated = simulate_empty_race_probability(n_races)
    exact = float(probability_at_least_one_empty(n_races))
    print(f"N={n_races}: simulation={simulated:.6f}, exact={exact:.6f}")

Typical output is close to:

N=7: simulation=0.296..., exact=0.296128
N=8: simulation=0.335..., exact=0.334578

Small discrepancies are expected because the simulation is random and uses a finite number of trials.

Common pitfalls

Pitfall 1: Treating empty-race events as independent

For a fixed race, the probability it is empty is:

For N = 8, this is:

But the events:

race 1 is empty
race 2 is empty
...
race N is empty

are not independent. If one race is empty, the opponents have been concentrated into fewer races, changing the probability that another race is empty.

Two tempting but incorrect approximations at N = 8 are:

The exact value is between them:

Inclusion-exclusion is the tool that correctly accounts for dependence.

Pitfall 2: Forgetting the -1 opponent

There are 3N total robots, but one of them is our deviating robot. Only the other robots are randomly choosing all-in races. Therefore the number of balls in the occupancy model is:

not 3N.

Using 3N changes the threshold calculation.

Pitfall 3: Relying on floating-point comparisons near the threshold

The threshold is close:

Standard floating-point arithmetic is fine for display, but exact rational arithmetic is cleaner for proving:

The notebook's use of Fraction avoids rounding ambiguity.

Pitfall 4: Thinking tie-breaking matters

Tie-breaking among opponents in occupied races can affect which opponent wins a particular occupied race, but it does not affect our exploit.

Our robot:

• loses occupied races because opponent bids there are 1;
• wins any empty race because our positive bid beats opponent bids of 0.

There is no tie involving our robot in the favorable event.

Complexity

The inclusion-exclusion implementation has:

time complexity:  O(N) arithmetic terms
space complexity: O(1) outside the size of big integers/rationals

The integers can become large because the calculation includes powers of the form:

For the threshold search here, this is tiny. Even exact rational arithmetic through N = 100 is straightforward in Python.

The dynamic-programming verification has roughly:

time complexity:  O(N * m) = O(N^2) because m = 3N - 1
space complexity: O(N * m)

It is slower and more memory-intensive than inclusion-exclusion for this problem, but it is conceptually useful as an independent check.

Minimal tests

A focused test suite should assert the exact threshold rather than merely printing decimals.

from fractions import Fraction


def test_threshold_is_eight() -> None:
    benchmark = Fraction(1, 3)

    assert probability_at_least_one_empty(7) < benchmark
    assert probability_at_least_one_empty(8) > benchmark
    assert first_n_beating_one_third()[0] == 8


def test_dp_matches_inclusion_exclusion() -> None:
    for n_races in range(1, 15):
        assert (
            probability_at_least_one_empty(n_races)
            == probability_at_least_one_empty_dp(n_races)
        )

If testing only the notebook logic, the most important assertions are:

assert first_n_beating_one_third()[0] == 8
assert probability_at_least_one_empty(7) < Fraction(1, 3)
assert probability_at_least_one_empty(8) > Fraction(1, 3)

Summary

The problem becomes simple once the opponent strategy is viewed as an occupancy process.

1. Opponents choose races uniformly and independently.
2. Our robot bids positively on every race, for example 1/N in each.
3. Our robot qualifies exactly when the opponents leave at least one race empty.
4. The empty-race probability is computed exactly by inclusion-exclusion.
5. The first N where this probability exceeds the symmetric benchmark 1/3 is N = 8.

Final answer:

N = 8
p = 0.334578325799579...