6
$\begingroup$

Beginner puzzle

This puzzle is intended to be suitable for people who are new to puzzle solving.

Clarification: Both experienced solvers and new solvers are welcome to post solutions to this puzzle.

Sixteen counters, which are black on one side and white on the other, are arranged in a 4 by 4 grid. Initially all the counters are facing black side up. A single move consists of choosing a 2 by 2 square within the grid and flipping all four of its counters over. Describe a sequence of moves of minimum length that finishes with the colors of the counters of the 4 by 4 grid alternating (as shown in the diagram).

4 x 4 grid with counters alternating black and white (like a chessboard) with a black counter in top-left corner

This puzzle is from a UK Junior Mathematical Olympiad.

Improve this question
$\endgroup$

4 Answers 4

Reset to default
8
$\begingroup$

A simple proof that PDT's solution is optimal:

Consider the first and the 4th(last) column. In order to make the intended checkerboard pattern on the two columns, we need at least two flips on the left side and two others on the right side. One flip on a side is impossible because it can only produce a pattern that has two whites adjacent. Since the flips made on the left do not change the right edge (and vice versa), we need four flips in total to make both edges right.

However, the pattern we just produced is not the right pattern:

X X O O
O O X X
X X O O
O O X X

Now we need to flip the entire middle columns to get the checkerboard, which takes two more flips.

Improve this answer
$\endgroup$
10
$\begingroup$

I am not sure if this is optimum but I can do it in six moves:

enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here

Improve this answer
$\endgroup$
0
6
$\begingroup$

Label the rows by A, B, C, D from top to bottom, and columns by 1, 2, 3, 4 from left to right.

Space D1 has to get flipped, so the $2\times 2$ square CD12 (that is, the square with rows CD and columns 12) must be chosen an odd number of times. Of course there is no need to choose any square more than once, since the only thing that matters is the parity (even/oddness). So we choose CD12 exactly once.

Now space D2 has been flipped an odd number of times so it must be flipped back. We already dealt with CD12, and the only remaining square that contains D2 is the square CD23. Therefore CD23 must be chosen (an odd number of times, hence once).

Space D4 must not be flipped, hence square CD34 must not be chosen.

Therefore square BC34 must be chosen, due to space C4.

Continuing around the outside of the $4\times 4$ (counter-clockwise), we choose squares AB34, AB23, BC12. We do not choose square AB12.

Finally we see that there is no need to choose the middle square, BC23. So we are done, having chosen $6$ squares.

This is minimal because

These $6$ squares must be chosen an odd number of times.

Also,

the remaining $3$ squares must be chosen an even number of times, so in fact the solution is unique, up to (i) choosing the same squares in a different order, and (ii) choosing square $n$ an "extra" $2k_n$ times.

Improve this answer
$\endgroup$
2
$\begingroup$

I think I found a 6 move solution different to PDT

step 1

step 2

step 3

step 4

step 5

step 6

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ This has the same six moves, just in a different order. As with all lights-out puzzles, the order of the moves does not matter. $\endgroup$
    – Daniel Mathias
    Commented Apr 2 at 21:37
  • $\begingroup$ I upvoted because the solution is a nicely presented. But yes, it is the same solution once you know the moves can be swapped. $\endgroup$
    – Florian F
    Commented Apr 2 at 22:43

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