26
$\begingroup$

This problem has been originally posted at math.stackexchange.

Since there are no answers and no comments there yet, I am crossposting it here to know if it is already known and tractable.

Here is the problem, slightly restricted with respect to the original:

starting from a multiset of $6$ integer numbers, we modify it repeatedly by replacing two elements $a,b$ at choice with $a+b,a+b$. Is it possible to make all elements equal for any choice of the original multiset? Does the answer change if we replace "integer" with "rational"?

Note that the original poster at math.stackexchange seems to have a proof for $n=3,5$ elements. As noted in comments below, it is impossible to equalize $a,a,b$ with $a \gt b \ge 0$, because you will have another sequence of the same form.

Improve this question
$\endgroup$
11
  • 7
    $\begingroup$ If we can make six integers equal with these moves then we can also make six rationals $r_i$ equal, by applying to the $r_i$ the moves that work for the integers $n r_i$ where $n$ is a common denominator. So the question for “rational” is the same as for “integer”. $\endgroup$
    – Gro-Tsen
    Commented Aug 6, 2023 at 14:26
  • 3
    $\begingroup$ I think the game should be studied with elements of $\mathbb{Z}^6$, starting with the canonical basis. If it can be solved for this “universal” case then by simple linear algebra it can be solved for any Abelian group, as @JoelDavidHamkins hints. $\endgroup$
    – Gro-Tsen
    Commented Aug 6, 2023 at 14:35
  • 3
    $\begingroup$ Why six numbers? Do you have a solution for five numbers? $\endgroup$
    – Denis Shatrov
    Commented Aug 6, 2023 at 15:18
  • 4
    $\begingroup$ This question is almost the same as this one: mathoverflow.net/questions/421671/…? $\endgroup$
    – domotorp
    Commented Aug 6, 2023 at 15:23
  • 4
    $\begingroup$ @domotorp that one is much simpler. With $(a+b)/2$ the sum of all elements is constant therefore if the original sequence is e.g . $0,0,0,0,0,1$ it won't work. $\endgroup$
    – Fabius Wiesner
    Commented Aug 6, 2023 at 15:28

4 Answers 4

Reset to default
26
$\begingroup$

I claim that it is always possible to make all of the integers equal to each other. To see this, consider the allowable transformations

  1. $(a,b,c,d,e,f)\mapsto(a+b,a+b,c,d,e,f)$,

  2. $(a_1,\dots,a_6)\mapsto(a_{\sigma(1)},\dots,a_{\sigma(6)})$, and

  3. $(a,b,c,d,e,f)\mapsto(a/n,b/n,c/n,d/n,e/n,f/n)$ whenever $a/n,b/n,c/n,d/n,e/n,f/n$ are all integers.

We shall write $(a,b,c,d,e,f)\mapsto^*(g,h,i,j,k,l)$ if $(g,h,i,j,k,l)$ can be obtained from $(a,b,c,d,e,f)$ by using a sequence of allowable transformations. We observe that if $(a,b,c,d,e,f)\mapsto^*(1,1,1,1,1,1)$, then can transform $(a,b,c,d,e,f)$ into $(n,n,n,n,n,n)$ for some $n$ using only transformations $1$ and $2$, but transformation 3 makes it easier to use induction to show that we can always get $(a,b,c,d,e,f)\mapsto(1,1,1,1,1,1)$.

We observe that $(a,b,c,d,e,f)\mapsto^*(a+b+c+d,a+b+c+d,a+b+c+d,a+b+c+d,e+f,e+f)$. Now set, $\alpha=a+b+c+d,\beta=e+f$. I claim that $(\alpha,\alpha,\alpha,\alpha,\beta,\beta)=(0,0,0,0,0,0)$ or $(\alpha,\alpha,\alpha,\alpha,\beta,\beta)\mapsto^*(1,1,1,1,1,1)$ by induction on the square of the $\ell^2$ norm $4\alpha^2+2\beta^2$ of $(\alpha,\alpha,\alpha,\alpha,\beta,\beta)$.

Case 0: $\alpha=0,\beta=0$. This is trivial.

Case 1: $\alpha=0,\beta\neq 0$. In this case, $(\alpha,\alpha,\alpha,\alpha,\beta,\beta)\mapsto^*(\beta,\beta,\beta,\beta,\beta,\beta)\mapsto^*(1,1,1,1,1,1)$.

Case 2: $\alpha\neq 0,\beta=0.$

$(\alpha,\alpha,\alpha,\alpha,\beta,\beta)\mapsto^*(\alpha,\alpha,\alpha,\alpha,\alpha,\alpha)\mapsto^*(1,1,1,1,1,1)$.

Case 3: $\alpha\neq 0,\beta\neq 0$, $\alpha$ is even.

If $\alpha$ is even, then $(\alpha,\alpha,\alpha,\alpha,\beta,\beta)\mapsto^*(\alpha,\alpha,\alpha,\alpha,2\beta,2\beta)\mapsto^*(\alpha/2,\alpha/2,\alpha/2,\alpha/2,\beta,\beta)$ and $(\alpha/2,\alpha/2,\alpha/2,\alpha/2,\beta,\beta)\mapsto^*(1,1,1,1,1,1)$ by the induction hypothesis.

Case 4: $\alpha\neq 0,\beta\neq 0$, $\beta$ is even. $(\alpha,\alpha,\alpha,\alpha,\beta,\beta)\mapsto^*(2\alpha,2\alpha,2\alpha,2\alpha,\beta,\beta)\mapsto^*(\alpha,\alpha,\alpha,\alpha,\beta/2,\beta/2)$, and $(\alpha,\alpha,\alpha,\alpha,\beta/2,\beta/2)\mapsto^*(1,1,1,1,1,1)$ by the induction hypothesis.

Case 5: $\alpha\neq 0,\beta\neq 0$, $\alpha,\beta$ are both odd.

Let $\alpha=2\gamma+1,\beta=2\delta+1.$ Then $(\alpha,\alpha,\alpha,\alpha,\beta,\beta) \mapsto^*(2(2\gamma+1),2(2\gamma+1),2(\gamma+\delta+1),2(\gamma+\delta+1),2(\gamma+\delta+1),2(\gamma+\delta+1))$ $\mapsto^*(2\gamma+1,2\gamma+1,\gamma+\delta+1,\gamma+\delta+1,\gamma+\delta+1,\gamma+\delta+1)=(\alpha,\alpha,\frac{\alpha+\beta}{2},\frac{\alpha+\beta}{2},\frac{\alpha+\beta}{2},\frac{\alpha+\beta}{2}).$

If $\alpha=\beta$, then clearly $(\alpha,\alpha,\alpha,\alpha,\beta,\beta) \mapsto^*(1,1,1,1,1,1)$, and if $\alpha\neq\beta$, then we may use the induction hypothesis to conclude that $(\alpha,\alpha,\frac{\alpha+\beta}{2},\frac{\alpha+\beta}{2},\frac{\alpha+\beta}{2},\frac{\alpha+\beta}{2})\mapsto^*(1,1,1,1,1,1).$

Improve this answer
$\endgroup$
11
  • 4
    $\begingroup$ The same argument does not work for real numbers though, so that question remains open. But observe that we may straight away reduce to $(x, x, x, x, y, y)$, and thereafter all entries remain in $\mathbf Z x + \mathbf Z y$, so it is essentially equivalent to ask about the single case $(e_1, e_1, e_1, e_1, e_2, e_2)$ where $e_1$ and $e_2$ are the basis vectors of $\mathbf Z^2$. The argument above breaks down because elements of $\mathbf Z^2$ really have four kinds of parity. $\endgroup$
    – Sean Eberhard
    Commented Aug 6, 2023 at 20:14
  • 3
    $\begingroup$ @BillyJoe Suppose the initial list is $(x_1, \dots, x_n)$ where $x_i > 0$ for all $i$, and suppose some number of moves changes the list to $(N, \dots, N)$. Any move that creates an $N$ has the form $(x, y) \to (x+y, x+y)$ where $x, y> 0$ and $x+y = N$, so it creates precisely two $N$'s. Moreover no move ever destroys an $N$ (because that would create a bigger element). Therefore the initial list $(x_1, \dots, x_n)$ must contain an odd number of $N$'s. In particular for $(2, \dots, 2, 1)$ the only possibility is $N=1$, but that's impossible because it's less than $2$. $\endgroup$
    – Sean Eberhard
    Commented Aug 6, 2023 at 22:03
  • 4
    $\begingroup$ This argument in this answer can be generalized to any even $n$. One way to see this, is to consider lemma: if we have allowed operations $(x,y) \to (x+y, x+y)$ and $x \to 2x$, then any sequence $(x_1, \ldots x_n)$ (for any $n$) we can transform into constant sequence. Proof: induction, similar to the answer. The even $n$ case, but with only operation $(x,y) \to (x+y, x+y)$ then follows: Apply the operation to all neighboring pairs, to get $(y_1, y_1, y_2, y_2, \ldots y_{n/2}, y_{n/2})$ where $y_k = x_{2k} + x_{2k+1}$, and then apply lemma to $(y_1, \ldots y_{n/2})$. $\endgroup$
    – Jarosław Błasiok
    Commented Aug 7, 2023 at 3:52
  • 2
    $\begingroup$ With this proof here, if we have $k$ numbers which add up to $L$, we can we can finish the game in $\mathcal{O}(k L^3)$ steps: in $k$ steps we can either decrease the sum of all numbers, or decrease the energy $\sum x_i^2$ while keeping the sum intact. $\endgroup$
    – Jarosław Błasiok
    Commented Aug 8, 2023 at 23:58
  • 2
    $\begingroup$ I think optimizing the minimum steps to make the list equal largely rely on this case. Because you only need $O(nlog(n))$ step to standardize the list to the case where only 2 distinct elements. And in the next step (transfer real case down to integers) you will not want the output integer being too big. I guess the minimum number of step needed is indeed $O(nlog(n))$ $\endgroup$
    – jackdean
    Commented Aug 9, 2023 at 19:20
15
$\begingroup$

The problem is soluble for real numbers, and indeed for any tuple $(x_1, \dots, x_n)$ with $n$ even and $x_i$ real (or in any abelian group) for all $i$. (For impossibility for odd-length tuples see this comment or this comment.)

For rational values the problem is solved in the answer of Joseph Van Name and the comment of Jarosław Błasiok. We will reduce the real case to the rational case. Note this also implies that the number of operations needed for a fixed tuple length is actually bounded.

Solution for $n=6$:

An arbitrary tuple can obviously be reduced to the form $(x, x, y, y, y, y)$ (in five steps). Let $z = x + y$. Then

$$\begin{align} (x, x, y, y, y, y) &\to (z,z,x,y,y,y) && (\text{add $x$ and $y$})\\ &\to (z, z+x, z+x, y, y, y) && (\text{add $z$ and $x$})\\ &\to (z, 2z, 2z, z+x, y, y) && (\text{add $z+x$ and $y$})\\ &\to (z, 2z, 3z+x, 3z+x, y, y) && (\text{add $2z$ and $z+x$})\\ &\to (z, 2z, 4z, 4z, 4z, 4z) && (\text{add $3z+x$ and $y$ twice}). \end{align}$$ At this point the tuple is equivalent to the integer tuple $(1,2,4,4,4,4)$ and we can proceed as in Joseph Van Name's answer.

Solution for arbitrary even tuple length $n$:

We can make any $2^k$ arbitrary elements equal (with $k2^{k-1}$ moves), so we reduce the list to the form $(x, \dots, x, y, \dots, y)$ by making the first $2^{[\log_2(n)]}$ elements equal and then making the last $2^{[\log_2(n)]}$ elements equal. Hence assume the list has the form $(x,\dots,x,y,\dots,y)$ where $x$ and $y$ appear $X$ and $Y$ times respectively and $X$ and $Y$ are both even.

We may assume $X, Y > 0$, $y$ is nonzero (otherwise apply $(x, 0) \to (x,x)$ repeatedly) and $x/y$ is irrational. Subsequently all entries remain in $\mathbb Z x + \mathbb Z y$. Let $z = x + y$.

Now consider an arbitrary tuple $(x_1, \dots, x_n) \in (\mathbb Z x + \mathbb Z y)^n$ and define counters $a, b, c \ge 0$ as follows:

$$\begin{align} a &= \#\{i: x_i \in \mathbb Z z + x\},\\ b &= \#\{i: x_i \in \mathbb Z z + y\},\\ c &= \#\{i: x_i \in \mathbb Z z\}. \end{align}$$

Observe that with the operation $(x_i,x_j) \to (x_i+x_j,x_i+x_j)$ we can do any of the following:

  1. if $a, b> 0$, decrease $a$ and $b$ by $1$ and increase $c$ by $2$,
  2. if $a, c> 0$, decrease $c$ by $1$ and increase $a$ by $1$,
  3. if $b, c> 0$, decrease $c$ by $1$ and increase $b$ by $1$.

By doing 2+1 or 3+1 we get the following additional operations:

  1. if $a,b,c > 0$, decrease $b$ by $1$ and increase $c$ by $1$,
  2. if $a,b,c > 0$, decrease $a$ by $1$ and increase $c$ by $1$.

Now, starting from the tuple $(x,\dots, x,y,\dots,y)$, we have initially $(a,b,c) = (X,Y,0)$. After operation 1 we have $(a,b,c) = (X-1,Y-1,2)$. Doing operation 4 and 5 many times , we reach $(a,b,c) = (1,1,n-2)$. Now operation 1 finishes the job.

Improve this answer
$\endgroup$
9
  • 5
    $\begingroup$ I took the liberty of cleaning up some formatting and correcting several small inaccuracies. I did this to promote this answer as a correct solution of the real-entry case, as it seems to be overlooked (as of writing, I am the only up-voter). $\endgroup$
    – Sean Eberhard
    Commented Aug 9, 2023 at 16:59
  • 1
    $\begingroup$ Thank, but i think i prefer the part where nonzero even numbers of $x$ and $y$ rather than exactly two $x$ because originally I did not solved it by induction $\endgroup$
    – jackdean
    Commented Aug 9, 2023 at 17:33
  • 1
    $\begingroup$ If the original $a, b \geq \frac{2n}{5}$, then you can also guarantee that the coefficients of $z$ are either $1$ or $2$, by splitting the tuple into decuplets $4x, 6y$ and doublets $1x, 1y$. The decuplets can be handled as follows: $4x, 6y \rightarrow 2x, 4y, 4z \rightarrow 4(x + z), 4y, 2z \rightarrow 8(2z), 2z$. This allows us to largely skip the possibly long process in Joseph Van Name's post. $\endgroup$
    – user44191
    Commented Aug 10, 2023 at 7:24
  • 2
    $\begingroup$ I’m not sure what Joseph Van Name’s process will give, but a simple way of reducing $(1,2,4,4,4,4)$ is $(1,2,4,4,4,4)\mapsto(5,5,6,6,4,4)\mapsto(5,5,10,10,10,10)\mapsto(10,10,10,10,10,10)$. $\endgroup$
    – Emil Jeřábek
    Commented Aug 10, 2023 at 9:23
  • 1
    $\begingroup$ Also, 1 followed by 2 will give 4 assuming only $a,b>0$ ($c>0$ is not needed), and likewise for 5. $\endgroup$
    – Emil Jeřábek
    Commented Aug 10, 2023 at 9:29
12
$\begingroup$

This is purely an addendum to jackdean and Joseph Van Name's posts to write out the combined process for $n = 6$ explicitly. Each addition replaces the two elements "in-place" with their sum.

  1. Add 1 and 2. $(a + b, a + b, c, d, e, f)$
  2. Add 3 and 4. $(a + b, a + b, c + d, c + d, e, f)$
  3. Add 5 and 6. $(a + b, a + b, c + d, c + d, e + f, e + f)$
  4. Add 3 and 5. $(a + b, a + b, c + d + e + f, c + d, c + d + e + f, e + f)$
  5. Add 4 and 6. $(a + b, a + b, c + d + e + f, c + d + e + f, c + d + e + f, c + d + e + f)$.

Relabel $x = a + b, y = c + d + e + f$, so we now have $(x, x, y, y, y, y)$.

  1. Add 1 and 3. $(x + y, x, x + y, y, y, y)$
  2. Add 1 and 2. $(2x + y, 2x + y, x + y, y, y, y)$
  3. Add 1 and 4. $(2x + 2y, 2x + y, x + y, 2x + 2y, y, y)$
  4. Add 1 and 2. $(4x + 3y, 4x + 3y, x + y, 2x + 2y, y, y)$
  5. Add 1 and 5. $(4x + 4y, 4x + 3y, x + y, 2x + 2y, 4x + 4y, y)$
  6. Add 2 and 6. $(4x + 4y, 4x + 4y, x + y, 2x + 2y, 4x + 4y, 4x + 4y)$

Relabel $z = x + y = a + b + c + d + e + f$, so our tuple is $(4z, 4z, z, 2z, 4z, 4z)$

  1. Add 1 and 3. $(5z, 4z, 5z, 2z, 4z, 4z)$
  2. Add 1 and 3. $(10z, 4z, 10z, 2z, 4z, 4z)$
  3. Add 2 and 4. $(10z, 6z, 10z, 6z, 4z, 4z)$
  4. Add 2 and 5. $(10z, 10z, 10z, 6z, 10z, 4z)$
  5. Add 4 and 6. $(10z, 10z, 10z, 10z, 10z, 10z)$

(hat tip to Emil Jeřábek for finding a 2-step shortcut in the final part)

Improve this answer
$\endgroup$
4
$\begingroup$

For the purpose of determining how many steps are necessary for arbitrary $n$:

Assume $n \geq 6$ is even and not a power of $2$ (as we already have an easy answer for when it is). Let $k = \lfloor \log_2(n) \rfloor$, and $m = \lfloor \log_2(\frac{2n}{3})\rfloor$. Then it's not hard to see that $2^m + 2^k \geq n$, and that $\frac{n}{3} \leq 2^m \leq \frac{2n}{3}$.

We start the process by equalizing the first $2^k$ elements of our tuple. Once that is done, we equalize the last $2^m$ elements of our tuple. As $2^k + 2^m \geq n$, all of the elements of our newly equalized tuple take on one of two values, with $a$ copies of one value $x$ and $b$ elements of the other value $y$. WLOG let $a \geq b$; note that by the above restrictions, both $a$ and $b$ are even, and that $a \leq 2b$.

We can therefore split our $n$-tuple into $\frac{a - b}{2}$ sextuplets of the form $x, x, x, x, y, y$, and $2b - a$ doublets of the form $x, y$. Let $z = x + y$. We can turn the sextuplet into six copies of $8z$ as follows:

$(x, x, x, x, y, y) \rightarrow (x+y, x, x, x, x+y, y) \rightarrow (x+2y, x, x, x, x+y, x+2y)$

$\rightarrow (2x+2y, 2x+2y, x, x, x+y, x+2y) \rightarrow (3x+4y, 2x+2y, x, x, x+y, 3x+4y)$

$\rightarrow(4x+4y, 2x+2y, 4x+4y, x, x+y, 3x+4y)$

$\rightarrow (4x+4y, 2x+2y, 4x+4y, 4x+4y, x+y, 4x+4y) = (4z, 2z, 4z, 4z, z, 4z)$

$\rightarrow (4z, 3z, 4z, 4z, 3z, 4z) \rightarrow (4z, 6z, 4z, 4z, 6z, 4z) \rightarrow (4z, 12z, 4z, 4z, 12z, 4z)$

$\rightarrow (16z, 16z, 4z, 4z, 12z, 4z) \rightarrow (16z, 16z, 16z, 4z, 16z, 4z) \rightarrow (16z, 16z, 16z, 16z, 16z, 16z)$

and we can turn the doublet into two copies of $16z$ by adding it together 5 times.

In total, this takes: $k*2^{k - 1}$ steps to equalize the first $2^k$ elements, $m*2^{m - 1}$ steps to equalize the last $2^m$ elements, $13*\frac{a - b}{2}$ steps to bring all the sextuplets to $8z$, $\frac{5}{2}*(2b - a)$ steps to bring the doublets to $16z$

The last two parts can be easily combined to give $\frac{8a - 3b}{2} = \frac{11}{2}a - \frac{3}{2}n$ steps. Note that $a \leq \frac{2n}{3}$, so the final steps take at most $\frac{13n}{6}$ steps.

Equalizing $2^k$ elements in the obvious way takes $k2^{k - 1}$ steps (and I suspect that can't be improved), so by using $m \leq k \leq \log_2(n)$, we obtain a bound of $n \log_2{n} + \frac{13n}{6}$ steps. Note that this bound isn't tight - we can improve the coefficient for $n \log_2{n}$ to $\frac{3}{4}$ by considering the cases of $m = k$ and $m = k - 1$ separately - but this already puts us to within about double the bound on the "easy" scenario where $n$ is a power of 2.

An alternative, inductive approach for $n \geq 10$:

We clearly have an answer for $n = 0, 2, 4, 6, 8$. If $n$ is divisible by $4$, then we can divide the $n$-tuple into two even-length parts, equalize each (by induction), then mix them together in the obvious way.

If $n$ is not divisible by $4$, then divide the $n$-tuple into two even-length parts whose lengths differ by $2$. Equalize both. Then take 3 elements from the smaller part and 5 elements from the larger part, giving an octuplet of the form $(x, x, x, y, y, y, y, y)$. Follow the following steps for the octuplet:

\begin{align} (x, x, x, y, y, y, y, y) &\rightarrow (x, x, x+y, x+y, y, y, y, y) \\ &\rightarrow (x, 2x+y, 2x+y, x+y, y, y, y, y)\\ &\rightarrow (2x+y, 2x+y, 2x+y, 2x+y, y, y, y, y)\\ &\rightarrow (2x+2y, 2x+2y, 2x+2y, 2x+2y, 2x+2y, 2x+2y, 2x+2y, 2x+2y) \end{align} where each line except the last takes one step, and the last takes 4. Then there are $\frac{n - 8}{2}$ copies of both $x$ and $y$ outside of the octuplet , so we can pair them up and add them together. Finally, we can add together copies of $x$ and $y$, so all elements end up equal to $2x + 2y$.

If $f(n)$ denotes the number of steps this recursive process takes to equalize all elements, then we get that $f(n) = \begin{cases} 2 f(\frac{n}{2}) + \frac{n}{2} & 4|n \\ f(\frac{n - 2}{2}) + f(\frac{n + 2}{2}) + n - 1 & 4\not| n \end{cases}$

Our base cases are currently $f(0) = 0, f(2) = 1, f(4) = 3, f(6) = 16, f(8) = 12$. I believe this recurrence relation gives an asymptotic answer of $f(n) \sim \frac{3}{4} n \log_2(n)$, as the "worse" split (when $4 \not | n$) always includes one part with length divisible by 4. This is not an optimal solution - for $n = 10$, there's a solution that works in 24 steps based on splitting into a doublet and an octuplet, while the above takes 28 steps, and for $n = 14$ it's faster to just equalize all 8 rather than just the last 6.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ actually you only need $4 * (2b-a)/2$ steps to bring all the $z$ to $16z$ $\endgroup$
    – jackdean
    Commented Aug 10, 2023 at 5:59
  • 1
    $\begingroup$ It's feel very surprising to me that the most steps-consuming part is making $2^t$ elements equal which take about $O(t2^t)$ steps. $\endgroup$
    – jackdean
    Commented Aug 10, 2023 at 6:04
  • 1
    $\begingroup$ Besides bounding the number of steps, this is a nice argument to reduce the arbitrary even $n$ case to $n=6$. $\endgroup$
    – Sean Eberhard
    Commented Aug 10, 2023 at 8:26
  • 1
    $\begingroup$ @SeanEberhard There's a somewhat more elegant induction argument which can reduce the arbitrary even case to the $n = 6$ case; its bound can be much improved by using the $n = 10$ decuplet $(x, x, x, x, y, y, y, y, y, y)$. If I've calculated correctly, the decuplet argument leads to a bound surprisingly similar to the bounds I found above. $\endgroup$
    – user44191
    Commented Aug 10, 2023 at 9:14
  • 1
    $\begingroup$ @EmilJeřábek jackdean's answer makes all of the elements into integer multiples of $z$, but doesn't make all of them the same multiple - I've included those extra steps here. jackdean's part corresponds to the 2nd section in the community wiki post, while Joseph Van Name's post corresponds to the 3rd section. I've also found a slight modification to jackdean's solution that provides a shortcut later, knocking it down to $\frac{11}{6} n$. $\endgroup$
    – user44191
    Commented Aug 10, 2023 at 9:58

You must log in to answer this question.

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