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 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .