300000
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutsch | O'zbek | РусскийLights©
If you are only interested in solving Lights contest problems then skip ahead to Hints for playing the game below.
Before we start let us introduce some math terms.
Math language
We use this opportunity to practise math formalism and will group statements into
- Hypothesis (proposed statement as a starting point for further investigation)
- Definition (explaining the meaning of a word or phrase)
- Theorem (bold statement)
- Lemma (minor statement)
- Proof (statements that show without doubt that a theorem or lemma is correct. The symbol □ will indicate the end of a proof.)
- Corollary (statement that follows directly from a theorem or lemma)
A good way to explore a topic is to ask yourself simple questions and to try to answer them. We will do that now. You can look at this page as a manual for doing research, especially the section investigating symmetries. Along the way, we will find hints on how to play the game.
Does it matter in which order clicks are made?
No. The status of a light depends only on the number of clicks made on the light itself and on the neighbouring lights, not on the order of clicks. If the total number of clicks on the light and on its neighbours is even, then the light does not change its status. If the number is odd then the status changes, independent of the order of clicks.
Example:Pick two different neighbouring lights, say, A and B. Then click them in the order A, B, B, A. What is the result? ↠ Nothing has changed because B, B has no effect and A, A has no effect either.
Let us now reverse the order of the first two clicks and click them in the order B, A, B, A. What is the result? ↠ Again nothing has changed. The order of the first two clicks did not matter. The same is the case if we click the two buttons each twice in any order. The order of clicks does not matter.
If the order of clicks does not matter then how can one reduce the number of clicks of a long sequence?
One way of lowering the number of clicks is as follows.
While solving the puzzle, one records for each light the number of clicks made on this light. Afterwards, one sets each even number of clicks on a light to zero and each odd number of clicks to 1. The new sequence has the same effect and is also a solution.
Definition:A sequence of clicks is called reduced if each light is clicked at most once. The above process is called a reduction.
What is an upper bound for the length of a reduced sequence of clicks?
- A sequence can only have as many clicks as there are lights because in a reduced sequence each light is clicked at most once. So if the board has height h and width w then there are h×w lights and a reduced sequence can have at most h×w many clicks.
If the order of moves does not matter, how could one perform a complete search (brute force search) for a solution, i.e. a sequence of clicks that switches all lights ON?
Because the order of clicks does not matter, it is enough to know for each light whether it is clicked in a solution or not. Therefore it would be enough for a complete brute force search to try clicking all combinations of all lights.
If the board has h×w lights then there are 2h×w combinations of them (2 options for each light whether it is clicked in that combination or not). Such a brute force search would take too long. However, if 'Help Notes' is switched on (not available in contests) then one can simply click all lights one by one and check whether this click brought you closer to the solution. If yes, then leave it, else click it again.
The following questions will lead the way to shorten sequences of clicks even further.
If all lights are ON and each light is clicked exactly once what is the result?
-
Lemma:
If on a rectangular grid all lights are ON and each light is clicked once then afterwards the corner lights are OFF (O), all other lights on the edges are ON (#) and all remaining lights are OFF (O) as shown in this 4 x 4 board:
# # # # O # # O
# # # # # O O #
# # # # # O O #
# # # # O # # O
before after
Proof:
To start with, each light itself is clicked and therefore switched once. Each light also switches when its neighbour is clicked.
Therefore, if the number of neighbouring lights is even, then the light will be switched an extra even number of times, so in total an odd number of times. Therefore, it will still be OFF if it was initially ON.
Similarly, if the number of neighbouring lights is odd, then the light will be switched an extra odd number of times, so in total an even number of times. Therefore, it will still be ON if it was ON initially.
By counting the number of neighbours of each light one gets the statement of the lemma. □
Are there reduced sequences of clicks where at the start and at the end of the sequence all lights are ON? We will call such a sequence a cycle.
- start with all lights ON
- have two different reduced sequences which both switch the same lights OFF, for example, switch all lights OFF
- merge both sequences to one sequence which, if started with all lights ON, will end with all lights ON
- reduce that combined sequence to get a cycle. This reduced cycle contains clicks because both combined sequences were different, so there must be at least one click in one sequence which is not in the other original sequence. The reduced combined sequence will have this click.
If each light is clicked an even number of times then reduction (explained earlier) gives zero clicks of each light and then it is not a surprise that all lights stay ON. But is there a reduced sequence with clicks that starts and ends with all lights ON?
Definition:A reduced sequence which includes at least one click is called a cycle if all lights have the same status before and after that sequence.
We will look for cycles by starting with all lights ON and ending with all lights ON. Such a cycle would then leave also every other initial state unchanged, i.e. if we start with a board with some lights ON and some OFF, and we perform this cycle, those same lights will be ON and OFF. Can you see why?
One possibility to find a cycle is to
For which sizes of boards is this possible? For a specific board size one can answer this question by formulating a linear algebraic system of equations and investigating it. More about that can be read in the references given further below.
How can we find a cycle for a 4×4 board?
-
Let us start with all lights ON (#) and click each light exactly once. We know, we get
O # # O
# O O #
# O O #
O # # O
Because we are looking for a cycle, i.e. starting and ending with all lights ON we try and click all lights that are OFF (shown as O) once which not only clicks them ON but leaves all other lights ON as well. Please verify it yourself.
To remind ourselves: At first we clicked all lights and then clicked again on the lights on both diagonals. So we clicked the lights on diagonals twice. By reducing this whole sequence, all double clicks on diagonal lights would be discarded and only clicks on the # lights in the above board would remain. So, we started with all lights ON and ended with all lights ON. Therefore the 8 clicks on the # in the above board form a cycle! HOORAY, we found a cycle! 🥳
Please try it out and convince yourself that clicking on the 8 lights marked # above does not change the lights of a 4×4 board. This is most easily seen when starting with all lights ON.
How can a cycle be used to shorten a sequence of clicks even further?
If a cycle is known then this may be usable to shorten sequences of clicks even more.
Lemma:If a cycle with c many clicks is known and a sequence is given of which n clicks belong to the cycle, then replacing these n clicks by the c−n clicks that are not in the cycle gives an equivalent sequence.
Proof:This proof is constructive, i.e. it shows how to construct such a sequence.
If we append the sequence with the cycle then the new combined sequence would be equivalent because we added a cycle. In the combined sequence n clicks are performed twice, once in the original sequence and once in the cycle. By reduction, i.e. deleting these double clicks, the new sequence would still be equivalent (because reduction generates equivalent sequences) and would now have, instead of n clicks, c−n clicks belonging to the cycle. □
Corollary:If c−n < n then the new sequence is shorter. This is the case if and only if n > c/2. In words: If a sequence contains more than half of the clicks of a cycle then the sequence can be shortened by appending the cycle and deleting double clicks.
Example:Make (with pencil on paper) a list of 13 lights on the 4×4 board, start with all lights ON and click the 13 lights and draw a picture of the result. (Why 13 and not, say 12? We will see further below. :-) ) Now check which of the 13 clicks belong to the cycle and make a new list of clicks (with pencil on paper) where these cycle clicks are replaced by the other clicks in the cycle. Start again with all lights ON and perform this shorter sequence of clicks.
What is the result?
The result of this shorter sequence should be the same as before.
What is an upper bound for the length of a shortened sequence of clicks on a 4×4 board?
-
Theorem:
A sequence of clicks on a 4×4 board can be reduced to maximally 12 clicks.
Proof:We learned that a reduced sequence on a 4×4 board can only have 4×4=16 clicks. We know a cycle of 8 clicks for the 4×4 board. Therefore a sequence can have at most 16−8=8 clicks that do not belong to a cycle. We also found out that if a sequence has more than half of the clicks of a cycle then it can be shortened. Therefore, a reduced and shortened sequence can have at most:
8 (clicks not belonging to the cycle)
+ 8/2 (half of the clicks from the cycle)
= 12 clicks
on a 4×4 board. □
All possible 4×4 board problems to switch all lights ON can be solved with at most 12 clicks.
Clarification:The theorem does not say whether there exists a sequence of length 12 that cannot be shortened with cycles. Maybe the maximal length is 12, 10 or 8. The theorem only says that it cannot have more than 12 clicks.
Following the above conclusions, what could be an example of a 4×4 problem that takes the most number of clicks to switch all lights ON?
We click all lights not in the cycle, so all 8 lights on diagonals. Then we pick 4 lights from the cycle, for example, one on each side in clockwise direction. With © indicating a click we made these 12 clicks:
© · © ©
© © © ·
· © © ©
© © · ©
resulting in the board
# O O #
O # # O
O # # O
# O O #
Is this 12-click sequence now of maximal length that cannot be shortened?
No. Already these 4 clicks
· © · ·
© · · ·
· · · ©
· · © · have the same result:
# O O #
O # # O
O # # O
# O O #
What does that mean?
It means we have a new cycle of 12+4=16 clicks, HOORAY! 🥳 If we drop double clicks (© + © = ·), this new cycle of 12 clicks remains:
© · © © · © · · © © © ©
© © © · + © · · · = · © © ·
· © © © · · · © · © © ·
© © · © · · © · © © © ©
Please verify that this is a cycle.
What comes out when we append the 12-click cycle and the 8-click cycle and shorten that?
The sum of two cycles must be a cycle, i.e. it does not change the board:
© © © © · © © · © · · ©
· © © · + © · · © = © © © ©
· © © · © · · © © © © ©
© © © © · © © · © · · ©
gives the 90° rotated version of the 12-click cycle, which is our new 3rd cycle. Please verify that this is a cycle as well.
What does that mean for the maximal length of a sequence of clicks on a 4×4 board?
The sequences
© · © © · · © ·
© · · · and © © © ·
· · · © · © © ©
© © · © · © · ·
each have 8 clicks.
Can they be shortened with the 3 cycles?
Each one overlaps with the 8-click cycle by exactly 4 clicks and overlaps with each 12-click cycle by exactly 6 clicks. Please verify these 6 statements. They do not overlap with each cycle by more than half of the cycle's clicks. So, these sequences cannot be shortened with these 3 cycles, but adding only one more click to them would make it possible to shorten them.
We make this unproven conjecture:
Hypothesis:The maximal length of a sequence of clicks on a 4×4 board that cannot be shortened by a cycle is 8.
You are welcome to prove it. First one would have to show that there are no other independent cycles.
In the following we will look at 5×5 boards and investigate more symmetries.
What about 5×5 boards? Can you find a cycle for that board?
- start with all lights ON
- click each light once and get
O # # # O # O O O # # O O O # # O O O # O # # # O - click all lights on diagonals once, also the center light just once. The result is that all lights are ON.
- reduce the sequence by dropping all double clicks on diagonals leaving 25−9=16 clicks shown as © in:
· © © © · © · © · © © © · © © (1) © · © · © · © © © · - and celebrate, we found a cycle, HOORAY! 🥳
Similar to 4×4 boards we
Please try it out and convince yourself that clicking on the 16 lights marked © above does not change the lights of a 5×5 board. This is most easily seen when starting with all lights ON.
What is an upper bound for the length of a shortened sequence of clicks on a 5×5 board?
-
Theorem:
A sequence of clicks on a 5×5 board cannot have more than 17 clicks.
Proof:We learned that a reduced sequence on a 5×5 board can only have 5×5=25 clicks. We know a cycle of 16 clicks for the 5×5 board. Therefore a sequence can have at most 25−16=9 clicks that do not belong to a cycle. We also found out that if a sequence has more than half of the clicks of a cycle then it can be shortened. Therefore, a reduced and shortened sequence can have at most:
9 (clicks not belonging to the cycle)
+ 16/2 (half of the clicks of a cycle)
= 17 clicks
on a 5×5 board. □
If a 5×5 board problems to switch all lights ON has a solution then there is a solution with at most 17 clicks.
Clarification:Does it mean that there are sequences of 17 clicks that cannot be shortened?
Answer:No. So far we do not know.
Which role does symmetry play in this game?
Because the board is of rectangular shape, the pattern of lights that are ON/OFF may be rotational symmetric by 90° or 180° or it may have a mirror symmetry along a horizontal or vertical symmetry line. If the board is a square it might also have a mirror symmetry along a diagonal or even both diagonals.
In the following the idea is that the solution consists of a number of clicks which have that symmetry and other clicks that do not have that symmetry.
How can we make progress?
We need inspiration and we get it from playing the game and clicking randomly lights till we get a board that looks strange or has a nice symmetry. And then we wonder whether the sequence of clicks is also special.
We may come across a board like this:
O O O O O
# O # O #
O O # O O (2)
# O # O #
O O O O O
and have forgotten how we reached it. This is easy to find out by selecting 'Help Notes ON' and clicking each position. If the number shown in 'Help Notes: You can win in at most XX clicks' was lowered, we take a note of the position, and if not, we click it again. We find this solution where © indicates a click:
· · · · ·
© © © © ©
· · © · · (3)
· © · © ·
© · © · ©
Now we should be really surprised and get very curious!
Why?
Because the board (2) has a mirror symmetry with the middle horizontal line as symmetry line but the solution does not have that symmetry. It is rare in math that a symmetric problem has a non-symmetric solution.
What now?
We should investigate this by extracting the symmetric part and the non-symmetric part of (3).
We therefore write (3) as the sum of a symmetric and a non-symmetric part:
· · · · · · · · · · · · · · ·
© © © © © · © · © · © · © · ©
· · © · · = · · © · · + · · · · ·
· © · © · · © · © · · · · · ·
© · © · © · · · · · © · © · ©
Just like treasure hunters are looking for gems, we in math are also looking for unique objects. The above decomposition is not unique. There are many ways to write the non-symmetric part as a sum of a symmetric and another non-symmetric part.
Is there a unique split?
We can make it unique by requiring the non-symmetric clicks to be on only one side of the symmetry line.
We use © + © = · and therefore write now
· · · · · · · · · · · · · · · · · · · ·
© © © © © · © · © · © · © · © · · · · ·
· · © · · = · · © · · + · · · · · + · · · · ·
· © · © · · © · © · © · © · © © · © · ©
© · © · © · · · · · · · · · · © · © · ©
· · · · · · · · · ·
© © © © © · · · · ·
= · · © · · + · · · · ·
© © © © © © · © · ©
· · · · · © · © · ©
Knowing that we are on to something, we now want to know all about it.
Because the original board was symmetric and the symmetric part must make a symmetric board, therefore the non-symmetric sequence must also make a symmetric board.
What is it?
· · · · · O O O O O
· · · · · O O O O O
· · · · · (4) generates the board # O # O # (5)
© · © · © O O O O O
© · © · © O O O O O
Please check it!
We will see that there are very few non-symmetric solutions that generate a symmetric board and have all clicks on one side of the symmetry line.
What if one walks around the board (5) and looks at it and at the solution (4) from the other side?
The board looks the same (because it has the 180° symmetry), but the solution becomes
© · © · ©
© · © · ©
· · · · · (6)
· · · · ·
· · · · ·
So (6) is another non-symmetric sequence producing the same symmetric board (5). Is that an accident or is that in general the case?
This is a general statement:
If a symmetric problem (here (5), having a 180° symmetry) produced by a non-symmetric sequence (here (4)) then performing the symmetry operation (here a 180 ° rotation) on this sequence generates a new non-symmetric sequence (here (6)) which creates the same board (here (5)).
What happens when one executes both non-symmetric sequences?
After the first sequence (4) three lights are switched OFF (in board (5)) and after the second sequence (6) the 3 lights are switched again, now ON. That means (4) + (6)
© · © · ©
© · © · ©
· · · · · (7)
© · © · ©
© · © · ©
is a 12-click cycle! HOORAY!! 🥳 Please verify that by doing these 12 clicks.
What could one use this new cycle for?
Like the other 16-click cycle, this can be used to shorten sequences of clicks.
Can one shorten the 16-click cycle with the 12-click cycle? The result must be a cycle because cycle + cycle = cycle.
Executing both cycles gives (because of © + © = · )
· © © © · © · © · © © © · © ©
© · © · © © · © · © · · · · ·
© © · © © + · · · · · = © © · © © (8)
© · © · © © · © · © · · · · ·
· © © © · © · © · © © © · © ©
which must be a cycle, and yes, it is simply cycle (7) rotated by 90°.
Is the 16-click cycle also the sum of two non-symmetric solutions of a symmetric problem?
We have 2 ways of writing the 16-click cycle as a sum:
· © © © · · · · · · · © © © ·
© · © · © © · · · · · · © · ©
© © · © © = © © · · · + · · · © © (9)
© · © · © © · © · · · · · · ©
· © © © · · © © © · · · · · ·
· © © © · · · · · · · © © © ·
© · © · © © · · · © · · © · ·
© © · © © = © © · © © + · · · · · (10)
© · © · © © · · · © · · © · ·
· © © © · · · · · · · © © © ·
Each one of the two sequences on the right side of (9) is a non-symmetric sequence resulting in the symmetric board
# O O O O
O O O O O
O O O O O (11)
O O O O O
O O O O #
Each one of the two sequences on the right side of (10) is a non-symmetric sequence resulting in the symmetric board
# O O O #
O O O O O
O O O O O (12)
O O O O O
# O O O #
So, the 16-click cycle is the sum of two non-symmetric solutions of a symmetric problem, even in two ways.
If one wants to minimize the number of sequences to remember then it is enough to remember
· · · · ·
© · · · ·
© © · · · (13)
© · © · ·
· © © © ·
because the other sequence on the right of (9) has the same effect and the sequences on the right of (10) are just sums of (13) and 90° rotations of (13).
How does that help to solve symmetric boards?
If it is true that for 5×5 boards the sequences (4), (13) and their 90° rotations are the only non-symmetric sequences that produce mirror symmetric boards (apart from symmetric clicks that yield other non-symmetric sequences) then to solve a mirror symmetric board one only needs to perform symmetric moves until either all lights are ON, or until one has reached one of boards (5) or (11) (or 90° rotations of them) and then one simply executes sequences (4) or (13) (or 90° rotations of them).
In other words, to solve a mirror symmetric 5x5 board, one only has to try out symmetric combinations of clicks which require fewer such symmetric clicks and thus result in a smaller search tree.
What is the maximal length of a shortened sequence of clicks on a 5×5 board?
We are not answering this question, but we have two suggestions.
Hypothesis:There are no other cycles for a 5×5 board that are not a combination of the 3 cycles with 12, 12 and 16 clicks.
Hypothesis:The maximal length of a shortened sequence of clicks on a 5×5 board is 13.
We leave it to you to think about a proof or a counterexample in form of another independent cycle or of a sequence with more than 13 clicks which cannot be shortened with the 3 cycles (7), (8) and (1) having 12, 12 and 16 clicks. The first hypothesis can be checked using linear algebra (see further below), but a simple proof or a different cycle would be nice to have. An example of a sequence with 13 clicks that cannot be reduced with the 3 cycles is
© · © · ©
· © · © ·
© · © · ©
· © · © ·
© · © · ©
Have fun in (re-)searching and proving!
Can all patterns of ON/OFF lights on the board be reached?
With h×w lights there are 2h×w pattern of ON/OFF lights. As we found out before, there are also 2h×w possible sequences of clicks.
But there are sequences which result in the same board pattern, namely any sequence and this sequence + cycle. Therefore we have more sequences than reachable board pattern, so there must exist board pattern that cannot be reached.
In mathematics there are words for such situations. If each sequence of clicks would result in a different pattern, then the map of sequences to pattern would be called injective. If each pattern would be the result of some sequence of clicks then the map of sequences to pattern would be called surjective. Our map of sequences of clicks to pattern is therefore non-injective and non-surjective.
Hints for playing the game
Preparation practice
To prepare for playing the game in a contest it is helpful to start with a board with all lights being ON. To get this board one lowers the number of 'Initial Clicks' and 'Purple Lights' to 0 and increases the size of the board. Then do 2 clicks either on direct neighbours or diagonal neighbours and remember the resulting pattern so that you recognize them when they come up in a game. Do such tries in a corner, at an edge and in the middle as pattern depend on the location too.
A different kind of practice is to take a 5×5 board with all lights ON and click lights that are symmetric with respect to a diagonal or middle line or that are 90° or 180° rotated versions of each other and see which symmetric pattern you can get.
What should one try first if there is a small group of nearby lights that are OFF?
In this case moves in the center of such small groups should be tried first because clicks on the edge of such groups would only switch OFF more lights further away and enlarge the group of lights that are OFF. If unsuccessful one has to click more lights further away and end up having to make clicks all over the board.
What if the board pattern has a symmetry?
The initial board may be mirror symmetric with respect to one or both diagonals or with respect to the horizontal and/or vertical line of symmetry. Other symmetries may be the 90° or 180° rotational symmetry. In section Which role does symmetry play in this game? we derived the following strategy.
One performs groups of symmetric clicks which preserve the symmetry until either all lights are ON, or when having a board of size 5×5 until one reaches one of these boards:
O O O O O # O O O O # O O O #
O O O O O O O O O O O O O O O
# O # O # (5) or O O O O O (11) or O O O O O (12)
O O O O O O O O O O O O O O O
O O O O O O O O O # # O O O #
(or 90° rotations of them) and then one simply executes sequences:
· · · · · · · · · · · © © © ·
· · · · · © · · · · © · © · ©
· · · · · (4) resp © © · · · (13) resp © © · © © (1)
© · © · © © · © · · © · © · ©
© · © · © · © © © · · © © © ·
(respectively 90° rotations of them).
What does it mean to 'Play symmetric'?
If any light on the symmetry line is OFF then this light itself needs to be clicked. Reason: If one would not click it and only click a neighbouring light then the other neighbouring light symmetric to the symmetry line should also be clicked and then the light on the symmetry line would be switched twice and stay OFF.
For the same reason, if any light on this diagonal is ON then this light must NOT be clicked.
If the position is symmetric with respect to two symmetry lines (2 diagonals or horizontal and vertical middle line) then the above rules apply to both lines. Any light on these lines that is OFF needs to be clicked and any light on these diagonals that is ON must NOT be clicked to have all lights ON and to have a symmetric solution.
If the board is not mirror symmetric but rotational symmetric then one makes groups of clicks with the same rotational symmetry to preserve this symmetry.
Whatever the symmetry is, when you click a light then click the symmetry related light(s) as well. In other words, if it is a 90° symmetry (4-fold rotational symmetry) then click the other 3 lights as well, if it is a 180° symmetry (2-fold rotational symmetry) then click the other one light as well. If it is a mirror symmetry then click the mirror symmetric light as well. If a light is its own symmetric light then click it only once. Examples for lights to be clicked once are the center light under any symmetry or a light on a diagonal under diagonal mirror symmetry or a light on a horizontal or vertical line through the center if that line is the symmetry line.
If after clicking a light and all its symmetric lights the symmetry increases (e.g. 2 mirror symmetries instead of one mirror symmetry) then use the increased symmetry from now on.
What if the board pattern has no symmetry?
If the board has no symmetry then one can try making clicks that switch more lights ON than OFF. Then one can make moves that bring OFF lights closer together. Sooner or later a symmetric position results and then one continues with symmetric clicks.
The last three questions concern more general cases.
What is a general solution strategy for finding a sequence of clicks that result in some given board pattern?
The history of this puzzle and the outline of a general solution is given on Wikipedia. Another more mathematical description with more references is given on Wolfram MathWorld. You might want to check whether our findings are contained in these publications or not.
Can every initial position of some lights being ON and the rest being OFF be changed into all lights being ON? If not, how can one tell? How can one find out whether the board of a given size has a cycle and if it exists, find the cycle?
These questions can be answered by formulating and investigating a linear algebraic system of equations. More about that can be read in references given above.
Would the above theory still hold if purple lights are present?
Purple lights potentially change everything. One has to check each statement above whether it is still valid in the presence of purple lights or how to modify the statements to keep them true. Linear algebra would be flexible and general enough to cover boards with purple lights.
Folgen oder abonnieren für Updates: