0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

We can make $49$ moves by always picking rectangles with opposite corners $(1,1)$ and $(x,y)$ for $2 \le x,y \le 8$.

This is best possible because:

  • Each move places at least one chip;
  • Each move that places a chip in a given row for the first time places at least two chips in that row;
  • Each move that places a chip in a given column for the first time places at least two chips in that column.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.