12
$\begingroup$

In a $8\times8$ chessboard, a cell is qualified if an adjacent cell (a cell which is on top, left, below, or right of the cell) excluding itself has a chess piece on it. How many chess pieces do we have to put in order to have all cells qualified?

$\endgroup$
14
$\begingroup$

Here is a solution with

20

pieces.

The black squares are the pieces.
enter image description here

The colouring of the empty squares ($2\times2$ in white, $4\times4$ in yellow, $6\times6$ in orange, $8\times8$ in red) shows how the pattern generalises to any $2k\times2k$ board.

For $8\times 8$ this solution is optimal.

The two colours of the chessboard split the problem into the two equivalent independent smaller problems of qualifying the 32 squares of one colour by placing pieces on the other colour. Every piece qualifies at most 4 squares, so obviously we need at least 8 to qualify a whole colour. To increase that bound, we need to see how many pieces we need to place that only qualify 3 or fewer squares. Let's call those 3-pieces.

. o . o . o . o
o . o . o . o .
. o . o . o . o
o . o . o . o .
. o . o . o . o
B . o . o . o .
. B . o . o . o
A . B . o . o .

In the above board, the corner square marked A can only be qualified by a piece on an adjacent square. That will be a 3-piece that qualifies two B squares as well. The remaining B square can only be qualified by another 3-piece (either on the edge of the board, or it shares another B-square). The same goes for the opposite corner as well, so we have used four 3-pieces, and have 20 squares remaining. It is fairly easy to see that it is impossible to qualify the remaining squares using five 4-pieces, whichever way you do each corner So at least 10 pieces are needed for one colour, and 20 pieces are needed to qualify the whole board.

| improve this answer | |
$\endgroup$
7
$\begingroup$

Here is a highly symmetric solution with 20 pieces.

enter image description here

Clearly, pieces has to be placed in pairs, otherwise the cell with one piece on it is not qualified.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Nice one. Note that they don't necessarily have to come in pairs, rather all pieces need to have a neighbouring piece. They could come in triples, or be connected in long stretches. $\endgroup$ – P1storius Mar 9 at 12:39
3
$\begingroup$

As @Jaap Scherphuis explains, 20 is the least amount of pieces needed to get all cells qualified. Couldn't find anything less than that. But the comment of @P1storius on the answer of @daw got me thinking, how many pieces do I need to get all cells qualified when not only using pairs but strings of pieces?


The answer: it requires 21 pieces as shown below. I used trial and error to find the solution. 21 pieces

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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