In the grid shown, 15 cells contain X’s and 10 cells are empty.
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
Any X may be moved to any empty cell. What is the smallest number of X’s that must be moved so that each row and each column contains exactly three X’s?
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:
O
X
X
X
X
O
X
X
X
X
X
X
X
X
X
X
X
(The cells from which X’s have been removed are marked with O’s; the cells to which X’s are moved are marked with X’s.)
Therefore, the smallest number of X’s that must be moved is 2.