# To Catch a Thief

In Alfred Hitchcock's movie "To Catch a Thief", the retired infamous jewel thief John Robie has to crack a safe with a complicated $4\times4$ pattern of keys. Each of the 16 keys is either turned around ($+$) or not turned around ($-$):

   - - + -
+ - - +
- + - -
+ - - +


To open the safe, John Robie must make all keys turned around. The catch is that whenever Robie turns one key (from $+$ to $-$ or from $-$ to $+$), then all the keys in the same row and all the keys in the same column simultaneously turn (from $+$ to $-$ or from $-$ to $+$ respectively). John Robie may turn any key as often as he likes.

Question: What is the minimum number of keys that John Robie has to turn to open the safe?

• Don't think it's a duplicate, but this question is also answered in the comments here. Dec 4, 2015 at 13:34
• Follow-up: What is the maximum number of turns required for any grid? Dec 4, 2015 at 15:49
• Does this answer your question? Is it Always Possible? Colour Flipping May 3, 2022 at 18:18
• @HemantAgarwal that is different: it asks for whether there exists a sequence of moves, whereas this asks for the optimal sequence of moves May 4, 2022 at 5:07

2 turns

To turn a single key without changing the rest of the keys you have to turn the key itself plus the three other keys in the same row plus the three other keys in the same column.

Whe you do this the following happens:

1. Every key you don't turn youself will be turned twice.
Once by the one in the same column as the key you didn't turn and the same row as the key you actually want to turn.
Once by the key in the sam row as the key you didn't turn and the same column as the key you actually want to turn.
Two turns bring the key back to its starting position.

2. Every key in the same row/column as the key you actually want to turn get turned four times.
Once by itself.
Three times by the other keys in the same row/column.
Four turns bring the key back to its starting position.

3. The key you actually want to turn gets turned seven times.
Once by itself.
Three times by the keys in the same row.
Three times by the keys in the same column.
Seven turns bring it to the other position.

Using this on our 10 keys we want to turn we get the following needed turns:

- - + -
+ - - +
- + - -
+ - - +

4 5 6 4
4 4 4 4
4 6 5 4
4 4 4 4


Finally since two turns of the same key result in the starting position we can reduce the number of turns as follows:

0 1 0 0
0 0 0 0
0 0 1 0
0 0 0 0


For a total of 2 turns.

• Have you tried to turn keys this way? I believe it doesn't work. Dec 4, 2015 at 10:29
• @Alissa It does work. It only needs a tiny bit of thinking to try it out. Dec 4, 2015 at 11:10
• Oh, sorry, it appears that I've misread the task. I thought that only keys next to the one we're turning are turned. Dec 4, 2015 at 12:19
• @Vini The two with a '1' on my last table. Dec 4, 2015 at 12:31
• Generalized solution: Find the rows and columns with an odd number of +'s, and turn the -'s where those rows and columns intersect. (Requires there be an even number of such intersections. Otherwise - not sure if it's solvable, need to play with that a bit.) Dec 4, 2015 at 14:31