# Placing chips on vertices of rectangle such that one corner was initially empty

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.

We can make $49$ moves by always picking rectangles with opposite corners $(1,1)$ and $(x,y)$ for $2 \le x,y \le 8$.
So after the first move (which "wastes" $3$ chips by placing $4$ chips instead of a minimum of $1$), there are $6$ empty rows and $6$ empty columns which require wasting $6+6$ more chips. So we waste at least $15$ chips, allowing us to make at most $64 - 15 = 49$ moves.