9
$\begingroup$

Imagine a semi-infinite grid-line in which every box can hold any number of balls.

+--+--+--+--+--+--+--+--+--+--+--
|  |  |  |  |  |  |  |  |  |  |    ... (infinity)
+--+--+--+--+--+--+--+--+--+--+-- 

The balls are a bit special as they can undergo fission and split up into two balls, one going into every direct neighbor box. The reverse process of ball-fusion is also possible! It combines two balls, which have a box in-between, to form one ball which is then added to the in-between box.

--+--+--+---+--+--+--                        --+--+---+---+---+--+--
  |  |  | O |  |  |    <--fusion/fission-->    |  | O |   | O |  |   
--+--+--+---+--+--+--                        --+--+---+---+---+--+-- 

It is important to remember that any box can hold multiple balls.

You are now tasked to find out whether the right order of ball-fission and -fusion can lead form this configuration:

+--+--+--+--+--+--+---+--+--
|  |  |  |  |  |  | O |  |   ... (only empty ones after this)
+--+--+--+--+--+--+---+--+-- 

to this one:

+--+---+--+--+--+--+--+--+--
|  | O |  |  |  |  |  |  |   ... (only empty ones after this)
+--+---+--+--+--+--+--+--+-- 

Bonus:

What about reaching the end-configuration which has exactly one ball in the very first box, starting from one of the earlier two?

Bonus Bonus:

Actually, can we always say when some configuration is reachable from some other configuration? (Given both only have a finite amount of balls)

$\endgroup$
3
  • $\begingroup$ This looks like a great puzzle, but I have some questions: 1. it seems that fission doesn't require the target boxes to be empty, but fusion requires the target box to be empty. Therefore the operations are not always invertible. Is this the intended rule? 2. Can a ball split into two and the two goes both to the left or to the right? If not, then it seems that the "end-configuration" cannot do anything, and no configuration can reach it. Is that true? $\endgroup$ – WhatsUp May 14 at 19:47
  • $\begingroup$ @WhatsUp 1: Ah I should state this differently! In both cases the boxes don't need to be empty. For example you can do fusion and get an additional ball to a box. 2: No this is intended to be strict. When splitting, each side gets one ball; no two balls on only one side allowed. The end-configuration can do something; you can split the ball that is in Box 2 and after that more possibilities open up. Any further feedback is very welcome; I am sure there is still room for a clearer formulation of the puzzle statement. $\endgroup$ – Lereau May 14 at 20:07
  • $\begingroup$ @WhatsUp I only now noticed what "end-configuration" you are talking about. I here you are correct. $\endgroup$ – Lereau May 14 at 20:21
7
$\begingroup$

Answer to the original question:

Any (finite) configuration can be represented by a polynomial in $\Bbb Z[x]$, by regarding the number of balls in the $i$-th box as the coefficient before $x^i$.

Any fission or fusion corresponds to adding or subtracting a polynomial of the form $x^{i + 1} - x^i + x^{i - 1}$ to the original polynomial.

Therefore, if two configurations can be obtained from each other, then the difference of the two corresponding polynomials is a multiple of the polynomial $x^2 - x + 1$. Note however that this is a necessary and not always sufficient contidion, as can be seen from the answer to "bonus" below.

If both configurations are "one-ball configurations", then the difference polynomial looks like $x^m - x^n$. This is a multiple of $x^2 - x + 1$ if and only if $m - n$ is a multiple of $6$.
Hence the two configurations in the question cannot be obtained from each other.

An equivalent argument is to assign the $i$-th box a "weight" of $\omega^i$ with $\omega = \frac{1 + \sqrt{-3}}2$ a primitive sixth root of unity. Then each fission or fusion doesn't change the total weight of all balls.

Answer to "bonus":

As the fission and fusion operations are inverse to each other, it suffices to note that there is no possible operation from the end-configuration, hence no other configuration can reach it.

I don't have answer to "bonus bonus" yet, but I have the following observation:

If there is a ball in box $i$ with $i > 0$ (that is, not the left most box), then we can transform it to a ball in box $i + 6$:
010000000
101000000
110100000
111010000
111101000
111110100
111111010
020111010
011011010
010101010
At this point it becomes symmetric. Just reverse the above procedure but with left-right symmetry.

My feeling is that the necessary condition describe above is "almost sufficient", that is, up to small issues at the left most box. The idea of the proof should be

to transform everything into just two neighboring boxes.

$\endgroup$
1
$\begingroup$

For the bonus bonus,

Let the initial and final desired lines $A$ and $B$ correspond to polynomials $a(x)$ and $b(x)$ with nonnegative integer coefficients; by the same reasoning, $x^2-x+1$ divides $a(x)-b(x)$. Obviously, if one of the lines only has a ball in the first box, the move is possible iff the two lines are identical. Else, first manipulate $A$ and $B$ using fission to put a ball in box $2$ in both lines. Then consider the operation changing the new $A$ to the new $B$, possibly allowing boxes to have a negative number of balls. Starting with the new $A$, use fission repeatedly to replace the ball in box $2$ with arbitrarily many more balls in the first $t$ boxes for a large integer $t$, and do the same with new $B$. Then apply the operation previously described to solve the problem.

Example: 20101 to 1001001: 20101 -> 21011 (fission from the beginning), 1001001 <- 1010101 <- 1101101 (fission in reverse from the end), so we need 21011 -> 1101101. To do this, note that $x^6+x^4+x^3+x+1-x^4-x^3-x-2=x^6-1=(x^2-x+1)(x^4+x^3-x-1)$ so the operation is $x^4+x^3-x-1$. This would be 0 0 0 0 0 0 0 -> -1 1 -1 0 0 0 0 -> -1 0 0 -1 0 0 0 -> -1 0 0 0 -1 1 0 -> -1 0 0 0 0 0 1. Then do 21011 -> 30111 -> 31021 -> 31112 -> 311211 -> 3112201 = 20011 + 1111101 and 1101101 <- 2011101 <- 2102101 <- 2111201 <- 2112111 <- 2112202 = 1101101 + 1111101. Thus we want 3112201 -> 2112202, which can be done as 3112201 -> 2202201 -> 2111201 -> 2112111 -> 2112202 (using the previous procedure of $x^4+x^3-x-1$).

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