There are 2012 lamps arranged on a table. Two persons play the following game. In each move the player flips the switch of one lamp, but he must never get back an arrangement of the lit lamps that has already been on the table. A player who cannot move loses. Which player has a winning strategy?
Problem
Source: 2012 Baltic Way, Problem 6
Tags: combinatorics
26.11.2012 17:27
The first player to play has a winning strategy. Choose a single lamp, and on every turn have him toggle it. We will prove that if the second player has a valid move, the first player must also have a valid move, meaning the strategy is in fact winning (there are of course only finitely many configurations, so every game must terminate) Every configuration $C$ of lamps can be expressed as either $0C'$ or $1C'$ where $C'$ is the configuration of the $2011$ other lamps and the 0/1 bit represents the state (off/on) of the chosen lamp. When play passes to the first player and the configuration is $0C'$, he flips it to $1C'$. When it is $1C'$, he flips it to $0C'$. We only need to show that it is not possible to repeat an already-used configuration. Suppose for the sake of contradiction that it is possible to do so. WLOG the first player receives the configuration $0C'$ and by hypothesis the configuration $1C'$ has already appeared for some $C'$ and sequence of moves. If the first player was the one who reached the configuration $1C'$, he must have been given $0C'$ by the second player, contradicting the fact that the newly received $0C'$ is a new configuration. If on the other hand the second player was the one who reached the configuration $1C'$, he must have been given $0C'$ by the first player, again contradicting the fact that the newly received $0C'$ is a new configuration. Then since the game must terminate and the first player can always move after the second player, he has the winning strategy.
13.07.2016 17:29
hyperbolictangent wrote: If on the other hand the second player was the one who reached the configuration $1C'$, he must have been given $0C'$ by the first player, again contradicting the fact that the newly received $0C'$ is a new configuration. This obviously isn't true, as $1C'$ can be reached by the second player from any of 2011 other configurations that differ from it by one lamp position. A fix: If the second player reached $1C'$ the first time, then the second player could never have reached $0C'$ to pass it to the first player, as the difference between the configurations is in an odd number of lamps, which can only be achieved by flipping switches an odd number of times. So after the second player would have passed $1C'$ to player $1$, an odd number of moves would need to be performed for the second player to pass $0C'$ to the first player later. However, this move sequence should contain an equal number of moves by both players, and therefore would need to have an even number of moves, a clear contradiction.