In the grid shown, 15 cells contain X's and 10 cells are empty. What is the smallest number of X's that must be moved so that each row and each column contains exactly three X's?
Solution
Each of the first and second columns has 4 X's in it, which means that at least 2 X's need to be moved. We will now show that this can be actually done by moving 2 X's. Each of the first and second rows has 4 X's in it, so we move the two X's on the main diagonals, since this will remove X's from the first and second columns and the first and second rows simultaneously. The fifth column starts with one X in it, so we move the two X's to the fifth column into the rows that only contain 2 X's. Doing this, we obtain a grid where each row and column contains exactly three X's.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.