Existence of finite strategy in a "synergy"-hopping game

Question

I have in mind the next Game:

Given $n$ points on $\mathbb{R}$, two random points are picked and moved to the location of their average.

E.g., pick points at location $x_1, x_2$ and they both moved to $\frac{x_1 + x_2}{2}$.

It is not difficult to show, that center of the mass of such system is stationary, for simplicity let it be located at $0$.

I'm interested in possibility of converging all points to the center of mass in finite number of steps (each step is picking a pair of points). Note, that asymptotic convergence is "obvious".

To clarify on the previous point, the assumption of random picking could be dropped, in favor of showing if points in general position could be led to convergence.

For example, for $n = 2^k$, the strategy is to serially collapse pairs of points, then quadruples, etc.

Strategy for $n = 4$:

• pick points at $x_1, x_2$ move to $\frac{x_1 + x_2}{2}$.
• pick points at $x_2, x_4$ move to $\frac{x_3 + x_4}{2}$.
• if not yet every point at $0$, pick one point at $\frac{x_1 + x_2}{2}$ and one at $\frac{x_3 + x_4}{2}$ and move to $0$ (repeat twice)

For $n = 3$, if none of the points is initially at $0$, it is impossible to drive all points to $0$ [i.e. no such strategy exists]. For this note that at any point in time after the first step the split is one point vs. pair of two other points.

At this point, I have a conjecture, that for all $n \neq 2^k$ a finite strategy does not exist. With a random intuition, that none of $\frac{1}{n}$ are finitely representable in binary.

What should be my direction in proving this conjecture?

UPDATE: My thoughts on this $\frac{1}{n}$ approach.

After setting center of mass to $0$ we know $$\frac{1}{n}x_1 + \frac{1}{n} x_2 + \ldots + \frac{1}{n} x_n = 0 $$

Let track the points as a linear combinations of the initial points. E.g. if we choose to pair $x_1$ and $x_2$, then we have points $$\frac{1}{2}x_1 + \frac{1}{2}x_2, \frac{1}{2}x_1 + \frac{1}{2}x_2, 1\cdot x_3, \ldots, 1 \cdot x_n$$

Then after $m$ steps points in general look like $$\sum\limits_{i=1}^n\frac{A_{1,i}}{2^m}\cdot x_i, \sum\limits_{i=1}^n\frac{A_{2,i}}{2^m}\cdot x_i, \ldots, \sum\limits_{i=1}^n\frac{A_{n,i}}{2^m}\cdot x_i, \text{ with } A_{k,i} \in \{0, 1 \ldots, 2^m\}$$

Suppose, there exist some finite strategy. Then [this is a weak point] we somehow could suppose $(x_i)$ is an independent set over $\mathbb{R}$, and all the coefficients should be equal.

But should we then suppose, that $\frac{A_k,i}{2^m} = \frac{1}{n}$?

Answer 1

Three directions you could take come to mind:

• Each averaging step applies a projection operator. You want know whether some product of these operators yields the projection operator which leaves the one-dimensional subspace along the constant vector invariant and annihilates its orthogonal subspace. The non-commutativity of the projection operators seems to get in the way unless $n=2^k$, where you can combine them hierarchically such that they annihilate successively larger orthogonal subspaces so that projections from different parts of the hierarchy commute.
• You could backtrack from the desired final state: You start with all points in one place, and in each step, you're allowed to add opposite displacements to a pair of points that are in the same place. Can you bring the points into an arbitrary position?
• The questions Prove that the elements of X all have the same weight and We have $n$ real numbers around the circle and among any consecutive 3 one is AM of the other two. Then all the numbers are the same or $3\mid n$. come to mind. Even though the problem suggests a solution with linear algebra, perhaps you can reduce to the integer case as I did in my answers to those questions and somehow show that in the integer case not all bits in the binary representations of the numbers can be brought to $0$ simultaneously unless $n=2^k$. In the present problem the numbers don't stay integers, but they only acquire one additional bit after the binary point in each averaging step, so perhaps you can neverthless show that you can never get rid of all bits.

An example of the projection approach, as requested:

For $n=3$, the three averaging operations you can perform correspond to the projection matrices

$$ P_{23}=\pmatrix{1\\&\frac12&\frac12\\&\frac12&\frac12},P_{31}=\pmatrix{\frac12&&\frac12\\&1\\\frac12&&\frac12},P_{12}=\pmatrix{\frac12&\frac12\\\frac12&\frac12\\&&1}\;, $$

which correspond, respectively, to annihilating the directions $(0,1,-1)$, $(-1,0,1)$ and $(1,-1,0)$ and projecting onto the two-dimensional subspaces orthogonal to these directions. Since no pair of these directions is orthogonal, you can never make any progress; each projection destroys what the previous one achieved in terms of annihilation. By contrast, for $n=4$, if you project first with $P_{12}$ and $P_{34}$ onto the subspace spanned by $(1,1,0,0)$ and $(0,0,1,1)$ and then with $P_{13}$ and $P_{24}$, onto the subspace spanned by $(1,0,1,0)$ and $(0,1,0,1)$ (which you can do because each of these pairs commutes), you end up projecting onto their intersection, $(1,1,1,1)$, which is the goal of the game.