The least amount of pieces on a board with the following conditions:

combinatorial-geometrycombinatorics

There's an infinite board. Imagine you add a rectangle of $m*n$ pieces. With $m,n \geq 2$ (There's a piece every square, and you can't put one above other.) You can make a piece 'jump' other that is next to it (Vertically or horizontally only, not diagonally), if the square next to the "jumped" piece (In the same direction) is empty, also, the "jumped" piece disappears. After many movements, What is the least amount of pieces that can be on the board?

So, it's obvious that the answer can't be $0$ since there's no point of it, it has to be at least one if we have, for example, to pieces left of all the $mn$ pieces that are connected each other.
I tried to do a coloring of the infinite board, in a chess pattern, so we have Black pieces (Pieces in a black tile) and White pieces, this make any white piece unable to make dissapear another white one and the same with black ones. At the end, the least we have of each color the better, because if we get to have only two left with different colors and connected, then we'll know the least number of pieces is 1. i tried looking for different rectangles of pieces, and i got 1 and 2 as answers. For example doing the following when $m=3$ and $n=4$ makes the board have 1 piece at the end: (From left to right)

It clearly follows that it has 1 piece at the end. I found other cases as ($m=2,n=4$), ($m=2, n=5$), but i also found cases where i got the least is 2, like ($m=2, n=3$), ($m=3, n=3$), etc. i haven't noticed anything else besides this. Any suggestions?

Best Answer

This is a fun problem with a nice solution!

First of all, imagine coloring the checkerboard in three colors like so:

A B C A B C A B C ...
B C A B C A B C A ...
C A B C A B C A B ...
...

Let $a,b,c$ be the number of checkers on each color. Each move increases one of these variables by $1$, and decreases the others by $1$. This means that the quantities $a-b,b-c$ and $c-a$ will always have the same parity.

Now, suppose that either $m$ or $n$ is a multiple of $3$. Then you will initially have $a=b=c$, so that $a-b,b-c$ and $c-a$ all start out even. However, if you manage to reduce the board to a single checker, then at least one of $a-b,b-c$ or $c-a$ would be odd. Therefore, the problem is insoluble when $m$ or $n$ is a multiple of $3$.

When neither dimension is a multiple of $3$, you can succeed. Consider the following "T"-move. It allows you to eliminate a $3\times 1$ block of marbles, provided one of the ends has a marble on on side and an empty space on the other:

• • _         _ _ •         _ • •         • _ _     
  •    -->      •    -->      _    -->      _   
  •             •             _             _

Applying this repeatedly, you eliminate a $3\times n$ block from the top of the rectangle, provided $m>3$ and $n\ge 3$:

• • • • • • • • 
• • • • • • • • 
• • • • • • • • 
• • • • • • • • 

|
v

• • • • • • • _ 
• • • • • • • _ 
• • • • • • • _ 
• • • • • • • • 

|
v
• • • • • • _ _ 
• • • • • • _ _ 
• • • • • • _ _ 
• • • • • • • • 

|
v
...
|
v

• • • _ _ _ _ _ 
• • • _ _ _ _ _ 
• • • _ _ _ _ _ 
• • • • • • • •

and then apply the same idea with three sideways T's to get rid of that last $3\times 3$ block. The same idea allows you eliminate three columns at a time provided the dimensions are larger enough.

This procedure allows you to reduce the board either a $4\times 4$, $2\times 4$, $4\times 2$ or $5\times 5$ rectangle, depending on the remainders of $m$ and $n$ modulo $3$. I leave it to you to figure out how to solve these small cases.

Related Solutions

[Math] Covering a chess board with $2$ missing places with $31$ dominoes

Draw a hamiltonian cycle on the chessboard. Any cycle will do, and the following one suffices:

chessboard with hamiltonian cycle

Pick (any) one square and call it $s_0$. Number the following squares in the hamiltonian cycle $s_1, s_2,\ldots s_{63}$:

chessboard with numbered squares

Note that the even $s_i$ are all one color (say pink) and the odd $s_i$ are the other color (say brown). So far this is all very easy.

Now suppose two squares of the opposite colors have been deleted; for example:

chessboard with two squares deleted

The cycle has been cut into two paths, both of which have even length. Such a path is easily covered with dominoes: say one path is $s_k, s_{k+1}, \ldots, s_{k+2j+1}$, where the subscripts are understood mod 64. Then the dominoes easily go onto $(s_k, s_{k+1}), (s_{k+2}, s_{k+3}), \ldots (s_{k+2j}, s_{k+2j+1})$. Similarly the other path is tiled by $(s_{k+2j+3}, s_{k+2j+4}), \ldots, (s_{k-3}, s_{k-2})$.

chessboard tiled with dominoes

This theorem and the proof I have given appear on pages 111–112 of Solomon W. Golomb Polyominoes (revised ed.), Princeton University Press, 1994. The proof is attributed to Ralph Gomory.

What’s the maximal number of chess pieces under this rule

Answer: When $n\ge 3$, the largest number of pieces you can put on the board is $$ \text{max # pieces}=\begin{cases} 2n^2/3 & n \equiv 0\pmod 3\\ (2n^2+1)/3 & n\not\equiv 0\pmod 3 \end{cases} $$ This also works for $n=1$, but for $n=2$, you can fit one more piece than the formula.

How to achieve this maximum: Suppose the squares are labeled by ordered pairs of positive integers, so that $(1,1)$ is the lower left corner and $(n,n)$ is the upper right. Define the $k^{th}$ diagonal to be the set of squares $(x,y)$ for which $x+y-1=k$. This means the $1^\text{st}$ diagonal is a single square $(1,1)$, the $n^\text{th}$ diagonal is the main diagonal with $n$ squares, and the $(2n-1)^\text{st}$ diagonal is a single square, $(n,n)$.

The strategy is to fill the board with pieces, and then remove pieces on the superdiagonal, and every third diagonal after and before it. That is, the set of diagonals with index $n+1+3i$, for all integers $i$ such that there is a diagonal with that index. Here is an example with $n=5$ attaining the optimum of $(2\times 5^2+1)/3=17$.

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

Proof of optimality: First, suppose that $n$ is a multiple of $3$. In this case, the $n\times n$ board can be completely tiled with $1\times 3$ rectangles. The number of tiles is $n^2/3$. Each of these rectangles can contain at most two chess pieces (otherwise you would have three in a row), so you can have at most $2\times n^2/3$ pieces, as claimed.

When $n$ is not a multiple of $3$, you use the same strategy, except this time you tile all but one of the squares with $1\times 3$ and $3\times 1$ tiles. Each of the tiles can have at most two pieces, plus one additional piece on the uncovered square, which comes to $(2n^2+1)/3$.

If $n$ is one more than a multiple $3$, then the leftover tile is one of the corners, and the tiling is pretty easy to find. Here is an illustration when $n=7$:

If $n$ is two more than a multiple of $3$, then the uncovered tile will be at $(3,3)$. On the left is the case $n=5$. For general $n$ in the form $3k+2$, you can do the same strategy by placing the $n=5$ tiling in the lower left corner, and the rest can easily be tiled with $1\times 3$ and $3\times 1$. On the right is an illustration when $n=8$.

Best Answer

Related Solutions

[Math] Covering a chess board with $2$ missing places with $31$ dominoes

What’s the maximal number of chess pieces under this rule

Related Question