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.

Solution

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.

Product of all numbers

A prime $p$ is called "good" if there is an $m$ such that $p$ divides $m^2 - 2$. For example, 7 and 17 are good primes. Suppose $p$ is a good prime. Consider all numbers in the form of $a\sqrt{2} + b$ where $a,b \in \{0, \dots, p-1\}$ and $(a,b) \neq (0,0)$. The product of all those numbers can be written as $s\sqrt{2} + t$ where $s$ and $t$ are integers. Find their remainders modulo $p$. What if $p$ is not a good prime?

Solution

If $p$ is a good prime then $s \equiv t \equiv 0 \mod p$. If $p$ is not a good prime, then $s \equiv 0, t \equiv -1 \mod p$

Proof:

Define the "~" (equivalency) as follows: two numbers $s \sqrt{2} + t$ and $u\sqrt{2} + v$ are equivalent if $s \equiv u$ and $t \equiv v \mod p$. Then we readily see that the following properties are easy to show:

$X \sim X$ (reflexivity).

$X \sim Y \iff Y \sim X$ (symmetry).

If $X \sim Y$ and $Y \sim Z$ then $X \sim Z$ (transitivity).

Given these three then equivalency divides all numbers in te form $s\sqrt{2}+t$ into equivalency classes. Furthermore we see that:

If $X \sim Y$ and $W \sim Z$ then $X+W \sim Y+Z$ and $XW \sim YZ$. It follows directly from the properties of modular arithmetics.

Now, if $p$ is a good prime, then note that $(\sqrt{2} + m)(\sqrt{2} + p-m) = (2-m^2 + pm) + p\sqrt{2} \sim 0$. Thus the product of all numbers in question is equivalent to zero.

If $p$ is not a good prime, it's a lot more complicated.

First we claim the following: given $X \nsim 0$, then there exists $Y$ such that $XY \sim 1$. We call this $Y$ the inverse of $X$.

Proof: Given a number $a\sqrt{2} + b$, first we define the number $r$ as follows: $r \in (0, \dots, p-1)$ such that $r(b^2-2a^2) \equiv 1 \mod p$.

This $r$ must exist, because $b^2 - 2a^2 \not\equiv 0 \mod p$, for otherwise we have $(ba^{-1})^2 \equiv 2 \mod p$, a contradiction.

Then consider the number $ar\sqrt{2}-br$. The product of this and $a\sqrt{2} + b$ is: $$(ar\sqrt{2}-br)(a\sqrt{2} + b) = (2a^2-b^2)r \sim 1$$

Then we prove the second claim: If $XY \sim 0$ then either $X \sim 0$ or $Y \sim 0$.

Proof:

Let $X = a\sqrt{2}+b, Y = c\sqrt{2}+d$ then $XY = (bc+ad)\sqrt{2}+(2ac+bd) \sim 0$ so we have: $$bc+ad \equiv 0 \mod p$$ $$2ac+bd \equiv 0 \mod p$$ Assuming that both $X,Y$ are not equivalent to zero, either $c \neq 0$ or $d \neq 0$ because otherwise $Y \sim 0$. If $d \neq 0$ then: $$abc \equiv -a^2d \mod p$$ $$2abc \equiv - b^2d \mod p$$ $$\Rightarrow b^2d \equiv 2a^2d \mod p$$ $$(ba^{-1})^2 \equiv 2 \mod p$$ A contradiction. If $c \neq 0$ then we similarly show: $$abd \equiv - b^2c \mod p$$ $$abd \equiv -2a^2c \mod p$$ $$(ba^{-1})^2 \equiv 2 \mod p$$ Also a contradiction. (The assumption that $X \nsim 0$ is needed to take inverse of $a$)

So based on the second claim, we now assert that each number in the problem statement has an inverse, and the inverse is unique. For if $XY \sim XZ \sim 1$ then $X(Y-Z) \sim 0$ so $Y \sim Z$. This means that a lot of pairs among those numbers would multiply 1. The only numbers left are those who are inverses with itself. To find such numbers, note the following:

$$X^2 = 2ab\sqrt{2} + (2a^2+b^2) \sim 1$$ $$\iff ab \equiv 0, 2a^2+b^2 \equiv 1 \mod p$$ If $a \equiv 0$ then $b^2 \equiv 1$, so $p$ divides $b^2-1 = (b+1)(b-1)$. The only possible $b$ are $1, p-1$, and these numbers are in the problem statement.

If $b \equiv 0$ then $2a^2 \equiv 1$ which means $2 \equiv (a^{-1})^2 \mod p$, a contradiction.

So the only numbers who don't "cancel out" with other numbers are 1 and -1, and they're included in the final product. Thus the product of all those numbers is $\sim -1$.