Prisoner Challenge
Ternary narrowing Each whiteboard state encodes a pair (which bag to inspect next, current uncertainty interval [, r]). Initially [, r] = [1, N]. The prisoner inspects the designated bag and sees value v: If v <: the...
Problem Statement
Rendered from the "Problem Statement" section in the LaTeX write-up.
Two bags contain $a$ and $b$ coins respectively, where $1 \le a, b \le N$ and $a \ne b$. Prisoners enter one at a time, read a whiteboard value in $\{0, 1, \ldots, x\}$ (initially 0), then either:
inspect bag A or bag B (learning the coin count), then
guess which bag has fewer coins, or write a new value to the whiteboard and pass.
Design a strategy table so that eventually some prisoner guesses correctly. Minimize the whiteboard range $x$.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Ternary narrowing
Each whiteboard state encodes a pair (which bag to inspect next, current uncertainty interval $[\ell, r]$). Initially $[\ell, r] = [1, N]$.
The prisoner inspects the designated bag and sees value $v$:
If $v < \ell$: the inspected bag has fewer (the other bag's value lies in $[\ell, r]$, so $v < \ell \le \text{other}$).
If $v > r$: the other bag has fewer.
Otherwise partition $[\ell, r]$ into three roughly equal parts. If $v$ falls in the bottom third, guess the inspected bag is smaller. If in the top third, guess the other bag is smaller. If in the middle third, write a new state (toggle the bag, narrow to the middle third) and pass.
After at most $\lceil \log_3 N \rceil$ rounds the interval shrinks to a single value and a guess is forced.
Theorem.
The strategy is correct. The uncertainty interval strictly shrinks by a factor of at least 3 in each pair of rounds, so termination is guaranteed within $2\lceil \log_3 N \rceil$ states.
Proof.
When a prisoner sees value $v$ in the middle third and passes, the new interval $[\ell', r']$ satisfies $r' - \ell' + 1 \le \lceil(r - \ell + 1)/3\rceil$. The unseen bag's value also lies in $[\ell, r]$ (by the invariant), and since $a \ne b$, the unseen value differs from $v$. After toggling, the next prisoner inspects the other bag. If the other bag's value falls outside $[\ell', r']$, a correct guess is made immediately. Otherwise the interval narrows further.
Number of states
We need $2 \lceil \log_3 N \rceil$ states (factor 2 for alternating between bags A and B). Thus $x = 2\lceil \log_3 N \rceil - 1$. For $N = 5000$, $\lceil \log_3 5000 \rceil = 8$, giving $x = 15$.
Complexity
Whiteboard range: $x = 2\lceil\log_3 N\rceil - 1$.
Strategy table size: $O(x \cdot N)$.
Correctness: guaranteed by the ternary-narrowing invariant; every pair $(a,b)$ with $a \ne b$ is resolved within $x + 1$ prisoner visits.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> devise_strategy(int N) {
// Strategy table: s[i][j] for whiteboard state i, coin count j
// s[i][0] = which bag to inspect (0=A, 1=B)
// s[i][j] for j=1..N: action after seeing j coins
// value -1: guess this bag (the inspected one) has fewer
// value -2: guess the other bag has fewer
// value >= 0: write this value to whiteboard
// Ternary search approach
// State encodes (depth, which_bag_last_seen)
// At each depth, the range is narrowed by factor of 3
// Compute number of states needed
int depth = 0;
{
int range = N;
while (range > 1) {
range = (range + 2) / 3; // ceiling division
depth++;
}
}
// Total states: 2 * depth (alternating A and B)
// But we also need a state for each (depth, bag) pair
int num_states = 0;
// Each state: (level, inspecting_bag)
// level 0: full range [1, N], inspect A
// level 1: narrowed range, inspect B
// level 2k: inspect A, level 2k+1: inspect B
// Precompute ranges for each level
vector<pair<int,int>> ranges; // (lo, hi) at each level
ranges.push_back({1, N});
int lo = 1, hi = N;
while (hi - lo > 0) {
int len = hi - lo + 1;
int third = (len + 2) / 3;
lo = lo + third;
hi = hi - third;
if (lo > hi) break;
ranges.push_back({lo, hi});
}
num_states = 2 * ranges.size();
// Actually, let me reconsider. The number of states is the number of levels.
// Each level alternates which bag to inspect.
int max_level = ranges.size();
vector<vector<int>> strategy(2 * max_level, vector<int>(N + 1, 0));
for (int level = 0; level < max_level; level++) {
int state_A = 2 * level; // inspect A at this level
int state_B = 2 * level + 1; // inspect B at this level
int lo_range = ranges[level].first;
int hi_range = ranges[level].second;
int len = hi_range - lo_range + 1;
int third = max(1, (len + 2) / 3);
int cut1 = lo_range + third - 1; // end of bottom third
int cut2 = hi_range - third + 1; // start of top third
if (cut2 <= cut1) cut2 = cut1 + 1;
// State for inspecting A:
strategy[state_A][0] = 0; // inspect bag A
for (int v = 1; v <= N; v++) {
if (v < lo_range) {
strategy[state_A][v] = -1; // A is definitely smaller
} else if (v > hi_range) {
strategy[state_A][v] = -2; // B is definitely smaller
} else if (v <= cut1) {
strategy[state_A][v] = -1; // A in bottom third -> A is smaller
} else if (v >= cut2) {
strategy[state_A][v] = -2; // A in top third -> B is smaller
} else {
// Middle third: transition to next level, inspect B
if (level + 1 < max_level && 2 * level + 1 < (int)strategy.size())
strategy[state_A][v] = state_B;
else
strategy[state_A][v] = -1; // fallback
}
}
// State for inspecting B:
strategy[state_B][0] = 1; // inspect bag B
for (int v = 1; v <= N; v++) {
if (v < lo_range) {
strategy[state_B][v] = -2; // B is smaller
} else if (v > hi_range) {
strategy[state_B][v] = -1; // A is smaller
} else if (v <= cut1) {
strategy[state_B][v] = -2; // B in bottom third -> B is smaller
} else if (v >= cut2) {
strategy[state_B][v] = -1; // B in top third -> A is smaller
} else {
// Middle third: transition to next level, inspect A
if (level + 1 < max_level)
strategy[state_B][v] = 2 * (level + 1);
else
strategy[state_B][v] = -2; // fallback
}
}
}
return strategy;
}
int main() {
int N;
scanf("%d", &N);
auto strat = devise_strategy(N);
printf("x = %d\n", (int)strat.size() - 1);
for (int i = 0; i < (int)strat.size(); i++) {
printf("State %d (inspect %c):", i, strat[i][0] == 0 ? 'A' : 'B');
for (int j = 1; j <= min(N, 20); j++)
printf(" %d", strat[i][j]);
printf("\n");
}
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.