Evenly distributing $n^2$ ball between $n$ pockets by chosing $2$ of them at a time. We have $n^2$ balls distributed among $n$ pockets (some of them may be empty). We can choose any two pockets of which sum of balls is even and then distribute the balls equally among these two pockets. We can repeat it as many times as we wish. For every natural, even number $n$ such that $2 ≤ n ≤ 10$ decide if by using this method we can always distribute the balls so that at the end every bag contains n balls, no matter how many balls there are in each pocket at the beginning.
I think and I am informed it is true that we can do it for every n number of pockets which is a power of two. I suppose, we split them in two until we are left with $n/2$ pairs of pockets. Then we make a move on each pocket and make our way out merging the subsets of pairs. For $n=4$ we have two pairs which we first want to even out and then make the move on the first elements from the each pair an then on the second elements from each pair. However the number of ball combined in the selected pockets has to be even. That feels to be the case as if $n$ is a power of two, $n^2$ is even so we have an even number of odd numbers of balls. How would a proper proof of that look? How to prove we cannot do it if $n$ is not a power of two?
 A: First, call a distribution of balls "dead" when some pockets have an even number $E$ of balls and the rest have an odd number $O$ of balls.  When we start with such a dead distribution, it's impossible to change the distribution of balls, so we cannot evenly spread the balls among the pockets.
We will be able to generate a special class of dead distributions as follows: Given any $n>1$,

*

*Choose $k$ such that $0 \leq k < n$.  Put $k$ balls into each pocket.  At the end of this step, we have $n^2 - nk = n(n-k)$ balls remaining to distribute.

*Write $n(n-k) = 2^i\cdot m$ where $m$ is odd.  If $2^i < n$, then pick any $2^i$ pockets and put $m$ balls in each, so these pockets will have $m+k$ balls in total; otherwise, do nothing.

With this procedure, we have two claims:

*

*This procedure can test whether a given $n$ has a dead distribution.

When the procedure finishes, some pockets have $k$ balls and others have $m+k$ balls and $(m+k) - k = m$ is odd, so the resulting distribution is dead.
On the other hand, when a dead distribution exists with $E$ and $O$ as in my first paragraph, we can set $k = \min(E,O)$ and take $|E-O|$ balls from each of the $P$ pockets currently holding $\max(E,O)$ balls.  Every pocket now has $k$ balls.  Also, you now hold $$n(n-k) = P\cdot |E-O| = 2^i\cdot m$$ balls in your hand, and since $|E-O|$ is odd, $2^i \leq P < n$, so the procedure also yields a dead distribution.

*

*The existence or non-existence of a dead distribution is the key question we must investigate.

In short, this is because the existence of a dead distribution provides an initial distribution from which you cannot equally distribute the balls, and the non-existence of a dead distribution, combined with the fact any distribution $(b_1, b_2, \ldots, b_n)$ of balls can move at most $\sum b_i^2$ times before you cannot make any more moves, which only happens when the final distribution is equally split among all pockets or is a dead distribution.

Now consider the cases:

*

*$n$ is not a power of two:  If $n$ is odd, choose $k=0$ in the above procedure; otherwise choose $k=1$.  Then $n-k$ is odd and $2^i$ divides $n(n-k)$, so $2^i$ divides $n$.  Since $n$ is not a power of $2$, $2^i < n$ so the above procedure successfully yields a dead distribution.  Therefore, when $n$ is not a power of two, it is not always possible to evenly distribute the balls.

*$n$ is a power of two:  In this case, regardless of the $0 \leq k < n$ chosen, we will always have $n$ dividing $2^i$, so $n \leq 2^i$.  Therefore the above procedure can never complete, and in particular no dead distribution of balls exists.  Therefore, when $n$ is a power of two, it is always possible to evenly distribute the balls.

A: To rule out cases where a fair distribution is impossible it suffices to show there is one initial allocation that can't be distributed.

*

*$n$ is odd
Let all the balls be in the same pocket. Then no "move" is permitted. Thus the allocation is impossible.


*$n = 2^d\cdot m,\ m$ is odd $>1$
Split the $2^{d+1}\cdot m^2$ balls evenly into $2^{d+1}$ pockets. Note that since $m\ge3$ there are enough pockets. Now, we can "move" forever but no move can change the allocation, apart from change which pockets contain the balls.


*$n = 2^d$
Proof by induction:

*

*Base case: Check $n = 2$ by hand.

*Inductive hypothesis: Assume that it holds for some $d$.

*Inductive step: Pick any starting allocation. Then, if there are any pockets with odd number of balls paired them with each other until only pockets with even are left. Now, if you treat any two balls as one, the series of "moves" that solves the inductive case allocates 2 balls in $2^d$ pockets. To finish, you simply match all two ball pockets with all the empty ones.



EDIT:
Case 2 is wrong. My idea is to split it into $2^i m^2$ in such way that you will always be stuck with numbers of the same form. Working on it.
A: Let's do it for n=6 and n=10
For n=6 If you take it as $({7,7,7,7,4,4})$ or ${5,5,5,5,8,8}$ or ${3,3,3,3,12,12}$ or ${1,1,1,1,16,16}$ or ${9,9,9,9,0,0}$. Here the sum is 36 but you can't make it into ${6,6,6,6,6,6}$.
For n=10 If you take it as ${1,1,1,1,1,1,1,1,46,46}$ or ${9,9,9,9,9,9,9,9,14,14}$ or something of the form {o,o,o,o,o,o,o,o,e,e} where o is odd and e is even
So basically doesn't work for n=6 or n=10 or any n of the form 4k+2 for k>0.
It does work for $n=2^k$
It doesn't work for odd numbers also.
Am I making sense?
