4
$\begingroup$

Here is the best game ever, Dancing Floor Machine. This machine is brilliant! Every grid is like a switch on/off button, whenever you push on a grid on the floor, that grid and the neighbor grids turn on or off depending on the current condition. If it is off, it will turn on, otherwise turn off. For example:

enter image description here

At the beginning of the given example, $3$ is already on, the rest is off, When I push on $5$, $5$ turns on, and the neigbor grids as well, $2$,$4$,$6$ and $8$.

The question is

$1-$ At least how many times do we need to press on the button on the floor shown as below to turn them all on?

enter image description here

$2-$ Since you learn the methodology while solving previous question, at most how many times do you need to press on the buttons to turn them all on in the worst case scenario?

Good Luck!

$\endgroup$
  • $\begingroup$ Can someone who has access to imgur modify this so that the images are ASCII box drawings? $\endgroup$ – Jakob Lovern Apr 6 '18 at 19:33
  • $\begingroup$ Probably a duplicate of Color Configuration 3x3 board (or perhaps that one is a duplicate of this). $\endgroup$ – Rubio Apr 7 '18 at 1:06
5
$\begingroup$

For part 1, pressing

1234678 (in any order)

will solve the grid.

For part 2, note that this game

is almost identical to the game Lights Out. The only difference is that you're instructing us to put all lights on instead. There's a nice article on Wolfram MathWorld about this game, and most observations there apply to your game as well.

One of the observations is that

in a minimal solution, each light needs to be pressed no more than once, because pressing a light twice is equivalent to not pressing it at all.

and another one:

Since the matrix of the above system of equations has maximal rank (it is a 9×9 matrix with nonzero determinant), the game on a 3×3-lattice is always solvable.

Combining that, we see that there are

$2^9$ possible 'moves' and $2^9$ possible positions, so every position has a unique solution (up to reordering of the moves).

Hence,

a position where the solution is pressing 123456789 takes the longest (9 moves). This position is (. = off, x = on):
.x.
x.x
.x.

$\endgroup$
  • $\begingroup$ lol I had no idea, such a game exists... $\endgroup$ – Oray Apr 6 '18 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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