Lamppost Toggle Cycle on a Square

Worked Solution

How to Think About It: This is a finite deterministic system -- the state space has $2^4 \times 4 = 64$ possible states (lamp states plus walker position). A deterministic map on a finite set must eventually cycle, so eventual periodicity is guaranteed by the pigeonhole principle. The real work is tracing the orbit from the initial state to find the period. The key mechanic: when the walker steps from position $P$ to the next position $Q$, if $L_P = 1$ then $L_Q$ flips; else $L_Q$ stays. The walker always moves clockwise regardless of lamp states -- the walk is deterministic and cyclic. With only 4 lamps and a deterministic rule, you can simulate it directly.

Quick Estimate: The full state must repeat within 64 steps (pigeonhole on 64 states), and a repeat of the initial state requires the walker back at $A$, so the period must be a multiple of 4 and at most 64. Beware the tempting guess of 16 ($4 \times 4$): the lamps alone return to all-on at step 15, but the walker is at $D$, not $A$ -- that is not a full-state repeat. Expect a period that is a multiple of 4, somewhere near the 64-state ceiling.

Approach: Pigeonhole gives periodicity for free; explicit simulation of the 64-state map finds the orbit and the minimal period.

Formal Solution:

(a) The dynamical system.

Let the lamps be $(L_A, L_B, L_C, L_D) \in \{0,1\}^4$ with 1 = on, and the walker position in $\{A,B,C,D\}$. The state space is

$$\boxed{S = \{0,1\}^4 \times \{A,B,C,D\}, \qquad |S| = 16 \times 4 = 64}$$

The update rule $f: S \to S$ is a well-defined deterministic function: given the current full state, the walker moves clockwise to the next position $Q$ from position $P$, and $L_Q$ flips if and only if $L_P = 1$.

(b) Explicit simulation of the orbit.

Label positions $A=0, B=1, C=2, D=3$ with clockwise steps. "Walker at $X$ after step $t$" means the walker just arrived at $X$. The walker position at step $t$ is $(t \bmod 4)$ after starting at $A=0$.

• Step 0 (start): Lamps $(1,1,1,1)$, walker at $A$. (No step yet; previous lamp undefined -- treat as first step below.)

For step $t \geq 1$: walker moves from position $t-1$ to position $t$ (mod 4). Check lamp at previous position; if on, toggle current.

• Step 1: Walk $A \to B$. Previous = $A$, $L_A = 1$: toggle $L_B$. $L_B: 1 \to 0$. State: $(1,0,1,1)$, at $B$.
• Step 2: Walk $B \to C$. Previous = $B$, $L_B = 0$: do nothing. State: $(1,0,1,1)$, at $C$.
• Step 3: Walk $C \to D$. Previous = $C$, $L_C = 1$: toggle $L_D$. $L_D: 1 \to 0$. State: $(1,0,1,0)$, at $D$.
• Step 4: Walk $D \to A$. Previous = $D$, $L_D = 0$: do nothing. State: $(1,0,1,0)$, at $A$.
• Step 5: Walk $A \to B$. Previous = $A$, $L_A = 1$: toggle $L_B$. $L_B: 0 \to 1$. State: $(1,1,1,0)$, at $B$.
• Step 6: Walk $B \to C$. Previous = $B$, $L_B = 1$: toggle $L_C$. $L_C: 1 \to 0$. State: $(1,1,0,0)$, at $C$.
• Step 7: Walk $C \to D$. Previous = $C$, $L_C = 0$: do nothing. State: $(1,1,0,0)$, at $D$.
• Step 8: Walk $D \to A$. Previous = $D$, $L_D = 0$: do nothing. State: $(1,1,0,0)$, at $A$.
• Step 9: Walk $A \to B$. Previous = $A$, $L_A = 1$: toggle $L_B$. $L_B: 1 \to 0$. State: $(1,0,0,0)$, at $B$.
• Step 10: Walk $B \to C$. Previous = $B$, $L_B = 0$: do nothing. State: $(1,0,0,0)$, at $C$.
• Step 11: Walk $C \to D$. Previous = $C$, $L_C = 0$: do nothing. State: $(1,0,0,0)$, at $D$.
• Step 12: Walk $D \to A$. Previous = $D$, $L_D = 0$: do nothing. State: $(1,0,0,0)$, at $A$.
• Step 13: Walk $A \to B$. Previous = $A$, $L_A = 1$: toggle $L_B$. $L_B: 0 \to 1$. State: $(1,1,0,0)$, at $B$.
• Step 14: Walk $B \to C$. Previous = $B$, $L_B = 1$: toggle $L_C$. $L_C: 0 \to 1$. State: $(1,1,1,0)$, at $C$.
• Step 15: Walk $C \to D$. Previous = $C$, $L_C = 1$: toggle $L_D$. $L_D: 0 \to 1$. State: $(1,1,1,1)$, at $D$.
• Step 16: Walk $D \to A$. Previous = $D$, $L_D = 1$: toggle $L_A$. $L_A: 1 \to 0$. State: $(0,1,1,1)$, at $A$.
• Step 17: Walk $A \to B$. Previous = $A$, $L_A = 0$: do nothing. State: $(0,1,1,1)$, at $B$.
• Step 18: Walk $B \to C$. Previous = $B$, $L_B = 1$: toggle $L_C$. $L_C: 1 \to 0$. State: $(0,1,0,1)$, at $C$.
• Step 19: Walk $C \to D$. Previous = $C$, $L_C = 0$: do nothing. State: $(0,1,0,1)$, at $D$.
• Step 20: Walk $D \to A$. Previous = $D$, $L_D = 1$: toggle $L_A$. $L_A: 0 \to 1$. State: $(1,1,0,1)$, at $A$.

Continuing this simulation (tracking full states including walker position) is the reliable method. The orbit is deterministic, and given the finite state space of 64 states, periodicity must occur within 64 steps. The configuration after $N$ steps is the orbit value at position $N \bmod 60$ once the period (established in part (c)) is known; the table above gives the configuration for each of the early steps.

(c) Periodicity proof and minimal period.

Claim: The process is eventually periodic.

Proof: The state space is $S = \{0,1\}^4 \times \{A,B,C,D\}$, which has $|S| = 64$ elements. The update rule $f: S \to S$ is a well-defined deterministic function (given the current full state, the next state is uniquely determined). The sequence of states $s_0, s_1 = f(s_0), s_2 = f(s_1), \ldots$ must eventually revisit a state (by the pigeonhole principle, within the first 65 steps). Once a state repeats, the sequence is periodic from that point onward. $\square$

Minimal period: The full simulation (which can be completed by hand or computer within the 64-state bound) determines the minimal period by tracking when the full state $(L_A, L_B, L_C, L_D, \text{walker})$ first repeats. A complete simulation reveals that the orbit returns to the initial state $(1,1,1,1)$ with the walker at $A$ for the first time after exactly $p = 60$ steps (15 full circuits of the square), with no earlier repeat of any full state -- so there is no transient, and the minimal period is

$$\boxed{p = 60}$$

Note this is $60$, not $16$: the lamp configuration alone hitting all-on at step 15 (walker at $D$) does not close the orbit, because the walker position is part of the state.

Answer: The state space is $\{0,1\}^4 \times \{A,B,C,D\}$ with 64 total states. The configuration after $N$ steps follows the explicit orbit computed by simulation (tabulated above for early steps), repeating with period 60. The process is eventually periodic by pigeonhole on the finite state space; the orbit from all-on/walker-at-$A$ has no transient, and the minimal period is $\boxed{60}$.