There are 64 pawns placed on a chessboard. Each square contains a pawn. Two squares are neighbours of each other if they share a common side.

In the first step, some pawns are removed. Then, at every step thereafter, a pawn is removed from any square with at least two empty neighbours. This continues until the board is empty or no more pawns can be removed.

What is the minimum number of pawns that must be removed in the first step so that all pawns can be removed in the subsequent steps?

[SOLVED]

2 comments

Rajesh Balakrishnan solved this puzzle:

A staircase of n empty squares (along the diagonal) can induce n − 1 neighbouring squares and thus recursively cover the entire board of size n × n. For our 8 × 8 chessboard, 8 empty spaces along the diagonal should be sufficient.

If the furthest empty space in a row (or column) is at m, then it is not possible to create a new empty space at m + 1 as it requires 2 empty sides to create a new empty space. Thus the first step should create empty spaces at the first and last columns/rows.

If there is an empty space at (m, n), a new empty space can be created at (x, y) such that x ≥ m and y ≥ n if and only if it pairs with another empty space at (m + 1, n + 1), (m + 2, n), or (m, n + 2) but not (m + 2, n + 1). It can be visualized as moving through an empty space (to be newly created) to get to its pair. So, the minimum number of steps to a pair is 2. e.g. |(m + 1) − m| + |(n + 1) − n|, |(m + 2) − m| + |n − n|.

The minimum number of steps to (8, 8) from (1, 1) is 14 and thus apart from the first space, we require 7 new spaces at the minimum in the first step.

It is not necessary to place all of them them along the diagonal. Patterns like (1, 2), (2, 1), (3, 4), (4, 3), (5, 6), (6, 5), (7, 8), (8, 7) and (1, 1), (1, 3), (3, 3), (5, 3), (5, 5), (7, 5), (7, 7), (8, 8) also work fine.

Susam Pal from cotpi commented:

The minimum number of steps to reach one square from another is also known as Manhattan distance, L1 distance or ℓ1 norm. In a Cartersian plane the Manhattan distance between (x1, y1) and (x2, y2) is |x1 − x2| + |y1 − y2|.

The Manhattan distance between (8, 8) and (1, 1) is |8 − 1| + |8 − 1| = 14. You have proven that apart from the first empty square, we need an empty square for every Manhattan distance of 2. So, yes, we need a minimum of 1 + 142 = 8 empty squares in the first step.

Credit

This puzzle is based on:

Further reading

The following is a list of resources on related topics:

Post a comment

RSS