12
$\begingroup$

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).

$\endgroup$
0

3 Answers 3

15
$\begingroup$

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.

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.

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.

An example of the bijection

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.)

$\endgroup$
4
  • 3
    $\begingroup$ I wouldn't really call this "simple", "easy", or "clear". Maybe for people with extensive math knowledge (e.g., what in god's name is a 'bijection', and how does that show us anything?) but the other ninety-nine-plus percent of the population is in the dark here. The other answer does a much better, much cleaner job of explaining. $\endgroup$ Feb 24, 2016 at 12:52
  • $\begingroup$ @question_asker It's simple in that the transformation (of the board and of the pawn pieces) is simple. That it is a bijection comes from the fact that on the $10 \times 10$ board, no two red squares may touch and no red square may lie on the blue, extra squares. And the final part is the trivial calculation that $\frac{100}{4} = 25$. I stand by my assertions that these are simple steps an attentive reader can easily grasp. Moreover, this line of reasoning can be easily expanded to other versions of the same problem. $\endgroup$ Feb 24, 2016 at 16:33
  • 1
    $\begingroup$ This comment makes more sense of the explanation to me than the entire post does (again, no real math background here). I still don't know what a bijection is, nor how a bijection (whatever it is) fits into the puzzle. Please understand that I'm not being critical of your reasoning so much as the notion that it will be understood "easily" (implied: by a broad audience). $\endgroup$ Feb 24, 2016 at 16:36
  • 2
    $\begingroup$ @question_asker I am glad you now understand. In any case, I have added an example which should help clarify what's going on. A bijection is a one-to-one correspondence and is in a sense the main object of combinatorics. In combinatorics, one tries to count things that are 'difficult' by showing it is in bijection with something that is 'easier' to count, that is, both have the same number of elements. $\endgroup$ Feb 24, 2016 at 16:48
8
$\begingroup$

Here's what I got

enter image description here

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

enter image description here

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.

$\endgroup$
2
  • 1
    $\begingroup$ While this intuitively seems likely to be the correct value of x, I don't think this constitutes a proof of theorem 2. $\endgroup$
    – Miles
    Feb 24, 2016 at 8:06
  • $\begingroup$ @Miles Done. :) $\endgroup$
    – manshu
    Feb 24, 2016 at 8:19
2
$\begingroup$

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:

7x7 grid

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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