Sunday, October 16, 2016

logical deduction - Is it Always Possible? Colour Flipping


There's a 4x4 square, where switches are either red or green. When you flip a switch, all the buttons on that row and column will change color.



Is every starting position possible to complete? If not how many are there that are impossible?


Note: To complete all tiles must be green!


Letting 1s be red and 0s be green, here's an example flip;


 1011
0010
1111
0000

After:


1001

0000
0000
0010

The button press for above was the 3rd column, 3rd row.



Answer



It's always possible.


In order to flip a single switch, you flip it once, and all switches in the same row or column, in any order. The switch itself will be flipped 7 times, the switches in same row or column 4 times, the other switches twice. Which means all other switches will stay the same color.


Example:


0000        0010        1101        1111        1101        0101        0001        0000

0010 -3,2-> 1101 -3,1-> 1111 -3,3-> 1101 -3,4-> 1111 -1,2-> 0000 -2,2-> 1111 -2,4-> 0000
0000 0010 0000 1111 1101 0101 0001 0000
0000 0010 0000 0010 1101 0101 0001 0000

Using this technique, we can switch the red switches to green one by one. It will not be the most efficient solution in most cases, but it is possible.


Credit goes to @mdc32, his JSFiddle gave me an awesome blackboard!


No comments:

Post a Comment

classical mechanics - Moment of a force about a given axis (Torque) - Scalar or vectorial?

I am studying Statics and saw that: The moment of a force about a given axis (or Torque) is defined by the equation: $M_X = (\vec r \times \...