6
$\begingroup$

This little problem crossed my mind and appeared to be not quite trivial.

How can you place P pawns on a chessboard with the constraint that no pawn is exactly midway between two other pawns?

Sure enough, this problem has been studied before. The question of maximizing P on a board of size NxN already has an OEIS sequence. For an 8x8 board, the maximum is 26. (And by the way, the placement is unique up to rotation and reflection.)

But I don't want a solution that says "Here is the solution. How? Integer programming.". So I am setting the "no-computers" tag. I am asking for a human-friendly solution, which is a solution where you can explain why it is correct without a "brute-force" check of all possible alignments. This is possible as far as I know for P=24.

In summary, show an arrangement of 24 pawns on a 8x8 chessboard such that no pawn is exactly midway between two others and prove with words that it works.

PS: I wish I didn't have to mention it, but pawns are always placed in the exact center of a square.

$\endgroup$
1

2 Answers 2

7
$\begingroup$

    x x . . . . x x
    x . x . . x . x
    . x x . . x x .
    . . . . . . . .
    . . . . . . . .
    . x x . . x x .
    x . x . . x . x
    x x . . . . x x
 

Why?

Each of the (3x3) corners by itself does not even have three in a straight line, let alone equidistant. Any line of pawns involving more than one corner must skip at least 2 middle column or rows; skipping another 2 is sure to end outside the board.

$\endgroup$
1
  • $\begingroup$ This is different from the answer I found, but it is related to mine in an interesting way. Maybe someone will post it. For time being you get the check mark. $\endgroup$
    – Florian F
    Jan 21 at 13:28
3
$\begingroup$

Before this question gets lost in oblivion I would like to give my own solution.

    x x . x x . . .
    x x . x x . . .
    . . . . . . . .
    x x . . . . x x
    x x . . . . x x
    . . . . . . . .
    . . . x x . x x
    . . . x x . x x

I like it because

It relates to Albert's solution in the sense that his answer is a square of small diamonds, mine is a diamond of small squares.

Proof of validity:

If two of the pawns belong to the same square, then the third lies just outside. Therefore any line must use one pawn from three different squares.
If two of these squares are aligned horizontally or vertically, there is no third square suitably placed to provide a third pawn.
The only choices left for the three squares are those where the squares form an acute triangle, and these can obviously not provide three aligned pawns.

$\endgroup$

Your Answer

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

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