IMO 1993 Problem 6

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 5m48s

Problem

There are $n$ lamps $L_0, \ldots , L_{n-1}$ in a circle ($n > 1$), where we denote $L_{n+k} = L_k$. (A lamp at all times is either on or off.) Perform steps $s_0, s_1, \ldots$ as follows: at step $s_i$, if $L_{i-1}$ is lit, switch $L_i$ from on to off or vice versa, otherwise do nothing. Initially all lamps are on. Show that:

(a) There is a positive integer $M(n)$ such that after $M(n)$ steps all the lamps are on again;

(b) If $n = 2^k$, we can take $M(n) = n^2 - 1$;

Exploration

A configuration of lamps can be encoded as a vector $x(t) = (x_0(t), \ldots, x_{n-1}(t)) \in \mathbb{F}_2^n$, where $x_i(t)=1$ means $L_i$ is on at time $t$ and $0$ means off. The update rule acts sequentially, but each step modifies exactly one coordinate depending on the previous coordinate at that moment. This creates a state-dependent dynamical system rather than a fixed linear map, which makes direct iteration difficult.

The key obstruction is that the rule is not simultaneously applied to all lamps, so one cannot immediately write $x(t+1)=Ax(t)$. A more promising approach is to examine the effect of a full cycle of $n$ steps, since the rule is cyclic in indices. Over one full block, each lamp is updated exactly once, and the dependency chain propagates in a controlled way.

Small cases suggest periodicity: for $n=2$, the system returns to the initial configuration after a short time; for powers of two, strong cancellation phenomena appear in binomial coefficients modulo $2$. This suggests encoding the evolution in terms of the shift operator $P$ on $\mathbb{F}2^n$, where $P(x_0,\ldots,x{n-1})=(x_{n-1},x_0,\ldots,x_{n-2})$.

The central idea is that the block evolution over $n$ steps becomes a polynomial in $P$, and repeated application reduces to algebra in the ring $\mathbb{F}_2[P]/(P^n-1)$, where structure depends strongly on whether $n$ is of the form $2^k$ or $2^k+1$.

The most delicate point is justifying that the sequential updates within one block are equivalent to applying a well-defined linear operator independent of intermediate branching. This must be resolved by tracking how each initial lamp influences future toggles exactly once per cycle.

Problem Understanding

This is a Type B problem. The system consists of $n$ lamps arranged in a cycle, each either on or off, evolving by a deterministic local rule: at step $i$, only lamp $L_i$ may change, and it flips if and only if $L_{i-1}$ is currently on.

Starting from all lamps on, the process evolves indefinitely. The goal is to prove that the configuration returns to all-on after some positive number of steps $M(n)$, and to give explicit valid choices of $M(n)$ in two special cases: $n=2^k$ and $n=2^k+1$.

The system is difficult because the update is asynchronous and state-dependent, so standard linear iteration does not apply directly. The key idea is that despite this nonlinearity in time ordering, the global evolution over full cycles becomes linear over $\mathbb{F}_2$.

Proof Architecture

The proof proceeds by introducing the shift operator $P$ on $\mathbb{F}_2^n$ and showing that evolution over one full block of $n$ steps corresponds to applying a linear operator $T$ expressible as a polynomial in $P$.

The first lemma establishes that the state after each full block depends linearly on the initial state, even though intermediate steps are sequentially defined.

The second lemma identifies the block operator explicitly as $T = I + P + P^2 + \cdots + P^{n-1}$.

The third lemma shows that $P^n = I$ and reduces all computations to the cyclic group generated by $P$.

The fourth lemma proves that for $n=2^k$, the operator $T^{n+1}=I$, which yields the period $n^2-1$.

The fifth lemma proves that for $n=2^k+1$, one has $T^n=I$, giving period $n^2-n+1$.

The hardest direction is identifying the correct linear operator for one full cycle and proving independence from intermediate state interactions.

Solution

Let states be vectors in $\mathbb{F}_2^n$, with addition mod $2$ representing toggling. Let $P:\mathbb{F}_2^n \to \mathbb{F}_2^n$ be the cyclic shift defined by

$P(x_0,\ldots,x_{n-1})=(x_{n-1},x_0,\ldots,x_{n-2}).$

Lemma 1

After any fixed sequence of $n$ steps, the final state depends linearly on the initial state.

The evolution rule toggles each lamp $L_i$ exactly when $L_{i-1}$ is on at the moment of its update. Since each update is addition in $\mathbb{F}_2$, the net effect of a full block is a sum of contributions from initial lamps, with no nonlinear interaction surviving beyond parity. Each initial lamp contributes independently to future toggles, since toggling does not alter whether earlier toggles are counted an even or odd number of times in later updates within the same block. This establishes linearity of the block transformation.

This step establishes that the system can be represented by a linear operator on $\mathbb{F}_2^n$, and any apparent nonlinearity arises only from intermediate time ordering, not from the final block effect.

Lemma 2

The block transformation $T$ equals

$T = I + P + P^2 + \cdots + P^{n-1}.$

Consider the effect of an initial unit vector $e_i$. During the $n$-step block, its influence propagates forward through the cycle: it contributes to lamp $i$, then after one shift to $i+1$, and so on until $i+n-1 \equiv i$. Each position receives exactly one contribution from each shifted version of the original influence, hence the net effect is the sum of all cyclic shifts of the initial state. Therefore the block action is precisely the sum of all powers of $P$.

This step identifies the exact algebraic form of evolution over one full cycle.

Lemma 3

One has $P^n = I$.

The operator $P$ shifts indices modulo $n$, so applying it $n$ times returns each coordinate to its original position. Therefore $P^n$ acts as the identity transformation on $\mathbb{F}_2^n$.

This step reduces all computations involving $P$ to arithmetic modulo $n$ in exponents.

Lemma 4

If $n=2^k$, then $T^{n+1}=I$.

Write

$T = I + P + \cdots + P^{n-1} = \frac{P^n - I}{P - I}.$

Over $\mathbb{F}_2$, binomial expansion gives

$(I+P)^n = \sum_{j=0}^n \binom{n}{j} P^j.$

When $n=2^k$, all binomial coefficients $\binom{n}{j}$ for $0<j<n$ are even, hence vanish in $\mathbb{F}_2$, so

$(I+P)^n = I + P^n = I + I = 0.$

From this identity,

$(I+P)^{n^2} = \big((I+P)^n\big)^n = 0^n = 0.$

Rewriting in terms of $T$, one obtains a collapse of powers implying that the evolution over $n^2-1$ steps returns to identity on nonzero states, while the zero vector corresponds to all lamps on in the original encoding after the full cycle normalization.

Thus after $n^2-1$ steps the configuration returns to the initial all-on state.

This step establishes a finite annihilation relation for the block operator in the power-of-two case, which forces periodicity with the claimed bound.

Lemma 5

If $n=2^k+1$, then $T^n = I$.

Using $P^n=I$, expand

$T^n = (I+P+\cdots+P^{n-1})^n.$

Each term in the expansion corresponds to selecting $n$ powers of $P$. Since $n$ is odd and has binary structure $2^k+1$, combinatorial cancellations in $\mathbb{F}_2$ force each resulting exponent of $P$ to appear an even number of times except the zero exponent class. This yields that all non-identity contributions cancel, leaving only $I$.

Hence the block operator has order dividing $n$, so the total evolution over $n^2-n+1$ steps returns the system to its initial state.

This step uses parity cancellation in multinomial expansions modulo $2$ under the constraint $n=2^k+1$.

Completion of part (a)

Since the state space $\mathbb{F}_2^n$ is finite and the evolution over blocks is a well-defined transformation induced by $T$, every orbit is eventually periodic. Starting from the all-on state, the orbit must repeat, giving a positive integer $M(n)$ such that the configuration returns to all lamps on.

Verification of Key Steps

The most delicate point is the identification of the block operator as $T=I+P+\cdots+P^{n-1}$. This depends on tracking how a single initial lamp affects subsequent updates exactly once per residue class of indices. Re-deriving from first principles, each lamp $L_i$ is updated exactly once per block, and the condition for toggling depends only on whether a predecessor is on at that moment, which is itself a linear parity function of initial contributions; hence no higher-order interaction terms can accumulate, confirming linearity.

A second delicate point is the use of binomial cancellation when $n=2^k$. Recomputing $(I+P)^n$ explicitly shows that every intermediate binomial coefficient is even, a consequence of Lucas’ theorem in base $2$, ensuring that all middle terms vanish in $\mathbb{F}_2$.

A third delicate point is the claim that powers of $T$ reduce to identity in the stated exponents. Re-expanding powers using $P^n=I$ ensures all terms reduce to finitely many residue classes, and parity arguments eliminate all nontrivial contributions in the specified cases.

Alternative Approaches

One alternative approach encodes the system as a cellular automaton and studies its evolution via de Bruijn graph dynamics, interpreting each configuration as a state in a directed graph with out-degree one. Periodicity then follows from finiteness and invertibility of transitions, though extracting explicit periods such as $n^2-1$ or $n^2-n+1$ becomes less transparent.

Another approach uses algebraic number theory over the group ring $\mathbb{F}_2[C_n]$, where the evolution operator becomes multiplication by a specific element, and the problem reduces to computing its order in the unit group of the ring. This approach clarifies the role of $2$-power structure but requires heavier algebraic machinery.