On an $8\times8$ chessboard, a move consists of adding one chip to each of the four corners of a rectangle (whose sides are parallel to the sides of the board), on the condition that one of the corners was empty. Starting with a grid with no chips, what is the maximum number of moves that can be made?
A crude upper bound is $60$: the first move places chips on four distinct squares, and each subsequent move adds a chip to at least one empty square.
For a $4\times4$ board, I've managed to convince myself that you can do no better than $9$ moves. Intuitively, you want to be making lots of moves where you only add a chip to one empty square at a time, to maximise the possible number of moves.