# 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 '15 at 13:34
• Follow-up: What is the maximum number of turns required for any grid? Dec 4 '15 at 15:49

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 '15 at 10:29
• @Alissa It does work. It only needs a tiny bit of thinking to try it out. Dec 4 '15 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 '15 at 12:19
• @Vini The two with a '1' on my last table. Dec 4 '15 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 '15 at 14:31