5
$\begingroup$

An $8\times8$ checkerboard is filled with two-sided coins (that are blue on one side and red on the other side).

The following picture shows three examples of a cross (multiplication sign): the five red coins at the right margin form a standard cross centered at their middle coin; the two red coins in the upper left corner form a cross that is centered at the coin in the corner (the three remaining squares of the cross are outside the board and irrelevant); the three red coins in the middle of the upper half form another cross (with two squares outside the board):

checkerboard

Marco starts with the situation where all coins are blue, and by flipping some coins he wants to reach the situation where all coins are red. Whenever Marco flips one coin $x$, the other coins from the cross centered at $x$ are flipped simultaneously.

Question:

  • Can Marco reach the situation where all coins are red?

Bonus Question:

this question is worth 100 points

  • What is the number of moves to reach the goal according of $k$ where $k$ red coins are stochatically distributed on the board ?

Hint: Linear algerba is required

Improve this question
$\endgroup$
3
  • 6
    $\begingroup$ So, you want to know how to solve the Lights Out puzzle? I feel like this has been asked before. $\endgroup$
    – Kevin
    Commented Mar 17, 2015 at 16:53
  • 1
    $\begingroup$ @ Kevin solution is here ueda.info.waseda.ac.jp/~n-kato/lightsout im not searching solutions i want to know whether an optimal solution exists $\endgroup$
    – Abr001am
    Commented Mar 17, 2015 at 22:08
  • 1
    $\begingroup$ I spent a few minutes on this, no dice. It may help to consider that selecting any black square only affects black squares (true for white as well). The boards are identical up to rotation, so solve just the one of them. $\endgroup$
    – eretmochelys
    Commented Mar 20, 2015 at 19:33

5 Answers 5

Reset to default
4
+100
$\begingroup$

There is one solution, with 4 different possible rotations:

XXXXXXXX

X  XX  X
  XXXX
XXX  XXX
X  XX  X
XX XX XX
  X  X

The black and the white squares will never influence one another, so one only need to consider the puzzle with 32 squares. Further, it never makes sense to choose the same centre coin twice, since that would simply undo the initial action, and it doesn't matter in what order the flips are done. If we go through the coins row by row and for each decide whether to flip it as a centre, most of the decisions will be given by the state of another coin that cannot be influenced by any future decisions. With the right order there is only 7 decisions that does not have such a constraint, this means that there is only 128 strategies to try, only 2 of those work, and they produce the same solution in 2 different orientations. This solution must then be applied to both the white and the black squares, with two different rotation options for each.

This code solves half the puzzle, and prints any input seed that gives a correct solution to the console. It takes a little work to permute this into a solution pattern.

<!DOCTYPE HTML>
<html>
<head>
<meta http-equiv="content-type" content="text/html;charset=utf-8">
<title>Calc</title>
</head>
<body>
<script>
function trysol(num){
    var org=num
    var flip
    var map=[
        [1,1,1,1,1,1,1,1,1]
        ,[1,1,1,1,0,1,1,1,1]
        ,[1,1,1,0,0,0,1,1,1]
        ,[1,1,0,0,0,0,0,1,1]
        ,[1,0,0,0,0,0,0,0,1]
        ,[1,0,0,0,0,0,0,0,1]
        ,[1,1,0,0,0,0,0,1,1]
        ,[1,1,1,0,0,0,1,1,1]
        ,[1,1,1,1,0,1,1,1,1]
        ,[1,1,1,1,1,1,1,1,1]
    ]
    for(var y=0;y<10;y++){
    for(var x=0;x<9;x++){
        if(map[y][x]!=1){
            if(map[y-1][x]==1){
                flip=num%2
                num=num>>1
            }
            else{
                flip=2-map[y-1][x]
            }
            if(flip){
                map[y-1][x]=2-map[y-1][x]
                map[y+1][x]=2-map[y+1][x]
                map[y][x-1]=2-map[y][x-1]
                map[y][x+1]=2-map[y][x+1]
                map[y][x]=2-map[y][x]
            }
        }
    }
    }
    for(y=0;y<10;y++){
    for(x=0;x<9;x++){
        if(!map[y][x]){
            return
        }
    }
    }
    console.log(org)
}
for(a=0;a<128;a++){
    trysol(a)
}
</script>
</body>
</html>
Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ This is the answer! $\endgroup$
    – leoll2
    Commented Mar 20, 2015 at 21:01
  • $\begingroup$ can u please add the code , or whatever method u were been using to solve the problem ? $\endgroup$
    – Abr001am
    Commented Mar 20, 2015 at 21:30
  • $\begingroup$ @Agawa001 It is a severely reduced brute force approach, I only try 128 different patterns out of 4 billion possible. Are you aware of any method that requires less work? $\endgroup$
    – aaaaaaaaaaaa
    Commented Mar 21, 2015 at 13:05
  • $\begingroup$ yes it exists , and i dont think someone will come up with , but ur solution is temporarily final $\endgroup$
    – Abr001am
    Commented Mar 21, 2015 at 13:41
8
$\begingroup$

Answer to the main question

Theorem: There exists a solution for every checkerboard (of arbitrarily irregular and not necessarily rectangular shape).

In the proof, we we will say that two coins are neighbors, if their squares share a common corner but not a common edge. In other words, whenever you flip a coin then all its neighbors are flipped simultaneously. (Note also that no coin is a neighbor of itself.)

Furthermore, we will need the following auxiliary result (which essentially is the well-known handshake lemma from graph theory):

Auxiliary lemma: Every (rectangular or irregular) checkerboard with an odd number of coins contains some coin with an even number of neighbors.

Proof: We count the pairs $(c_1,c_2)$ of coins $c_1$ and $c_2$ such that $c_1$ is a neighbor of $c_2$. The number $N$ of such pairs must be even, since with every pair $(c_1,c_2)$ we also count the pair $(c_2,c_1)$. Let $n(c)$ denote the number of neighbors of coin $c$. Note that coin $c$ occurs in the first component of exactly $n(c)$ pairs, and that consequently $N=\sum_c n(c)$.
Now suppose for the sake of contradiction that all values $n(c)$ are odd. Then $\sum_c n(c)$ is the summation of an odd number of odd integer values, and hence an odd number itself. Hence $N$ is odd; contradiction.

The proof:

The proof of the theorem is done by induction on the number $k$ of squares on the checkerboard $C$. The $k=1$ is trivially true. So let us assume that the statement is true for all $k\le K-1$ and let us do the inductive step to $k=K$. We consider an arbitrary (irregular) checkerboard $C$ with $K$ squares.

(1) Let $s$ be an arbitrary square on the checkerboard $C$, and let $C-s$ denote the checkerboard that results by removing square $s$ from $C$. As $C-s$ has only $K-1$ squares, the inductive assumption implies the existence of a solution for the game on $C-s$; let $Sol(C-s)$ denote this solution.

(2) Now we return to the original checkerboard $C$. We consider an arbitrary square $s$ on $C$, and we apply the solution $Sol(C-s)$ to the checkerboard $C$. Afterwards all coins on $C-s$ are red. If the coin on square $s$ is also red, we have found a solution for checkerboard $C$ and are done.

(3) It remains to consider the following case: For every square $s$ on $C$, the application of $Sol(C-s)$ to $C$ yields a configuration in which all coins on $C-s$ are red and where the coin on $s$ is blue.

(4) Assume that the number $K$ of squares on $C$ is even. Then we consecutively apply all the solutions $Sol(C-s)$ for all the squares $s$ on $C$. Consider some arbitrary square $s^*$. The coin on square $s^*$ is flipped in each of the $K-1$ solutions $Sol(C-s)$ with $s\ne s^*$, while it is not flipped in solution $Sol(C-s^*)$. Hence the coin is flipped an odd number of times, and in the end becomes red. Since this holds for all squares, we end up with the all-red configuration. Done.

(5) Finally assume that the number $K$ of squares on $C$ is odd. We apply the auxiliary lemma to find a special square $s_o$ that has an odd number of neighbors. Then the number $x$ of squares on $C$ that are neither $s_o$ nor one of the neighbors of $s_o$ is odd.

We first flip the coin on $s_o$ (together with all coins on the neighbor squares), and then consecutively apply all the solutions $Sol(C-s)$ for all the squares $s$ on $C$, except for the square $s_o$ and its neighbors. In the resulting solution, the coin on $s_o$ if flipped exactly once. All other coins are flipped an odd number of times, as the number $x$ is odd. Since every coin is flipped an odd number of times, the resulting configuration is all-red. Done.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Could you please add a picture showing how to complete this task? I mean, which buttons should we press in order to get all the buttons red? $\endgroup$
    – leoll2
    Commented Mar 20, 2015 at 12:42
  • $\begingroup$ Yes, please post a pic so I can be done with this! haha $\endgroup$
    – JLee
    Commented Mar 20, 2015 at 14:42
  • $\begingroup$ accidental upvote $\endgroup$
    – JLee
    Commented Mar 20, 2015 at 23:54
4
$\begingroup$

Consider that selecting any black square only affects black squares (true for white as well). The boards are identical up to rotation, so solve just the one of them. Lets focus on the black:

| |3| |3| |3| |2|
|3| |5| |5| |5| |
| |5| |5| |5| |3|
|3| |5| |5| |5| |
| |5| |5| |5| |3|
|3| |5| |5| |5| |
| |5| |5| |5| |3|
|2| |3| |3| |3| |

Where we have ignored the white spaces and labeled each square with the number of neighbors it has (number of other squares which can possibly change its coin color, note that every square is its own neighbor). If we flip every square, then squares with odd numbers of neighbors will change color while squares with even number of neighbors will not. In the diagram above, we notice that by pressing every square, we can change all colors but the bottom left and top right.

... I'm not sure where I'm going anymore. This is a solution but not for the "even-sided" problem (the diagram above shows 4 black squares per side). If it were odd it cleans up real nice though.

If this spoils the fun for somebody else, please delete me.

Improve this answer
$\endgroup$
3
  • $\begingroup$ yes solution is symmetrical , thats good step $\endgroup$
    – Abr001am
    Commented Mar 20, 2015 at 19:35
  • $\begingroup$ wait the rightmost upper edge is 2 why ? $\endgroup$
    – Abr001am
    Commented Mar 20, 2015 at 21:23
  • $\begingroup$ @Agawa001 the numbers describe the total number of neighbors a square has (a neighbor is a square which, when selected, changes the color of a particular square). Given this definition, every square is its own neighbor, and the one in the top right has one more neighbor (below and to its left). $\endgroup$
    – eretmochelys
    Commented Mar 22, 2015 at 22:12
2
$\begingroup$

The answer to the question (as I misunderstood it) is yes. See below for the explanation.

I looked online and found the solutions for smaller puzzles, and used the knowledge I gained to try to solve the 8x8. I knew there was only 1 possible solution because of this link. After about 90 minutes I stumbled upon it. I used this site to test it. Toggle the lights with the 1's and do not flip the others.

Two to Seven

Eight

Improve this answer
$\endgroup$
3
  • $\begingroup$ nice try , if its the original version of light out puzzle i wouldnt o ffer a bounty , the question is about cross lights not lozenges $\endgroup$
    – Abr001am
    Commented Mar 19, 2015 at 21:46
  • $\begingroup$ oh ok. I see now. $\endgroup$
    – JLee
    Commented Mar 19, 2015 at 21:48
  • $\begingroup$ leave this post for common benifit if it wont be downvoted $\endgroup$
    – Abr001am
    Commented Mar 19, 2015 at 21:50
-3
$\begingroup$

Partial answer for 4×4 grid :

  • This answer approves the possibility of solution in smaller grid , waiting for a generalisation of this dilemma:

enter image description here

  • The lines take part of crosses where flipped coins represent squares intersected.
  • Gray shadowed squares are unfavorables ones cuz coins there are flipped n times where n is even.
  • Blod lines represent persistent lines , we cant remove them cuz they cross an empty square atleast.
  • tiny circles represent ties , if we remove a line from a tie we must remove another tie's line to ensure an odd number of lines crossing this square.
  • We start removing lines from a square containing minimal even number of different colored lines.
  • Task achieved when all squares contains odd number of different colored lines.

waiting for an answer concerning 8*8 grid ?

Improve this answer
$\endgroup$
14
  • $\begingroup$ look how much m i generous mr downvoter . $\endgroup$
    – Abr001am
    Commented Mar 19, 2015 at 17:08
  • $\begingroup$ I did not downvote, but I don't understand this answer at all. Why do you have three pictures? What does "The line stake part of crosses where flipped coins represent squares intersected." mean??? The first two figures have different gray shadowed squares, so which are the unfavorable ones? What are "blod lines"? Do you mean "blood", so the red lines? You say we can not remove those lines, but I don't know what "removing a line" even means... What do the lines have to do with the puzzle? $\endgroup$
    – user10445
    Commented Mar 20, 2015 at 13:47
  • $\begingroup$ this technique is used in graph theory so if uhavent studied such a thing in artificial intelligence it wd be hard for u to understand : - every X shape represnts squares where coins are flipped and our goal is to flip over all boead pieces odd number of times ,so this technique stands for reducing such shapes step by step in order to make all squares intersected by odd number of lines. $\endgroup$
    – Abr001am
    Commented Mar 20, 2015 at 14:44
  • $\begingroup$ Is 4x4 even possible? I can't even figure it out, much less 8x8 $\endgroup$
    – JLee
    Commented Mar 20, 2015 at 15:27
  • $\begingroup$ @Agawa001: I understand the question, and I have studied graph theory. I can't follow your answer. You show three different pictures, but don't explain what the connection between the three pictures is, and in the following text you don't specify to which of the three pictures you refer. And you might have intended the sentence "The lines take part of crosses where flipped coins represent squares intersected" to explain what the lines are, but this sentence is unreadable. It makes no grammatical sense, and I can not guess what you mean. $\endgroup$
    – user10445
    Commented Mar 20, 2015 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.