---
date: '2025-12-16'
description: a campaign from UK Government
id: sota-number-10
modified: 2026-06-05 15:08:11 GMT-04:00
socials:
  substack: https://sotaletters.substack.com/p/a-message-from-number-10
tags:
  - hiring
  - puzzle
title: a letter from 10 Downing Street
created: '2025-12-16'
published: '2025-12-16'
pageLayout: default
slug: puzzle/sota-number-10
permalink: https://aarnphm.xyz/puzzle/sota-number-10.md
generator:
  quartz: v4.6.0
  hostedProvider: Cloudflare
  baseUrl: aarnphm.xyz
full: https://aarnphm.xyz/llms-full.txt
---
> \[!question\] Question
>
> Ben and Lily play a game where they alternate picking pairs of numbers (A, B) where A and B are integers between 1 and 12. On his go Ben picks a pair, whereas Lily gets to pick two pairs on each of her goes. However, the two pairs she picks must be in one of these forms:
>
> (A,B), (A,B+1)
>
> (A,B), (A,B-1)
>
> (A,B), (A+1,B)
>
> (A,B), (A-1,B)
>
> Any given pair (A,B) may only be picked once, and once one player has picked it the other player may not pick it. They keep playing until one player cannot go.
>
> If Lily plays well, how many pairs of numbers can she end up with, regardless of how Ben plays?

## solution

We can convert this into a $12 \times 12$ grid of pairs $(A,B)$ is a graph where:

- ben removes 1 cell per turn
- lily removes 2 adjacent cells (a domino) per turn
- game ends when lily can’t find adjacent cells

this is an _adversarial [[thoughts/domino tiling]]_ problem.

### the checkerboard invariant

color cells $(i,j)$ where $i+j \equiv 0 \pmod 2$ as “white”, others “black”. we get 72 white, 72 black cells.

note: every domino spans exactly <mark>1 white + 1 black</mark> cell (adjacent cells always differ in color).

### ben’s optimal strategy

ben targets one color class (say white). after round $k$:

$$
\begin{aligned}
\text{white\_remaining} &= 72 - k_{\text{lily}} - k_{\text{ben}} = 72 - 2k \\
\text{black\_remaining} &= 72 - k_{\text{lily}} = 72 - k \\
\end{aligned}
$$

white exhausts when $72 - 2k = 0$, i.e., $k = 36$.

at that point, 36 black cells remain. but black cells are mutually <span class="marker marker-h2">NON-ADJACENT</span> (checkerboard property)—the remaining graph has no edges.

therefore, lily can’t move.

> \[!tip\] Important
>
> For the game to end at round $k$, remaining cells must form an independent set. in a checkerboard grid, max independent set is 72 (i.e: one color class)

thus, ben needs to exhaust one color. he contributes $k$ picks; lily contributes $k$ (forced). to exhaust 72 whites: $2k \geq 72 \Rightarrow k \geq 36$.

so round 36 is the earliest possible end. Here, lily gets $36 \times 2 = 72$ cells.

lily’s domino constraint forces her to remove 1 white + 1 black each turn. she cannot slow down white depletion against ben’s targeting strategy, therefore the minmax value would be $12 \times  12 / 2 = 72$

```python title="ten\_downing.py" path="puzzle/ten\_downing.py"
from __future__ import annotations

import random, typing as t

type Cell = tuple[int, int]
type Color = t.Literal['white', 'black']

GRID_SIZE = 12


def color(cell: Cell) -> Color:
  return 'white' if (cell[0] + cell[1]) % 2 == 0 else 'black'


def neighbors(cell: Cell) -> list[Cell]:
  i, j = cell
  return [
    (x, y)
    for x, y in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]
    if 1 <= x <= GRID_SIZE and 1 <= y <= GRID_SIZE
  ]


def find_domino(remaining: set[Cell]) -> tuple[Cell, Cell] | None:
  for cell in remaining:
    for neighbor in neighbors(cell):
      if neighbor in remaining:
        return (cell, neighbor)


def simulate_optimal() -> int:
  r = {
    (i, j) for i in range(1, GRID_SIZE + 1) for j in range(1, GRID_SIZE + 1)
  }
  lily = 0

  while True:
    whites = [c for c in r if color(c) == 'white']
    if not whites:
      break
    ben = whites[0]
    r.remove(ben)

    domino = find_domino(r)
    if domino is None:
      break
    r.remove(domino[0])
    r.remove(domino[1])
    lily += 2
  return lily


def simulate_random(seed: int = 42) -> int:
  random.seed(seed)
  r = {
    (i, j) for i in range(1, GRID_SIZE + 1) for j in range(1, GRID_SIZE + 1)
  }
  lily = 0

  while r:
    ben = random.choice(list(r))
    r.remove(ben)

    domino = find_domino(r)
    if domino is None:
      break
    r.remove(domino[0])
    r.remove(domino[1])
    lily += 2

  return lily


if __name__ == '__main__':
  print(f'optimal: {simulate_optimal()}')
  print(
    f'randoms: min={min(random_results := [simulate_random(seed=s) for s in range(100)])}, max={max(random_results)}, avg={sum(random_results) / len(random_results):.1f}'
  )

```