Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this community
One token is placed on each square of an infinite checkerboard. One square is marked with an X. You want to get as many tokens on the marked square as possible. To do this, you may make any finite number of moves, where a move consists of choosing a square, placing two tokens on that square, and removing any three tokens of your choice from the eight surrounding squares.
What is the maximum number of tokens that you can have on the X?
Following in the footsteps of Big Black Box's and Trenin's answers, this shows very concretely that...
$47$ can indeed be achieved.
I tried a lot of different approaches to this problem, but ultimately it's taking the courage to do all the boring calculations that gets the job done. I set up an imgur album here with pictures that contain a (mostly) step by step solution that achieves $47$ tokens on the center.
At the beginning of the process there's plenty of room for choice, which might make it a bit difficult to follow. Still, checking its validity should boil down to performing elementary calculations according to the pictures.
The description of each image (in particular 'From $P(19)$ to $P(18)$') should help the reader understand what's going on. The notation used is also similar to Trenin's; in particular, $P(n)$ refers to squares at Chebyshev distance exactly $n$ from the center (the $X$).
I don't think $48$ is possible, and while Trenin provides a reasoning for why it can't happen in a certain situation, I don't believe it covers all cases. I'm too tired now, but I will think on it.
EDIT: A rigorous proof that $48$ cannot be achieved.
We first point out a few observations. Suppose there are $t$ tokens on $P(n+1)$; if we wish to move them to $P(n)$, the best we can do is moving $\left \lfloor \frac23 t \right \rfloor$ tokens. Studying the parity of $t$ modulo $3$, it's easy to see what's happening:
It's easy to check that these cases agree with the previous formula.
Now, we'll be looking at the reverse process. We will generally consider the lowest amount of tokens (lowest energy configuration) required when backtracking. As a consequence of this and the previous observation, reversion is done by $x \longrightarrow \left \lceil \frac32 x \right \rceil$.
If there were $48$ tokens on the $X$, then $47$ of them must have come from $P(1)$. Thus, before the transfer there must have been $\left \lceil \frac32 \cdot 47 \right \rceil = 71$ tokens on $P(1)$. Since at the beginning there were $8$ tokens on $P(1)$, $71-8=63$ of the tokens must have come from $P(2)$.
We can iterate this process, producing a sequence $a_n$ of numbers that describe how many tokens at least on $P(n)$ must have come from $P(n+1)$. Put another way, $a_n$ is the minimum amount of tokens added to $P(n)$ (beyond those already there at the beginning; the tokens are added from $P(k)$'s with $k>n$) required for $48$ to be achieved on $X=P(0)$.
The sequence is defined by:
$\left\{ \begin{array}{l} a_0 = 47 \\ a_{n+1}=\left \lceil \frac32 a_n \right \rceil – 8(n+1) \end{array} \right.$
Claim: $a_n = 16n+47$
We prove by induction. The base case $n=0$ checks out, so we proceed to the inductive step. We have that $\frac32 (16n+47) = 24n + 70.5$, whence $=\left \lceil \frac32 (16n+47) \right \rceil = 24n + 71$. Now, a simple calculation shows that $24n + 71 -8(n+1) = 16(n+1)+47$, so the sequences satisfy the same recursion, and thus indeed coincide.
The problem here is that this sequence is never $0$ or less. Effectively, this shows that no matter how large we choose $n$, we will always need to work with $P(k)$'s yet farther from $P(n)$. In other words, one cannot transfer enough tokens to the $X$ in finite time/within a finite distance from $X$.
Let $T_n$ be the number of tokens at a Chebyshev distance $n$ from X; fancy way of imagining squares around X of increasing distance $n$ from X.
The values of $T_n$ are;
$$T_1=8$$ $$T_2=16$$ $$T_3=24$$ $$...$$ $$T_n=n \times 8$$
Obviously, the goal is to move tokens towards X by replacing 3 tokens for 2. It makes the most sense to take tokens farther from X and place them closer. So, every move inward from a square will result in $\frac{2}{3}$ of the tokens.
Lets call $V_n$ the value of the tokens in $T_n$. As you move tokens towards X, the number of them decreases by $\frac{2}{3}$ each move.
We see that;
$$V_n=T_n \times \left(\frac{2}{3}\right)^n = 8n\left(\frac{2}{3}\right)^n$$
All we need to do now is solve the values of all the tokens, not forgetting the initial token at $X$.. $$Max = 1 + \sum_{n=1}^{\infty} V_n$$ $$Max = 1 + \sum_{n=1}^{\infty} 8n\left(\frac{2}{3}\right)^n=1+8\sum_{n=1}^{\infty} n\left(\frac{2}{3}\right)^n$$
We know that $\forall x \in (-1,1)$;
$$f(x)=\sum_{n=1}^{\infty} nx^n = \frac{x}{(x-1)^2}$$
So, substituting $x=\frac{2}{3}$, we get; $$Max = 1 + 8 \times f\left(\frac{2}{3}\right) = 1 + 8 \times \frac{\frac{2}{3}}{(\frac{2}{3}-1)^2}$$ $$Max = 1 + \frac{8 \times \frac{2}{3}}{\frac{1}{3}^2}$$ $$Max = 1 + \frac{8 \times 2 \times 9}{3}=49$$
So that is the theoretical number of tokens we can get to X. Actually achieving this is another matter since it would require an infinite number of moves. Thus, in any number of finite moves, the best we could achieve is 48 tokens.
Notice that in order to get 48 tokens, we need to make moves that put 47 tokens on X. However, you can't put an odd number since the rules state you can only remove 3 and add 2. Thus, we can't achieve 48 directly by always moving inward.
Is there another way to get tokens on X? Thanks to @julian-rosen for pointing it out. Lets say you have this situation:
0000
0XYZ
0000
Where $X=47$, $Y=1$, and $Z=2$. You can take one from X and the two off from Z, adding two to Y. Then you will have 3 at Y, which you can remove and place 2 more at X, which gives you 48. This also works if Y and Z are reversed, however that requires more tokens closer, so the first alternative should be easier.
So, in order to have 1 left over in the $n=1$ square and 2 left over in the $n=2$ square with 47 tokens on X, we need the following:
So, we would need 120 tokens in the $n=3$ square. We already know that the $n=3$ square has 24, so we'd only need an additional 96 tokens. The value of these tokens is related to their distance from $X$ as we calculated before. Thus, their value is $V=96 \times \left(\frac{2}{3}\right)^3=28\frac{4}{9}$. From the above equation, we know that $8\sum_{n=1}^{\infty} n\left(\frac{2}{3}\right)^n=48$. We also know that the value of the tokens in the $n=1$ spot is $8\times\frac{2}{3}=5\frac{1}{3}$, and those in the $n=2$ spot are $16\times(\frac{2}{3})^2=7\frac{1}{9}$, and the existing 24 tokens in the $n=3$ square are also $24\times(\frac{2}{3})^3=7\frac{1}{9}$. Thus,
$$8\sum_{n=4}^{\infty} n\left(\frac{2}{3}\right)^n=8\sum_{n=1}^{\infty} n\left(\frac{2}{3}\right)^n - 5\frac{1}{3} - 7\frac{1}{9} - 7\frac{1}{9}=48-19\frac{5}{9}=28\frac{4}{9}$$
Therefore, in order to get 96 tokens into the $n=3$ square would require an infinite number of moves.
Thus, 48 tokens is not possible.
Lets say you have a square centred on X whose Chebyshev distance to $X$ is $n$ or less. We will denote all elements in this square to be the set $S_n$. Furthermore, we will access individual elements by their coordinates. $S_n(0,0)$ will be the square in the top left. $S_n(n,n)$ will be the element at X.
As well, we will denote perimeter squares whose Chebyshev distance to $X$ is exactly $n$. These perimeter squares will be called $P_n$ and will employ the same coordinate system.
We will move all the tokens in $P_n$ to $P_{n-1}$ as follows.
Eventually, you will return to $S_n(1,1)$ and the only tokens left in $P_n$ will be the remainder after dividing by 3.
Continue this process until you are left with a $3\times 3$ square around X. Then move all the tokens into the middle using the remove 3 add 2 rule.
If $n$ is large enough, you will end up with a string of 2s in the remainder of each square leading to the centre with 45 tokens on $X$. These can be collapsed to a string of 1s leading to the centre with a 47 on $X$ using julian's move. The earliest this is possible is at $n=13$.
Here is an example of how to get 47 tokens. It uses the construction method outlined earlier; moving clockwise from the top left, move the outer tokens inward, propagating the remainder clockwise. Any remainder from the outer ring of tokens is left over in the square under the top left square.
The remainder tokens are shown as they are generated, but to keep the graphics small, they are ignored unless needed as we get closer to $X$.
n=13 n=12
111111111111111111111111111 1 n=11
111111111111111111111111111 11311311311311311311311313 1
111111111111111111111111111 1111111111111111111111111 113331313311331313311335
111111111111111111111111111 3111111111111111111111113 11111111111111111111111
111111111111111111111111111 1111111111111111111111111 31111111111111111111113
111111111111111111111111111 1111111111111111111111111 31111111111111111111113
111111111111111111111111111 3111111111111111111111113 11111111111111111111111
111111111111111111111111111 1111111111111111111111111 31111111111111111111111
111111111111111111111111111 1111111111111111111111111 11111111111111111111113
111111111111111111111111111 3111111111111111111111113 31111111111111111111113
111111111111111111111111111 1111111111111111111111111 31111111111111111111111
111111111111111111111111111 1111111111111111111111111 11111111111111111111113
111111111111111111111111111 3111111111111111111111113 11111111111111111111111
111111111111111111111111111 1111111111111111111111111 31111111111111111111113
111111111111111111111111111 1111111111111111111111111 31111111111111111111113
111111111111111111111111111 3111111111111111111111113 11111111111111111111111
111111111111111111111111111 1111111111111111111111111 31111111111111111111111
111111111111111111111111111 1111111111111111111111111 11111111111111111111113
111111111111111111111111111 3111111111111111111111113 31111111111111111111113
111111111111111111111111111 1111111111111111111111111 31111111111111111111111
111111111111111111111111111 1111111111111111111111111 11111111111111111111113
111111111111111111111111111 3111111111111111111111113 11111111111111111111111
111111111111111111111111111 1111111111111111111111111 31111111111111111111113
111111111111111111111111111 1111111111111111111111111 31111111111111111111113
111111111111111111111111111 3111111111111111111111113 51331133131331133131333
111111111111111111111111111 3113113113113113113113113 Outer ring tokens: 196
111111111111111111111111111 Tokens in outer ring: 164
Tokens in outer ring: 104
n=10
1171313331331333311337 n=9
311111111111111111113 3733331331333331339 n=8
311111111111111111113 3111111111111111113 23933133333333133b n=7
311111111111111111111 3111111111111111113 31111111111111113 3b133333333133b
111111111111111111113 3111111111111111113 31111111111111111 311111111111113
311111111111111111113 1111111111111111111 31111111111111113 311111111111113
111111111111111111111 3111111111111111113 11111111111111113 311111111111113
311111111111111111113 1111111111111111113 31111111111111113 311111111111113
311111111111111111113 3111111111111111113 11111111111111113 311111111111113
311111111111111111113 3111111111111111113 31111111111111113 111111111111113
111111111111111111113 3111111111111111111 31111111111111113 311111111111113
311111111111111111111 3111111111111111113 31111111111111113 311111111111113
311111111111111111111 3111111111111111113 31111111111111113 311111111111113
111111111111111111113 3111111111111111113 31111111111111113 311111111111113
311111111111111111113 1111111111111111113 31111111111111113 311111111111113
311111111111111111113 3111111111111111113 31111111111111111 311111111111113
311111111111111111113 3111111111111111111 31111111111111113 311111111111113
311111111111111111111 3111111111111111113 31111111111111113 d1333133333333b
111111111111111111113 3111111111111111113 b133313333333313b Outer ring: 192
111111111111111111113 9133313333333113339 Outer ring: 204
913331331333311333317 Outer ring: 212
Outer ring: 210
n=6
3b3333333133d n=5
3111111111113 23b33333333d n=4
3111111111113 31111111113 3b333333f n=3
3111111111113 31111111113 311111113 13b3333f n=2
3111111111113 31111111113 311111113 3111113 3b33f n=1
3111111111113 31111111113 311111113 3111113 31113 23bf
3111111111113 31111111113 311111113 3111113 31113 313
3111111111113 31111111113 311111113 3111113 31113 f3f
3111111111113 31111111113 311111113 3111113 f333f R: 68
3111111111113 31111111113 311111113 f13333f R: 92
3111111111113 31111111113 f1333333d R: 114
3111111111113 d133333333d Ring: 136
d13333333333b Ring: 156
Ring: 176
This leaves the final position before moving all the tokens to $X$ as:
23bf
3X3
f3f
With 68 tokens surrounding $X$. The first move is to take the 2 remainder tokens and one of the tokens surrounding $X$ and replace them with 2 tokens as follows:
02bf
5X3
f3f
We now have 69 tokens surrounding $X$. Trivially, we can remove all 69 and add 46 to $X$, leaving us with 47 tokens on $X$.
Here is a proof that the largest number of tokens that one can get on the X is 48. (I also suspect it can't be higher than 47, but Julian Rosen's comment to Trenin's answer shows that, if true, showing that would require a separate argument.) Of course I should note that this proof was inspired (as I believe the puzzle was too) by a very beautiful and fairly well-known math puzzle called Conway's soldiers.
Define an "energy function" that associates with each state $x$ of the board a positive number $E(x)$, given by
$$ E(x) = \sum_{\textrm{tokens } T} (2/3)^{d(T,X)}, $$ where $d(T,X)$ denotes the Chebyshev distance (the same one referred to in Trenin's answer) of the token to the X. Note that this is a convergent infinite series. Its value at the initial board state $x_0$ is \begin{align} E(x_0) &= 1 + 8\cdot (2/3) + 16\cdot (2/3)^2 + 24 \cdot (2/3)^3 + 32\cdot(2/3)^4 + \ldots \\ &= 1+8 \sum_{n=1}^\infty n \left(\frac{2}{3}\right)^n = 1+8 {\sum_{n=1}^\infty n\, t^n}_{\big|t=\frac23} =1+8 {\frac{t}{(1-t)^2}}_{\big|t=\frac23} = 1+8\frac{\phantom{(}\frac23\phantom{)^2}}{\left(\frac13\right)^2}=49. \end{align}
Lemma. In any legal move, the energy can only decrease or stay the same.
Proof. A legal move replaces three tokens, whose contribution to the energy sum is $$ (2/3)^a + (2/3)^b + (2/3)^c, $$ with two tokens, whose contribution to the sum is $$ 2\cdot(2/3)^d, $$ where $d$ is the Chebyshev distance between X and the position Y where the tokens are added, and $a,b,c$ is the Chebyshev distance between X and the position where the tokens are deleted. Since those positions are all neighboring positions to Y, all the numbers $a,b,c$ are between $d-1$ and $d+1$. If $a,b,c=d+1$ then the net change to the energy is $$ 2\cdot(2/3)^d - 3\cdot(2/3)^{d+1} = 0, $$ i.e., the energy remains the same. In all other cases it is easily checked that the energy decreases.
Proof that the number of tokens on the X can never exceed 48. The energy of the board at the beginning is 49. By the lemma, after any finite sequence of moves the energy is still less than or equal to 49. This includes some positive amount of energy due to tokens that are far away and weren't touched by the sequence of moves, so in practice at most 48 units of energy that can be contributed to the energy sum by tokens at the X, each of which contributes one unit of energy to the sum.
Edit: Added thoughts about how to achieve a matching lower bound. From the proof it is apparent that if we are to have hope of constructing a solution that actually manages to bring 48, or close to it, tokens to the X, such a solution must minimize the loss in energy - too many steps that decrease energy can bring the energy down below 48 or 47, thus limiting the number of tokens we can bring to the X. In particular, this line of reasoning shows that the best strategy would consist of drawing tokens in closer and closer from concentric squares of increasing Chebyshev distance from X - precisely the kind of strategy envisioned in Trenin's answer, that uses only moves that keep the energy the same. Now, this is the general idea, but it seems like there are some highly nontrivial details involved in showing that one can actually manage to concentrate enough of the energy at the X without "energy losses" due to the numbers of tokens in one of the concentric squares not being precisely divisible by 3, or tokens not being close enough to each other to be usable together, etc. So, further arguments and perhaps even a computer-based search may be needed to completely nail down the precise answer to the question.
