Intercepting Butterflies

We need send one of $2^{15}$ values through a set of universe size $20$, while one element may be inserted, deleted, or nothing happens.

A set over $\{1,\dots,20\}$ is just a 20-bit mask. Element $i$ is present iff bit $i$ is $1$. Adding or removing one element means flipping one bit. So the real problem is:

Encode 15 bits into 20 bits so that Bob can correct at most one bit flip.

That is a classic error-correcting-code job. Not spooky, just linear algebra wearing fake butterfly wings.

The Code We Need

We want $2^{15}$ valid masks. If every pair of valid masks has Hamming distance at least $3$, then any received mask within distance $1$ of a valid mask has a unique original. Distance $3$ is exactly the threshold for correcting one error.

Use a binary linear code with a $5 \times 20$ parity-check matrix $H$.

A 20-bit vector $c$ is valid when:

$$Hc = 0 \pmod 2.$$

The key trick is to choose the 20 columns of $H$ to be:

• nonzero,
• pairwise distinct,
• rank $5$ overall.

Then the code has dimension $20-5=15$, so exactly $2^{15}$ valid codewords. Perfect amount. Chef's kiss, but with XOR.

Why Pairwise Distinct Columns Matter

Suppose Alice sends a valid codeword $c$, so:

$$Hc = 0.$$

Bob receives $r$.

If nothing changed, then $r=c$, so:

$$Hr = 0.$$

If bit $i$ flipped, then:

$$r = c + e_i,$$

where $e_i$ is the vector with only bit $i$ set. Therefore:

$$Hr = H(c+e_i)=Hc+He_i=0+H_i=H_i,$$

where $H_i$ is column $i$ of $H$.

So the syndrome $Hr$ is either:

• $0$, meaning no change,
• column $i$, meaning bit $i$ was flipped.

Because every column is distinct, Bob can identify the bad bit exactly and flip it back.

Making Alice's Encoding Easy

We want a systematic construction, meaning the first 15 bits directly store the message, and the last 5 bits are parity.

Let positions $16,17,18,19,20$ have parity-check columns:

$$1,2,4,8,16$$

as 5-bit masks. These are the unit vectors.

For positions $1\dots15$, use the remaining nonzero 5-bit masks that are not unit vectors. There are exactly:

$$31 - 5 = 26$$

such masks, so picking 15 of them is easy.

Now encode a value $x$ by first converting it to a 15-bit message:

$$m = x-1.$$

For each message bit $i$ that is $1$, include position $i+1$ in the set and XOR its column into a running syndrome value.

At this point, the message bits alone have syndrome $s$. To make the full codeword valid, the 5 parity bits must contribute exactly $s$, because over $\mathbb{F}_2$:

$$s \oplus s = 0.$$

Since parity columns are $1,2,4,8,16$, we just set parity bit $j$ whenever bit $j$ of $s$ is $1$.

That gives Alice a valid 20-bit codeword.

Bob's Decoding

Bob reads the received set as a 20-bit mask $r$ and computes its syndrome:

$$s = Hr.$$

If $s=0$, the received mask is already valid.

Otherwise, $s$ must equal the column of the flipped bit. Bob finds that position and toggles it back.

Then the first 15 bits are the original message $m$, and the answer is:

$$x = m+1.$$

The second-run test cases may be shuffled, but this code does not care. Each set independently contains everything needed to recover its own $x$. No ordering assumptions, no hidden state, no nonsense.

Complexity

Each test case touches 20 positions, so the time is $O(20)$ and memory is $O(1)$. For $10^4$ tests, this is basically free.