300000
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutsch | O'zbek | РусскийСветофор©
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.
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.
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.
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.
- 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.
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.
-
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 afterProof:
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. □
- 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.
-
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.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.
The result of this shorter sequence should be the same as before.
-
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.
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 #
No. Already these 4 clicks
· © · · © · · · · · · © · · © ·have the same result:
# O O # O # # O O # # O # O O #
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.
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.
The sequences
© · © © · · © · © · · · and © © © · · · · © · © © © © © · © · © · ·
each have 8 clicks.
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.
- 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.
-
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.
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.
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!
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.
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.
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.
· · · · · 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.
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)).
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.
Like the other 16-click cycle, this can be used to shorten sequences of clicks.
Executing both cycles gives (because of © + © = · )
· © © © · © · © · © © © · © © © · © · © © · © · © · · · · · © © · © © + · · · · · = © © · © © (8) © · © · © © · © · © · · · · · · © © © · © · © · © © © · © ©
which must be a cycle, and yes, it is simply cycle (7) rotated by 90°.
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).
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.
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!
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.
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.
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.
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).
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.
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.
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.
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.
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.
Следите за обновлениями или подписывайтесь на них: