Let $n$ be a positive integer. There are $n$ lamps, each with a switch that changes the lamp from on to off, or from off to on, each time it is pressed. The lamps are initially all off. You are going to press the switches in a series of rounds. In the first round, you are going to press exactly $1$ switch; in the second round, you are going to press exactly $2$ switches; and so on, so that in the $k$th round you are going to press exactly $k$ switches. In each round you will press each switch at most once. Your goal is to finish a round with all of the lamps switched on. Determine for which $n$ you can achieve this goal.
Problem
Source: 2021 Simon Marais, B2
Tags: combinatorics
ccso
09.11.2021 15:32
Do you mean all lamps must be on in exactly n rounds or you could stop if all lamps are on? If the first case n=k^2 satisfies the condition
Isolemma
09.11.2021 17:05
The answer is all positive integers except $n = 2$. It is easy to verify the result for $n \leq 3$. We index the lamps $1, 2, \dots, n$. Consider the following "standard process". In round $k$, we switch $k$ lamps: if $k$ is odd, then we switch lamps $2, \dots, k + 1$; if $k$ is even, then we switch lamps $1, \dots, k$. Thus the effect of round $2k - 1$ and round $2k$ combined together is equivalent to switching just lamp $1$. If $n = 2m$ is even, then we choose an even integer $k$ such that $m \leq 2k \leq n$. This is possible whenever $n \geq 4$. We switch the lamps according to the standard process, except that at round $m$, we switch only the lamps that are not switch in the standard process. Namely, if $m$ is odd, then we switch lamps $1, m + 2, m + 3, \dots, 2m$; if $m$ is even, then we switch lamps $m + 1, m + 2, \dots, 2m$. Thus after $2k$ rounds, the standard process will end with all lamps being off, but our modified process will be equivalent to all lamps being switched once more, thus all on. If $n = 4m + 1$, then we switch lamps according to the standard process, except that at round $n$ we switch all lamps $1, \dots, n$. After round $4m$, all lamps will be off. Therefore after round $n$, all lamps are on. If $n = 4m + 3$, then we choose an odd integer $k$ such that $2m + 2 \leq 2k \leq n$. This is possible whenever $n \geq 7$. We switch the lamps according to the standard process, except that at round $2m + 1$, we switch lamps $2m + 3, \dots, 4m + 3$. After $2k$ rounds, the standard process will end with only lamp $1$ on. Our modified process will be equivalent to lamps $2, \dots, 4m + 3$ being switched once more, thus all lamps are on.