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
There is a simple way to see that manshu's answer of $x=25$ is correct.
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.
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.
EDIT: Added an 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.
No comments:
Post a Comment