Monday, December 1, 2014

Lights forming a hexagon

Six lights are placed such that they form a regular hexagon. At each turn, we're allowed to do one of the following:

1. Toggle three consecutive lights

2. Toggle three lights that form an equilateral triangle

3. Toggle two diametrically opposite lights

Prove or disprove, for any given starting configuration, we can turn off all the lights through a series of turns as described above.


Answer: we cannot.

Label the lights as 1,2,3,4,5,6, and denote each move as follows:

$A_i$: toggling lights $i, i+1, i+2$. There are 6 such moves: $A_1, \dots, A_6$.

$B_i$: toggling an equilateral with $i$ as one of its vertices. Obviously we only need to consider $B_1, B_2$.

$C_i$: toggling $i$ and its opposite. Again, we only need to consider $C_1, C_2, C_3$.

$D$: toggling all the lights. Although this is not one of the moves allowed explicitly in the problem statement, it can be achieved by the combination of $A_1+A_4$ (as well as many others), so it is effectively a legal move.

From a set of moves, we're allowed to remove it if it can be achieved by a combination of all the other moves remaining in the set. So from the set of all the moves described above, we can remove $A_4, A_5, A_6$ because they can be achieved by $D + A_1, D+A_2, D+A_3$ respectively.

Likewise, we can remove $B_2 = B_1 + D$ and $C_3 = C_1+C_2+D$. So now we're down to $\{A_1,A_2,A_3,B_1,C_1,C_2,D\}$. Now notice that: $A_2 = C_1 + A_1$, $A_3 = C_1 + C_2 + A_1$ so we remove them as well, leaving us with $\{A_1,B_1,C_1,C_2,D\}$.

Now although the number of possible move sequences is infinite, the number of reachable configurations from an all-off configuration is limited. There are five moves left in our set. We have not yet proved that they're all truly independent (i.e. we can no longer remove any more), but we don't need to. For each move in that set, it only matters whether that move is performed an even or odd number of time. In algebraic lingo, these moves are commutative and self-inverse. So that means there are at most $2^5$ configurations reachable from an all-off configuration, but we have $2^6$ total configurations. Each sequence of moves are its own inverse, so that means there are 32 configurations such that we cant turn off all the lights.

If we're asked to identify such configuration, we note the following: the configuration where only 1 light is on is not reachable from an all-off configuration. If this were possible, then we could apply that same sequence of moves (rotated appropriately) to achieve any desired configuration.

No comments:

Post a Comment