20
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I suppose if two or fewer tokens are available on the surrounding squares of a square $S$, then one may not make a move on $S$? $\endgroup$ – Fimpellizieri Feb 8 '16 at 0:25
  • $\begingroup$ @Fimpellizieri Right, a move can only be made if there are at least three tokens in the surrounding squares. $\endgroup$ – f'' Feb 8 '16 at 0:43
  • $\begingroup$ Added the more rigorous proof for not 48 and more information in the construction method for 47. $\endgroup$ – Trenin Feb 9 '16 at 18:57
  • $\begingroup$ I have added proof that 48 cannot be done. $\endgroup$ – Fimpellizieri Feb 10 '16 at 6:37
7
$\begingroup$

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.

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:

  • When $t \equiv 0$ mod $3$, we're simplying transfering them all.
  • When $t \equiv 1$ mod $3$, we leave one token behind.
  • When $t \equiv 2$ mod $3$, we remove the remainder two tokens from $P(n+1)$ and a single token from $P(n)$ to place two new tokens at $P(n)$, for a net gain of one token.

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$.

$\endgroup$
  • $\begingroup$ I've added another answer which also shows 47 tokens. It starts with a square of $n=13$, so a square of $27 \times 27$ like yours. However, there is very little reasoning involved - it is a very straight forward construction right until the last box. $\endgroup$ – Trenin Feb 9 '16 at 14:40
  • $\begingroup$ @Trenin As a side note, we can apply the reasoning in the proof of the $48$ part above to $47$ too; it suffices to take $a_0 = 46$ (instead of $47$). The sequence thus produced has its first non-positive term at $n=13$, so your example is minimal! $\endgroup$ – Fimpellizieri Feb 10 '16 at 7:03
  • $\begingroup$ Well done. Inductive proof is perfect for this. $\endgroup$ – Trenin Feb 10 '16 at 13:02
9
$\begingroup$

General Proof

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$$

Finite maximum

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:

  • n=0: $47-T_0=47-1=46$ tokens added. $46 \times \frac{3}{2}=69$. Add one since we need an extra token in the $n=1$ square.
  • n=1: $70-T_1=70-8=62$: tokens added. $62 \times \frac{3}{2}=93$. Add two since we need two extra tokens in the $n=2$ square.
  • n=2: $95-T_2=95-16=79$ tokens added. $79 \times \frac{3}{2}=120$

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.

Construction method for 47 tokens

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.

  • Starting near the top left corner of $P_{n-1}$ (this is the square at $S_n(1,2)$), take all the tokens in the three squares above it (above to the left, directly above, and above to the right). If divisible by 3, then move them all (using the put 2 remove 3 rule). Otherwise, leave any remainder in the square to the right, or above. Since every square in $S_n$ has at least one token initially, this is always possible.
  • Move to the right one square and repeat.
  • Keep going until you have completed the top row. Now rotate the entire board counter clockwise, and continue the process.

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$.

Example of 47 tokens

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$.

$\endgroup$
  • $\begingroup$ The finite number of moves constraint prevents you from using "all" the tokens so you can reduce this by 1 at least to 48. $\endgroup$ – hexomino Feb 8 '16 at 15:02
  • $\begingroup$ Yep - was in the process of finding the minimum $n$ that allows 48 so I could finish the answer. $\endgroup$ – Trenin Feb 8 '16 at 15:03
  • $\begingroup$ 1. If you can't reach 49, then the most you could theoretically reach is 47, not 48, since they are added in pairs beyond the original token in the center. 2. "should be able to use virtually all of them" is obviously not a proof that you can use sufficiently many of them to get this number (I was thinking of this but still don't have a proof, that may actually require a computer-based search). 3. I have a proof that 47 is an upper bound in any possible method, will post it later today when I have time. $\endgroup$ – user17947 Feb 8 '16 at 15:22
  • 2
    $\begingroup$ It isn't true that you must end up with an odd number of tokens on X. In some situations, moving a single token off X will allow you to add two later. For example, suppose there is a single token on X, a token one square to the right, and two tokens a square to the right of that. We could remove the token from X and the two rightmost tokens to add two tokens to the square to the right of X, then remove all three tokens there to add two tokens to X. $\endgroup$ – Julian Rosen Feb 8 '16 at 16:08
  • 1
    $\begingroup$ Also, to add $k$ tokens at distance $n$, we need $3\lceil k/2\rceil$ tokens at distance $n+1$. It looks like you used $\lceil 3k/2\rceil$ instead. $\endgroup$ – Julian Rosen Feb 8 '16 at 16:12
5
$\begingroup$

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.

$\endgroup$

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.