Locker problem
Source: BAMO 1999 P2
February 4, 2017
combinatorics
Problem Statement
A lock has keys arranged in a 4 \times 4 array, each key oriented either horizontally or vertically. In order to open it, all the keys must be vertically oriented. When a key is switched to another position, all the other keys in the same row and column automatically switch their positions too (see diagram). Show that no matter what the starting
positions are, it is always possible to open this lock. (Only one key at a time can be switched.)