1
$\begingroup$

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? An example of movements

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) enter image description here

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?

$\endgroup$
  • $\begingroup$ How did you get from your second board to your third? $\endgroup$ – Mike Earnest Aug 21 '18 at 17:46
  • $\begingroup$ Move (3,1) to (5,1) an then move (1,1) to (3,1) $\endgroup$ – SonodaUmi Aug 21 '18 at 17:59
  • $\begingroup$ Then you have a mistake; the checker at (4,1) was hopped over, so should be removed. $\endgroup$ – Mike Earnest Aug 21 '18 at 18:01
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ My teacher said it was a really beautiful solution, and it really is. Thank you! $\endgroup$ – SonodaUmi Aug 21 '18 at 18:25
  • $\begingroup$ @cptnSonoda Does your teacher sit next to you and checked the answer on math.stackexchange (MSE)? $\endgroup$ – callculus Aug 21 '18 at 18:38

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.