Professor Halfbrain and the 9x9 chessboard (Part 1)

Question

Professor Halfbrain has spent has spent the last few days with placing pawns on a $9\times9$ chessboard; each of the $81$ squares on the chessboard had side length $1$. Halfbrain always started with an empty board, and then one by one placed (point-sized) pawns onto it. Every pawn was placed precisely in the middle of one of the little chessboard squares. Whenever Halfbrain placed a new pawn, its distance to each of the pawns placed before was at least $2$.

Professor Halfbrain has proved two extremely deep theorems on such placements of pawns.

Professor Halfbrain's first theorem: It is possible to place three pawns according to the above rules.

Professor Halfbrain's second theorem: It is not possible to place $81$ pawns according to the above rules.

This puzzle asks you to improve the two theorems of professor Halfbrain and to make them even deeper. Find an integer $x$, so that "three pawns" in the first theorem may be replaced by "$x$ pawns", and so that "$81$ pawns" in the second theorem may be replaced by "$x+1$ pawns" (again yielding true statements, of course).

Answer 1

There is a simple way to see that manshu's answer $x=25$ is correct.

Translate the problem into an easier problem:

Rather than consider a $9\times 9$ board and pawns, consider a $10 \times 10$ board and $2 \times 2$ square pieces. We can associate to each pawn configuration on the $9 \times 9$ board a unique configuration of squares in the $10 \times 10$ board; consider the image below.

The blue squares are the squares we added to our board to make it $10 \times 10$. The $2 \times 2$ square on the side is a piece for our new board, and the red square marks where the pawn lies for our previous board. It's easy to see this relation is a bijection.

For example in the image below, to the left we have the $9 \times 9$ board in which red squares mark pawn positions. To the right is the corresponding $10 \times 10$ board with $2 \times 2$ square pieces; notice the position of red squares is preserved and no pieces overlap.

Solution of the puzzle

Solving Professor Halfbrain's problem now becomes the same as solving the translated problem: How many $2 \times 2$ square pieces can we place on a $10 \times 10$ board without overlappings?
Now, our new board has a total of $100$ squares, and each piece uses up $4$ squares. It's thus clear that no configuration can go beyond $25$ pieces.
On the other hand, it is possible to place $25$ pieces on the chessboard. (Just fill the board up until no space is left.)

Answer 2

Here's what I got

In this

Every dot represents a pawn. If I counted it correct then it is $9 \times 9$ board. Distance between two pawns is 2 units. And there are total $25$ pawns. To make this, I first placed the pawn on first row and first column and kept filling the grid according to the rules.

But

If I place the pawn on first row and second column then

I'll get

In this

Total number of pawns are $22$ which is lower then the first case. Same can be done if I start placing the pawns from Row 2 and Column 2. In that case total number of pawns placed will be $18$.

Therefore,

Theorem 1 (corrected):

It is possible to place 25 pawns according to the rules.

Theorem 2 (corrected):

It is not possible to place 26 pawns according to the rules.

Answer 3

Not a math person, so this is more of an observation than a proof:

Professor Halfbrain's improved first theorem: For a square board of $S^2$ spaces, it is possible to place $\left \lceil\frac{S}2 \right \rceil^2$ pawns according to the above rules.

Professor Halfbrain's improved second theorem: For a square board of $S^2$ spaces, it is not possible to place more than $\left \lceil\frac{S}2 \right \rceil^2 + 1$ pawns according to the above rules.

Explanation:

For a 7x7 grid, 4 rows of 4 pawns can be placed while following Professor Halfbrain's rules. Increasing the grid to an 8x8 grid doesn't increase the max number of pawns that can be placed. So for a square grid of width 7 or 8, the max number of pawns is 4, or $\left \lceil\frac{\text{width}}2 \right \rceil$. For a 9x9 grid, this gives 25 pawns, for a 1x1 grid, this gives a maximum of 1 pawn.