24
$\begingroup$

Loosely inspired by the game Abalone, I've encountered the following simple problem I cannot solve.
Suppose that we are given a finite set of marbles on an infinite chessboard.
One move consists of one marble jumping over another to an empty space.
For example, if (0,0) and (1,0) have marbles, but (2,0) doesn't, then we can move (0,0) to (2,0).
It is easy to see that there are starting configurations of an even number of marbles that we can "march off" to infinity using such moves.
But is this possible to do with an odd number of marbles?
It feels like this should have a simple explanation, but I don't see any right now.

More on motivation: In Abalone it is useful to start by moving to the center of the board. If one doesn't make sideways moves, then the triangular Abalone board reduces to a chess board. Or almost, because in Abalone it is also allowed to move adjacent marbles in any direction, not just in the direction of the row they are contained in. If one allows that too, then there are more configurations that can do an infinite march. Also, in Abalone one can move at most 3 marbles, so to move as fast as possible, one would always move 3 marbles, and not 2 at a time, but whatever argument works for parity, probably also works for divisibility with 3.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ It's easy to do with 3 marbles if diagonal jumps are allowed, so I presume they're not? $\endgroup$
    – Peter Taylor
    Commented May 2, 2022 at 23:05
  • 1
    $\begingroup$ I assume that each square of the chessboard can accommodate at most one marble? $\endgroup$
    – Timothy Chow
    Commented May 2, 2022 at 23:20
  • 1
    $\begingroup$ Yes and yes - sorry, I haven't noticed these before. $\endgroup$
    – domotorp
    Commented May 3, 2022 at 19:08

1 Answer 1

Reset to default
34
$\begingroup$

With $5$ you can using the following moves:

.....  .....  .....  .....  .....  .....  .....  ..oo.  ...oo 
.....  ..o..  ..o..  ..o..  ..oo.  ...oo  ..ooo  ..ooo  ..ooo 
.oo..  .oo..  .oo..  ..oo.  ..oo.  ..oo.  ..oo.  .....  ..... 
ooo..  oo...  .oo..  ..oo.  ..o..  ..o..  .....  .....  .....

So the only numbers of pieces for which no configuration can go to infinity are $1$ and $3$.

Improve this answer
$\endgroup$
15
  • 1
    $\begingroup$ That's a nice example! To be fair to myself, I had an extra condition that the allowed jumps are only upwards and to the right (see motivation), but when posing the question, I didn't include this. $\endgroup$
    – domotorp
    Commented May 2, 2022 at 20:05
  • 4
    $\begingroup$ I see, I included a new sequence which only has those moves (although it is a bit more complicated) $\endgroup$
    – Saúl RM
    Commented May 2, 2022 at 20:37
  • 3
    $\begingroup$ Wow! beautiful. $\endgroup$
    – Yuval Peres
    Commented May 2, 2022 at 22:40
  • 1
    $\begingroup$ Could you sketch an argument that shows that configurations of larger size can behave the same way? And might there also be disjoint configurations that unavoidably interfere with one another? $\endgroup$
    – Joseph O'Rourke
    Commented May 2, 2022 at 22:59
  • 7
    $\begingroup$ I assumed that with "jumping to infinity" he meant that all the marbles eventually leave any bounded set $\endgroup$
    – Saúl RM
    Commented May 2, 2022 at 23:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .