We place n lights L_0, L_1, ..., L_{n-1} on a circle.

combinatorics/lights.in.circle New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

We place n lights L_0, L_1, ..., L_{n-1} on a circle.  We count modulo
n, so L_n=L_0 etc.

Then we perform a number of steps S0,S1,...
Step S_j does the following:
  { if the light L_{j-1} is off, then step S_j does nothing
  { if the light L_{j-1} is on, then L_j will be inverted (i.e. on ->
    off and off -> on)

At the beginning all lights are on.
Suppose n=2^k [resp. 2^k + 1]: how many steps S_0, S_1, ..S_? does it
take to return to the original state where all lights were on?

[ Editor: as quoted by Stein Kulseth <stein@hal.nta.no>; the original
poster is not named in the collected posting. ]

Show solution

[ Editor: an earlier combinatorial solution, giving the same answers,
was not collected. ]

I.e., perform the following linear operation on n-tuples of integers
mod 2  (0=lamp off, 1=lamp on):

F: (x(0),x(1),....,x(n-1)) ----> (x(1),x(2),...,x(n-1),x(0)+x(n-1))

I.e., for which value of   t  is it true that  F^t (v) = v,
where  v = (1,1,1,...,1).

The characteristic equation of  F is:    x^n=x^(n-1)+1       (**).
This is irreducible mod 2, so for any nonzero vector  w,  F^t(w)=w
if and only if   F^t = I  as a linear map.

Note that  (**) implies   (x-1)=x^(1-n)

If n=2^k
             x^(2^k) - 1 = x^(2^k - 1)      (**)
             (x-1)^(2^k) = x^(2^k - 1)      (as we are working mod 2)
             x^(1-n)(n)  = x^(n-1)
                       1 = x^(n^2 - 1)

-->  F^(n^2-1)=I

Similar reasoning  for  n=2^k+1  shows   F^(n^2 - n + 1)=I.

So the answers are:  (n^2-1) and  (n^2 - n + 1), as in the previous
posting.

The advantage of this rather indirect method is that it shows what the
answer is for an arbitrary initial position: given  n  and a nonzero
vector  w corresponding to the initial position, it takes exactly   t
steps to restore a position rotationally equivalent to the initial one,
where  t  is the order of  F  as a linear map  (= the smallest  m  such
that (X^n - X^(n-1) - 1) divides  (X^m - 1) [Editor: printed as X^q]);  hence LCM(t,d) steps
restore the original position,  where  d  is the smallest divisor of
n such that this position is invariant under a rotation by  d  places.

If all lamps are off  (w=0), then clearly the operation does nothing so
things cycle after one step.

-- Tal Kubo <kubo@birkhoff.harvard.edu>