Given $n$ rational numbers. Every time you can delete $2$ numbers, and add 2 numbers which are equal to $\frac{a+b}{2}$ (assume the number you delete is $a$ and $b$). How to judge whether it is possible to make these $n$ numbers equal in finite steps? If possible, how to construct it?
$\begingroup$
$\endgroup$
10
-
$\begingroup$ if $n=2^k$, then we can easily construct an answer using divide-and-conquer. Let the average number of the $n$ numbers is $x$. A sufficient condition is if we can divide these $n$ numbers into several groups and for each group, its average number is equal to $x$ and its size is power of 2. $\endgroup$– jh wCommented May 3, 2022 at 14:57
-
3$\begingroup$ You can suppose the rationals are integers, in that case a necessary condition is that the denominator of the average is a power of $2$ $\endgroup$– Saúl RMCommented May 3, 2022 at 19:04
-
$\begingroup$ A simple example to consider is $(0,0,1)$. $\endgroup$– SomosCommented May 6, 2022 at 20:04
-
1$\begingroup$ By a wrong step on can destroy the solvability. For instance $[2,4,6]$ is clearly solvable in one step. But if one averages 2-4 instead one gets $[3,3,6]$ which is not solvable. $\endgroup$– YCorCommented May 7, 2022 at 6:25
-
1$\begingroup$ @BrendanMcKay no, [5,5,5,5,10] is not solvable because solvability is invariant under affine change and [0,0,0,0,1] is not solvable. $\endgroup$– YCorCommented May 7, 2022 at 7:49
|
Show 5 more comments
1 Answer
$\begingroup$
$\endgroup$
5
Too long for a comment.
Without loss of generality, we can assume the numbers are integers. I'll show that one can always achieve an integer multiset with only two values.
For a multiset $Y=\{\!\{ y_1,\ldots,y_n\}\!\}$ define $V(Y) = \sum_{1\le i<j\le n} \,(y_i-y_j)^2$.
Start with an arbitrary multiset of integers $X$. If there are two different values $x_i,x_j$ with the same parity, replace them by their average. This reduces $V(X)$ by $\frac n2(x_1-x_2)^2$ and preserves integrality. Since the reduction is at least $\frac n2$, we can only do this a finite number of times before all odd integers are equal and all even integers are equal.
Whether this helps the problem actually asked, I don't know.
answered May 7, 2022 at 4:13
-
$\begingroup$ The numbers are rational, so you should start with multiplying them by a common denominator. Also, for $V$ we alternatively may take the sum of squares of all numbers. $\endgroup$ Commented May 7, 2022 at 4:47
-
$\begingroup$ @FedorPetrov First part now incorporated. The sum of squares is fine but then one has to argue what the minimum is (trivial, yes, but one extra step). $\endgroup$ Commented May 7, 2022 at 5:48
-
$\begingroup$ I do not understand. The minimum of what? $\endgroup$ Commented May 7, 2022 at 6:05
-
$\begingroup$ @FedorPetrov I take it back. To show that only a finite number of steps is needed, one has to know that the sequence is bounded below, but that is obvious for both functions. I just chose one that reaches zero rather than some multiple of the square of the mean when all the numbers are equal, on a whim if you like. Our functions have an affine relationship anyway so the proof is equivalent. $\endgroup$ Commented May 7, 2022 at 6:30
-
$\begingroup$ Thank you for your answer. The trouble is ''a wrong step on can destroy the solvability'' by @YCor. I have tried to solve this problem in this approach, but it doesn't seem to go any further. $\endgroup$– jh wCommented May 7, 2022 at 6:58