For (a), observe that lights can never be all off. Suppose lights are all off at Stepj, L(j-1) must be on, contradiction. Denotes the situation of lights at Stepj as Sj. The number of pairs (j mod n, Sj) is finite, smaller than or equal to n*2^n. Take N > n*2^n, there exist i < j < N s.t. (i mod n, Si) = (j mod n, Sj). Note each Sk is uniquely determined by any previous Sl (l < k), conversely, known Sk can determine each previous Sl. By Si = Sj, we can claim S(j-i) = S(i-i) = S0, which is the situation that all lights are on. M(n) = j - i.

At each position, assign light number $ 1$ if it is on, $ 0$ if it is off. (a) First, the sequence cannot terminate: it can only terminate if it reaches configuration with all lamps off, which is not possible, since if after some step $ S_{k}$ the configuration is all lamps off, that must have been the configuration before step $ S_{k}$, so backtracking, the initial configuration must have been all off, which isn't true. Consider the infinite set of configurations after $ nt$ steps for some integer $ t$. Since there are only finitely many different configurations, some two must coincide. Choose the first such pair, after say $ i$ and $ j$ steps. So after $ j$ steps, the configurations just cycle. Now consider backtracking from step $ i$ to step $ 1$ (by backtracking, replace the relavent pair of switches as follows: (0,0) and (0,1) are unchanged, (1,0) goes to (1,1) and (1,1) goes to (1,0) ) : consider the sequence of steps taking step $ i$ to step $ 1$. Now applying the same sequence of steps to step $ j$, we can see by backtracking, after exactly $ i$ steps we will reach a configuration with all lamps on. (b) Let's looking at the configurations $ K_{i}$, where $ K_{i}$ is the configuration obtained after $ ni$ steps. Denote $ K_{i,j}$ be the number assigned to light $ j$ in configuration $ K_{i}$.It's easy to see that, working in $ (mod$ $ 2)$, $ K_{i+1, 1} = K_{i,0} + K_{i, 1}$. (This is true, since two adjacent numbers (1,1), (1,0), (0,0), (0,1) are changed to (1,0), (1,1), (0,0), (0,1) respectively). From there, an induction gives us, that for $ 1 \leq j \leq n$, $ K_{i+1, j} = \sum_{l=0}^{j} K_{i,l} ... (1)$. Looking at Pascal's triangle, for $ i=1,2$ we notice that the sequence: $ K_{i,0}, K_{i,1} ... K_{i,n-1}$ is identical to $ \binom {i} {i} , \binom {i+1} {i}, ... \binom {i+n-1} {i}$. Using $ (1)$, and well-known properties of Pascal triangle (i.e.: $ \binom {n+1}{k+1} = \binom {n}{k} + \binom {n}{k+1}$), and induction, we can see that this pattern is true $ i=1,2 ... n-1$. In particular, let's look at configuration $ K_{n-1}$: for $ 1 \leq i \leq n-1$, we have $ K_{n-1, i} = \binom {i+n-1}{i} = \binom {2^{k} - 1 + i}{2^{k} - 1}$. But using Lucas's Theorem ( http://planetmath.org/encyclopedia/LucassTheorem.html ), since the binary representation of $ 2^{k} - 1 + i$ contains at least one $ 0$, and $ 2^{k} - 1$ contains only $ 1$-s, it follows that, working in $ (mod$ $ 2)$, $ K_{n-1, i} = 0$ for $ i=1,2 ... n-1$ - so after $ n(n-1)$ steps we end up with a configuration with a $ 1$ for light # $ 0$, and a $ 0$ for every other light. From there, after $ n-1$ steps, since each following steps toggles one light, we will have configuration with all lights on. (c) Let's keep the notation from proof of (b) (i.e., the $ K_{i}$ notation), and let $ K'_{i}$ denote the arrangement obtained after $ ni$ turns (but here $ n = 2^{k} + 1$, and not $ n=2^{k}$). By looking at case $ k=2$ and comparing $ K_{i}$ with $ K'_{i}$, the following pattern becomes obvious: for $ i=1, 2, ... 2^{k}$, configuration $ K'_{i}$ is obtained from $ K_{i}$, by shifting $ K_{i}$ in cyclic direction twice, and adding in a $ 0$ for the lamp in position # $ 1$. We can prove this by using induction, and our equation $ (1)$ which tells us how to get configuration $ K'_{i+1}$ from $ K'_{i}$. Using this, we can see that $ K'_{n-2}$, every lamp except for lamp #$ 2$ is a $ 0$. Using equation $ (1)$, $ K'_{n-1}$ consists of all lamps except lamp # $ 1$ being a $ 1$. Thus, after one more step, all the lamps become $ 1$-s - so in $ n(n-1)+1 = n^2 -n +1$ steps, all lamps are on again.

We'll work in $\mathbb{Z}/2\mathbb{Z}$. Let $f(i)=1$ denote the initial state of lamp $L_i$ for $0\le i\le n-1$, and $f(i+kn)$ denote the state of lamp $L_i$ after it is modified $k$ times. Then $S_j$, for $j\ge0$, gives us $f(j+n)= f(j+n-1)+f(j)$ and thus \[G(x)=\frac{1}{1-x-x^n}=\sum_{r\ge0}f(r)x^r.\](We are working in $\mathbb{Z}_2[x]$.) (i) Considering $n$-tuples $(f(t+1),f(t+2),\ldots,f(t+n))$, the periodicity is clear by the fact that at most $2^n$ such $n$-tuples can exist and a fixed $n$-tuple uniquely determines the entire sequence ($f(x)=f(x-1)+f(x-n)$ and $f(x-n)=f(x)-f(x-1)$). (ii) If $n=2^k$, then it's equivalent to show that \[\frac{x^{n^2-1}-1}{1-x-x^n}=(x^{n^2-1}-1)G(x)=P(x)\]for some polynomial $P\in\mathbb{Z}_2[x]$. But \[x^{n^2}+x=(x^n)^n+x\equiv(x+1)^{2^k}+x\equiv x^{2^k}+1+x\equiv0\pmod{x^n+x+1},\]as desired (note that $\gcd(x,x^n+x+1)=1$). (iii) If $n=2^k+1$, then it's equivalent to show that \[\frac{x^{n^2-n+1}-1}{1-x-x^n}=P(x)\]for some polynomial $P\in\mathbb{Z}_2[x]$. But \[x^{n^2-n+1}+1=(x^n)^{n-1}x+1\equiv(x+1)^{2^k}x+1\equiv(x^{2^k}+1)x+1\equiv0\pmod{x^n+x+1},\]as desired.

Solution from Twitch Solves ISL: For part (i), the sequence of states (and time indices modulo $n$) is finite, so it is certainly eventually periodic; however, because the operation is invertible, it is totally periodic. Throughout the problem we always work modulo $2$. By a round we mean a sequence of $n$ consecutive operations. Note that a round has the following effect: \begin{align*} (a_1, \dots, a_{n-1}, a_0) \mapsto (&a_2+a_3+\dots+a_0, \\ & a_1 + a_2, \; a_1 + a_2 + a_3, \; \dots, \; a_1 + a_2 + a_3 + \dots + a_0). \end{align*}(We prefer to list $L_1$ first, rather than $L_0$.) For (ii), we give a description of the process for $n = 2^{k+1}$ in terms of the process for $n = 2^k$. We write our states as binary strings of length $n$, with the $i$th bit corresponding to $L_i$ (the last bit corresponds to $L_n = L_0$). The description goes as follows: We split the string into $L_1 L_2 \dots L_{n/2} \mid L_{n/2+1} \dots L_n$. There are two copies of the process for $n=2^k$ side by side until we reach the string $100\dots \mid 1000$. After the next round, we get $11\dots11 \mid 00\dots00$. Then, the left half plays another copy of the $n=2^k$ process, with the right half being all zero, until we reach $1000 \mid 0000$ Then $n-1$ turns later we get $111\dots111$ as needed. For concreteness, if $n=4$ is given by \[ 1111 \xmapsto{4\text{ moves}} 1010 \xmapsto{4\text{ moves}} 1100 \xmapsto{4\text{ moves}} 1000 \xmapsto{3\text{ moves}} 1111 \]in terms of the rounds, then $n=8$ is given by \begin{align*} 1111\mid1111 &\xmapsto{8\text{ moves}} 1010\mid1010 \xmapsto{8\text{ moves}} 1100\mid1100 \\ &\xmapsto{8\text{ moves}} 1000\mid1000 \xmapsto{8\text{ moves}} 1111\mid0000 \\ &\xmapsto{8\text{ moves}} 1010\mid0000 \xmapsto{8\text{ moves}} 1100\mid0000 \xmapsto{8\text{ moves}} 1000\mid0000. \end{align*}and seven moves later we return to all $1$'s. One can now check by a straightforward induction that the number of moves is $n^2-1$ exactly. For (iii), we give a description for $n=2^k+1$ in terms of that for $n=2^k$. All that needs to be observed is that the situation after the $i$th round of $n=2^k+1$ is the same as the $i$th round of $n=2^k$, except with last bit moved to the first, and one extra $0$ appended, up until we reach the special state $0010000\dots$. For example, for $n = 9$ we have \begin{align*} 111111111 &\xmapsto{9\text{ moves}} 001010101 \xmapsto{9\text{ moves}} 001100110 \\ &\xmapsto{9\text{ moves}} 001000100 \xmapsto{9\text{ moves}} 001111000 \\ &\xmapsto{9\text{ moves}} 001010000 \xmapsto{9\text{ moves}} 001100000 \xmapsto{9\text{ moves}} 001000000 \end{align*}and then after an additional $n+1$ moves we return to all $1$'s. The total move count can be computed to be the desired $n^2-n+1$.

This is a notation problem. We break the problem into blocks of $n$ moves. Let the initial configuration be $C_0$, the configuration after $n$ moves be $C_1$, etc. (i) Some $C_i$ and $C_j$ are the same for $i<j$ by the pigeonhole principle. Since the procedure can be done in reverse, $C_{j-i}$ and $C_0$ agree as desired; $M(n) = (j-i)n$ works. (ii) For ease of writing, let $A$ denote ON and $B$ denote OFF, so the starting configuration is $\underbrace{AAA\cdots A}_{2^k}$; the element at index $z$ corresponds to $L_z$ with $0$-indexing. Define the following sequence of sequences of $A$ and $B$ called $W_1,W_2,\dots$ as follows. Let $W_{2^q} = \underbrace{AA\cdots A}_{2^q} \underbrace{BB\cdots B}_{2^q}$. For $1\le t < 2^q$, let $\lfloor \log_2 t\rfloor + 1 = p$, then define $W_{2^q+t}$ as $\underbrace{W_tW_t\cdots W_t}_{2^{q-p}}\underbrace{BB\cdots B}_{2^q}$. Note that this new sequence has exactly $2^{q+1}$ total instances of $A$ or $B$ when expanded. We claim that after $sn-1$ steps for $1\le s < 2^k$, the sequence of $A$s and $B$s is $\underbrace{W_sW_s\cdots W_s}_{2^{k-q-1}}$ where $q=\lfloor \log_2 s\rfloor$, shifted so that the initial $A$ of this sequence corresponds to $L_{n-1}$. The result is clear at $s=1$. Now, we show the result by induction for $s=a$ with $2\le a < 2^k$. Let $a=2^q+t$ so that $q$ is a positive integer and $0\le t\le 2^q-1$. If $t < 2^q-1$, we have two cases: either there exists some $1\le p < q$ such that $t=2^p-1$, or there does not. In the former case, note that each $W_tW_t$ sequence starting with the first metamorphosizes into $W_{t+1}$ by the result for $s=t+1$, whereas the $B$ terms in the second half of $W_a$ are unaffected. In the latter case, the result is trivial because each $W_t$ is replaced by $W_{t+1}$. Now suppose $t=2^q-1$. It is clear by induction that $W_a = W_{2^{q+1}-1} = A\underbrace{BB\cdots B}_{2^{q+1}-1}$; the result is clear at $q=0$, and each subsequent case follows from the last by the definition of $W_a$. Then $n$ moves transmute the first instance of $W_a$ into $\underbrace{AA\cdots A}_{2^{q+1}}$, the second instance into $\underbrace{BB\cdots B}_{2^{q+1}}$, and so on. This means that the new sequence is $\underbrace{W_{a+1}\cdots W_{a+1}}_{2^{k-q-2}}$, as desired. Thus it suffices to observe that $n$ moves from $A\underbrace{BB\cdots B}_{2^k-1}$ transforms it into $\underbrace{AA\cdots A}_{2^k}$; we are done. (iii) The idea is the same as that of (ii), but instead we claim that for $1\le s < 2^k$ and $q=\lfloor \log_2 s\rfloor$, the expression is $B\underbrace{W_sW_s\cdots W_s}_{2^{k-q-1}}$ at step $sn+1$ by induction on $s$. The result is trivial at $s=1$, and for $s\ge 2$, note that the manipulations of (ii) work exactly the same way because lamp $L_{n-1}$ is always assigned to $B$, so it does not flip. Then to go from $(n-2)n+1$ to $(n-1)n+1$ flips all the lamps $L_i$ with $i=0$ or $2\le i\le n-1$ back to $A$, so we are done.