Wednesday, March 21, 2018

mathematics - Professor Halfbrain and the 9x9 chessboard (Part 1)



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.



From pawns to 2x2 squares


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.


An example of the bijection


No comments:

Post a Comment

classical mechanics - Moment of a force about a given axis (Torque) - Scalar or vectorial?

I am studying Statics and saw that: The moment of a force about a given axis (or Torque) is defined by the equation: $M_X = (\vec r \times \...