0
$\begingroup$

Define a game on a number line as follows: at the beginning, there are (possibly) some tokens at some negative integers on the number line. Each integer can hold any number of tokens. At each step, before you move a token to an adjacent integer, an adjacent token (not at the same integer) must be $\color{red}{\text{removed}}$ as a cost. If you can let a token reside at some integer after a finite number of moves, it is said that the integer is "reachable". Your goal is to obtain the maximum "reachable" integer.

For example, suppose there are two tokens at $-2$ and three tokens at $-1$. Via the following moves, you can reach the integer $2$: \begin{array}{|c|c|c|c|c|c|} \hline \text{integers} & -2 & -1 & 0 & 1 & \color{red}{\textrm{2}} \\ \hline \text{beginning} & 2 & 3 & 0 & 0 & 0 \\ \hline \text{after move } 1 & 1 & 2 & 1 & 0 & 0 \\ \hline \text{after move } 2 & 0 & 1 & 2 & 0 & 0 \\ \hline \text{after move } 3 & 0 & 0 & 1 & 1 & 0 \\ \hline \text{after move } 4 & 0 & 0 & 0 & 0 & 1 \\ \hline \end{array} In the table, the first row means the integers while each of the following row represents the tokens after a move. We can see that the maximum reachable integer is $2$.

I'd like to ask, given an initial distribution of tokens, how to calculate the maximum reachable integer? An analysis on simple cases (for example, there are tokens on integers $-1$ and $-2$ only) are also appreciated.

$\endgroup$
3
  • 2
    $\begingroup$ What have you tried? $\endgroup$ Apr 7, 2019 at 17:38
  • 1
    $\begingroup$ @BadAtGeometry understandable question, but I am just putting this link out there so we all know... $\endgroup$
    – Mr Pie
    Apr 8, 2019 at 5:05
  • 1
    $\begingroup$ @user477343 Oh thank you! $\endgroup$ Apr 10, 2019 at 1:26

1 Answer 1

4
$\begingroup$

This is the one-dimensional version of the (cool and interesting!) two-dimensional "Conway's soldiers" problem. In particular, you're essentially replacing a pair of tokens on spaces $n-2$ and $n-1$ with a token on space $n$, which means that assigning weight $\phi^n$ to space $n$ (where $\phi$ is the golden ratio) is preserved by this token move. In your example, the initial weighted sum of tokens is $$ 2\cdot\phi^{-2}+3\cdot\phi^{-1} = \frac{3+\sqrt5}2 = \phi^2, $$ which is a proof that no integer greater than $2$ is reachable for this example.

$\endgroup$
2
  • $\begingroup$ Yes, two games are identical in one-dimensional case. But in the two-dimensional extension, this game seems different from Conway's game due to different "remove" rule. May I ask how to analyze this game in two-dimensional extension? $\endgroup$
    – Hang Wu
    Apr 7, 2019 at 18:17
  • $\begingroup$ @HangWu, Can you help me this problem:math.stackexchange.com/questions/3213078/… $\endgroup$
    – know dont
    May 4, 2019 at 22:57

You must log in to answer this question.

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