Question for averaging the overall quantities by averaging a part

Question

There is a question: If integers $a$ and $b$ satisfy the following properties: for any $a$ real numbers, we can do an operation to average $b$ of them to the same quantities, and we can do a finite number of operations so that all does $a$ real numbers are the same (does not depend on the amounts), we call $a$ can be averaged by $b$. We omit the condition that $b\le a$ for convenience.

(Intuitively understanding: for any $a$ cups of water with arbitrary amounts, we can do an operation to average $b$ of them to the same quantities, and we can do a finite number of operations so that the amount of water in those $a$ cups are the same.)

A necessary condition is that if $a$ can be averaged by $b$, then for any prime $p$ that $p|a$, we have $p|b$. This is easy to prove: suppose $p|a$ but not $p|b$. So $p$ will never appear in the denominator if the starting configuration is one $1$ and others are $0$, and it will never be $1/a$ for all the real numbers.

Now we seek proof that this is also a sufficient condition, but this is false. For example, $8$ can't be averaged by $6$, because if the starting configuration is two $3$'s and six $-1$'s, all the configurations it can achieve will be $x,y$ and six $z$'s such that either $x=y\ne 0$ or $x$ and $y$ has a distinct power exponential of $3$.

(Clarify: It means if you factorize $x$ and $y$ into primes (say $x=\pm2^{p_2}3^{p_3}\dots$ and $y=\pm2^{q_2}3^{q_3}\dots$) Then either $x=y\ne 0$ or $p_3\ne q_3$. This can be proven by using induction. After proving this we know that we will never reach $x=-y$ case and thus we will never have $8$ averaged by $6$)

So how to find all pairs of $(a,b)$ such that $a$ can be averaged by $b$?

The question part ends here, the followings are partial progress on this problem. To make it not seems to be too long (it actually is!), I am going to hide them.

Here list some of the properties:

1. If $a$ can be averaged by $b$, then $ka$ can be averaged by $kb$.
2. If $a$ can be averaged by $b$ and prime $p|b$, then $pa$ can be averaged by $b$.
3. If $a$ can be averaged by $b$, $b$ can be averaged by $c$, then $a$ can be averaged by $c$.
4. For $1\le x\le y$, $y^2$ can be averaged by $xy$. (it is generalized by the lemma in the answers below: if $ax$ and $by$ can be averaged by $xy$, then $ab$ can be averaged by $xy$.)

Some sporadic positive and negative results:

positive results (not genarated by the properties above):

$(16,10)$, $(32,14)$, $(27,15)$, $(64,22/44)$, $(64,26)$ etc. holds. All $8k$ can be averaged by $6k$ for $k\ge 2$. Notice that $(54,48)$ can be done (refer to the comment).

negative results:

see the answer below. Currently (tested for all $b\le 50$) there is no negative results that does not violate the necessary condition and does not satisfy the condition of the answer below, except $(64,50)$ (this one I merely think they can't do, but I don't have any proof.)

Also a result:

using the properties above, for any $b$, there is finite number of $a$ such that $(a,b)$ satisfy the necessary condition but $a$ can't be averaged by $b$

A (maybe) simpler/intermediate question: if we only consider the starting configuration with one $1$ and others are $0$, what are the possible $(a,b)$'s? Also, if $(a,b)$ can do with the starting configuration with one $1$ and others are $0$, will it be done for arbitrary initial amounts?

a sufficient condition: If $(a,b)$ satisfy $\lfloor a/b\rfloor = k$, and $k(k+1)<b$, then, if one $1$ and others $0$ can do, arbitrary amount can do. Actually, we only need $k\times (b\mod k)+(a\mod k)\le b$ is okay.

Answer 1

Here are two partial negative claims.

Remark: Claim 1 is inspired by the relation $54\not\geq 48$ suggested in the comments. However, it does not prove that relation, although it proves, say, $486\not\geq 480$. (It also does not prove $2^n\not\geq 2^n-2$, which is shown in Claim 2.)

Claim 1. Assume that $b$ is divisible by some prime power $p^{2k-1}$ such that $p^k>a-b$. Then $a\not\geq b$.

Proof. Start with $b$ zeroes and $c=a-b$ ones. Notice that a simultaneous shift of all quantities by the same number does not affect anything. So we modify the process by shifting, after each operation, the quantities so that the averaged quantities turn into zeroes. We will also multiply the numbers, after each operation, by the same number so that they become integers coprime in total.

In other words, the modified process is as follows. We choose $b$ cups with total amount of $S$. We replace all those amounts by zeroes, and subtract $S/b$ from all other $c$ quantities. After that we multiply everything by the common denominator (and, maybe, reduce the common factor --- but it will be always coprime with $p$).

We claim that, after each operation, there will always be exactly $c$ nonzero numbers not divisible by $p$, and all those $c$ numbers are congruent $\mod p^k$. This immediately implies the result. In the beginning this holds.

Let $x$ be the common resuidue of nonzero numbers $\mod p^k$, and suppose we took $y$ of them into the averaged group. Then $p\nmid x$ and $p^k\nmid y$, so $S\equiv xy\not\equiv 0\pmod {p^k}$, and hence the irreducible form of $S/b$ has denominator divisible by $p^k$. Thus, after the operation, all $c$ potentially nonzero numbers will be indeed nonzero and their denominators will be divisible by $p^k$, although their differences will be integers. Then, after the multiplication by the common denominator (and reduction by the common factor coprime with $p$) they will have a desired form. This completes the proof.

Claim 2. $2^n\not\geq 2^n-2$ for $n\geq 3$.

Proof. We use the first step of the above modification, but omit reducing the factor. We will show that a situation with all zeroes except for two equal numbers cannot be averaged. Indirectly, the position before all-zeroes should be $(1,-1,0,\dots,0)$ (multiply by a constant if necessary). We may assume that, in the process, we did not get a situation with two equal nonzero numbers.

The step of the direct process looks like $$ (x,y,0,0,\dots,0)\mapsto (y-x/b,-x/b,0,\dots,0), $$ as if we took both $x$ and $y$ to be averaged, we would get two equal nonzero numbers. Revert the process; the step in the reverse process looks like $$ (x,y,0,\dots,0)\mapsto (-bx,y-x,0,\dots,0). $$ So, say, the first step in the reverse process is, up to the sign change, $$ (-1,1,0,\dots,0)\mapsto (b,2,0,\dots,0). $$ We claim that we always get two integers exactly one of which is divisible by $b$, so they will always be distinct. Indeed, if $b$ divides exactly one of $x$ and $y$, then $b\mid -bx$ but $b\nmid y-x$. The proof is complete.

Answer 2

A brief comment on notation: "can be averaged by" is a reflexive partial order. I shall use the notation $a \succeq b$ to indicate that $a$ can be averaged by $b$, and save $\geq$ for the usual total order on the integers.

---

Another partial answer, this time with a positive proposition which I'm calling the three-pass lemma:

If $a = mn$, $\exists s < n: sm \succeq b$, and $\exists t < m: tn \succeq b$ then $a \succeq b$.

Proof proceeds by arranging the $a$ values in $m$ rows of $n$ values each and then performing three passes:

1. Average the first $t$ rows, then the next $t$ rows, etc. If $tn \not\mid a$, finish by averaging the last $t$ rows. At the end of this pass, every row contains a single value repeated $n$ times.
2. Average the first $s$ columns, then the next $s$ columns, etc. If $sm \not\mid a$, finish by averaging the last $s$ columns. At the end of this pass, there only two distinct values remain: the first $n-s$ columns have one value, and the last $s$ columns have another. (If $sm \mid a$ then only one distinct value remains and we can stop).
3. Repeat the first pass. Each averaging operation of this pass takes the averaged positions to the target value.

Note that this proposition generalises your property 2 (take $m=p$, $n=a$, $s = \tfrac bp$, $t=1$) as well as your property 4 (take $m=n=y$, $s=t=x$).

Corollary:

Given $a$, we can find $b < a$ such that $b \preceq a$ iff $a$ is not squarefree.

Clearly if $a$ is squarefree then from $p \mid a \implies p \mid b$ the smallest predecessor of $a$ is itself. On the other hand, if $a = p^2 a'$ then we can take $m = p$, $n = pa'$, $s = a'$, $t = 1$, $b = pa'$ in the three-pass lemma. (This is also an instance of your property 2).

---

A similar notion of pass can be used for many $a, b$ to reduce to a single case that needs to be tested. Consider the following conditions:

• $c \succeq b$
• $d \succeq b$
• $a = cq + r$ with $0 \le r < c$
• $a = ds + t$ with $0 \le t < d$
• $\tfrac{t-r}{q} \le c \bmod s \le \tfrac tq$

Then we can reduce the question of whether $a \stackrel?\succeq b$ to a single test vector as follows:

1. Given an initial vector $\{u_1, \ldots, u_a\}$ we apply a pass of averages of size $c$ to reduce to $q+1$ clusters $\{v_1^c, v_2^c, \ldots, v_q^c, v_{q+1}^r\}$.
2. We now apply a pass of $s$ averages of size $d$ where the input to each average is $\{v_1^{\left\lfloor c/s \right\rfloor}, v_2^{\left\lfloor c/s \right\rfloor}, \ldots, v_q^{\left\lfloor c/s \right\rfloor}, v_{q+1}^{d - q\left\lfloor c/s \right\rfloor} \}$
3. That second pass creates one value $w_1$ with frequency $ds$. A final average of size $d$ which includes the $t$ values not equal to $w_1$ (and $w_1^{d-t}$) reduces to $\{w_1^{a-d}, w_2^d\}$, which by linearity is equivalent to $\{0^{a-d}, 1^d\}$. So if that latter test vector can be averaged, $a \succeq b$. (And, clearly, if it can't then $a \not\succeq b$).

The validity of step 2 depends on $q\left\lfloor \frac cs \right\rfloor \le d$; since $s\left\lfloor \frac cs \right\rfloor = c - (c \bmod s)$ this is equivalent to $$\begin{eqnarray*} cq - q(c \bmod s) &\le& ds \\ a - r - q(c \bmod s) &\le& a - t \\ t - r &\le& q(c \bmod s) \\ \end{eqnarray*}$$

We also require there to be sufficient $v_{q+1}$; i.e. $$\begin{eqnarray*} s(d - q\left\lfloor \frac cs \right\rfloor) &\le& r \\ ds - cq + q (c \bmod s) &\le& r \\ q (c \bmod s) &\le& t \\ \end{eqnarray*}$$

Combining the two, we see the necessity for the final precondition.

---

I've done a bit of experimentation with solving the test vectors produced by this reduction. If we consider the graph whose vertices are multisets of $a$ rationals and whose edges correspond to averaging $b$ values, solving a test vector is a pathfinding problem. However, the graph is infinite and most vertices have quite large out-degrees. The vertex priority which I've found most effective is to use Ilya Bogdanov's technique for normalising to a multiset of integers, and then prioritise the multisets with smallest maximum absolute value. Updated code and solutions will appear shortly on the gist I posted earlier in comments.

Answer 3

I decide to put some of my efforts and proofs here in order to make the problem statements clearer.

1. Proof of $8k$ can be averaged by $6k$ if $k\ge 2$.

for $k=2$, this can be covered by property 4. Now we assume $k\ge 2$. Average twice we can get $6k$ equals and $2k$ other equals. WLOG there are $6k$ $-1$'s and $2k$ $3$'s (we can shift and multiply all the number to a same number.)

First, we average $k$ $3$'s and $5k$ $-1$'s, we have $k$ $3$'s, $k$ $-1$'s, $6k$ $-1/3$'s. Now we take $a$ $3$'s, $b$ $-1$'s and $c$ $-1/3$'s and try to make it mean zero. That is, $3a-b-c/3=0$. Since we also have $a+b+c=6k$, we have $5a-b=3k$. We let $a=\lceil 3k/5\rceil$, $b=5a-3k$, and $6k-a-b$. We have $a\le k$ and $b\le k$ (check for $k=3,4$ it is correct, and for $k\ge 5$ we have $b\le 5\le k$.) After doing this, we have $6k$ $0$'s, and average the rest $2k$ and $4k$ zeroes we can get all zero.