Mathematical proof for long-term behavior of a sequence of integer vectors

Question

There are some children sitting around a round table. Each child is given an even amount of $1$-cent coins ($0$ is even) by their teacher, all the children at once. A child will give half his money to the child by his right, then the receiving child gives half of his to the one by his right and it goes on like that. If a child whose turn it is to give has an odd amount of coins, then the teacher gives him an extra coin.

Q : Prove that after several giving and taking, all of these children will have the same amount of $1$-cent coins except one of them who will have twice that amount.

Here is a small python code I wrote to demonstrate the question

def help(c):
    n=0
    m=len(c)
    while (n<len(c)-1):
        for i in range(0,m):
            if(c[i]%2==0):
                c[i]=c[i]/2
            else:
                c[i]=(c[i]+1)/2
            c[(i+1)%m]=c[(i+1)%m]+c[i]        
        a=c.count(c[0])
        b=c.count(c[1])
        n=max(a,b)
    return c

Answer 1

Suppose there are $n$ children, and make $n+1$ heaps of coins by making a heap for the coins that are in-transit during a transaction. Place this new heap between those two children in our circle. Then the receiving children takes his two heaps, evens them out, and moves to the left, leaving what was previously his heap as the new transfer heap for the next child to the right, and so on.

So we have $n+1$ heaps $c_0 \ldots c_n$, and the procedure we're doing is equivalent to replacing $c_k, c_{k+1}$ with two equal heaps of $\frac {c_k + c_{k+1}}2$ coins, rounded up if necessary. Then increase $k \pmod {n+1}$ and repeat.

Now, look at $\max_{0\le k\le n}\{c_k\}$. This is a decreasing positive sequence, because even with rounding up, we always have $\frac {c_k + c_{k+1}}2 \le \max \{c_k, c_{k+1}\}$. This shows that the total number of coins, which is always less than $(n+1)\max_{0\le k\le n}\{c_k\}$, stays bounded over time. And thus eventually the teacher is going to stop giving out new coins.

Then from that point on, since we're only evening out the different heaps, we can check that the quantity $\sum_{0\le i<j \le n} |c_i-c_j|$ is decreasing, and is strictly decreasing as long as anything non trivial happens : when replacing $c_k$ and $c_{k+1}$ with $\frac {c_k + c_{k+1}}2$, we have $\sum_{0\le i<j \le n} |c'_i-c'_j| - \sum_{0\le i<j \le n} |c_i-c_j| = (\sum_{i \notin \{k,k+1\}} |c_i - c'_k| + |c_i - c'_{k+1}| - |c_i - ck| - |c_i - c_{k+1}|) - |c_k - c_{k+1}| \le - |c_k - c_{k+1}|$ using the triangular inequality.

Since this quantity is positive and decreasing, it is eventually constant, which means that eventually, $c_k = c_{k+1}$ forall $k$ : then every heap has the same size, which is what we needed to show.

Answer 2

A beginning:

Assume that amounts of money are real numbers, denote by $x_k$ $\ (1\leq k\leq n)$ the amount of money the child which is $k$th in line possesses at a given moment, and by $x'_k$ $\ (1\leq k\leq n)$ the amount of money the child which is then $k$th in line possesses after one transaction. Then $$x'_1={1\over2}x_1+x_2, \quad x_2'=x_3,\quad\ldots,\quad x'_{n-1}=x_n, \quad x_n'={1\over2} x_1\ ,$$ or ${\bf x}'=A{\bf x}$, where the matrix $A$ is given by $$A=\left[\matrix{{1\over2}&1&0&\ldots&0\cr 0&0&1&\ldots&0\cr \vdots\cr 0&0&\ldots&0&1\cr {1\over2}&0&\ldots&0&0\cr}\right]\ .$$ The matrix $A$ has the eigenvalue $1$ with corresponding eigenvector $(2,1,1,\ldots,1)$.

Therefore we should prove that all other eigenvalues have absolute value $<1$, and that the effect of the extra coins handed out by the teacher will dry out.

Answer 3

A (too?) non-rigorous/intuitive approach:

Instead of dealing with all the children at once, consider there are two children 1 and 2, while all the other children are treated as 'external world', denoted by $E$. In each round $i$, $E$ gives 1 some coins, say $\alpha_i$. 1 gives half of its coins to 2, and two gives half of his to $E$ (after taking care of odd-numbered scenarios with the teacher's help). In order to model all possible behavior of the $n-2$ children, no restriction is imposed on $\alpha_i$s except they be natural numbers.

Suppose at any instant of time, say beginning of round 0, 1 and 2 had $(x_1,x_2)$ coins and it is 1's turn to share half his coins. Their coins change as:

Round 0: $$(x_1,x_2) \to (\frac{x_1}{2},x_2+\frac{x_1}{2})\to (\frac{x_1}{2},\frac{x_2}{2}+\frac{x_1}{4})$$

At the beginning of round 1, $x_1$ gets $\alpha_1$ coins from his neighbor in $E$. Effect of round 1 on children 1 and 2 is

Round 1:$$(\frac{x_1}{2}+\alpha_1,\frac{x_2}{2}+\frac{x_1}{4})\to (\frac{x_1}{4}+\frac{\alpha_1}{2},\frac{x_1+x_2}{2} +\frac{\alpha_1}{2}) \to(\frac{x_1}{4}+\frac{\alpha_1}{2},\frac{x_1+x_2}{4} +\frac{\alpha_1}{4})$$

Consider one more round, with 1 getting $\alpha_2$ coins this time.

Round2: $$(\frac{x_1}{4}+\frac{\alpha_1}{2}+\alpha_2,\frac{x_1+x_2+\alpha_1}{4}) \to (\frac{x_1}{8}+\frac{\alpha_1}{4}+\frac{\alpha_2}{2},\frac{3x_1}{8} +\frac{x_2}{4}+\frac{\alpha_1+\alpha_2}{2}) \to (\frac{x_1}{8}+\frac{\alpha_1}{4}+\frac{\alpha_2}{2},\frac{3x_1}{16} +\frac{x_2}{8}+\frac{\alpha_1+\alpha_2}{4})$$

All the coefficients for a particular term obey the series $$f_i = \frac{1}{2}(f_{i-1}+\frac{1}{2^i}),f_0=0$$ It is easy to see that $f_{i-1}<f_i$ and $f_i\to 0$ as $ i\to \infty$.

So, the amount of coins with 1 and 2 at the end round $i$ can be written as $$x_1(i) = \frac{x_1}{2^i} +\sum_{j} \frac{\alpha_j}{2^{i-j}}$$ $$x_2(i) = \frac{x_2}{2^i} + f_ix_1 + \sum_{j}f_{i-j}\alpha_j$$

It is easy to see that as $i$ increases, $x_1(i)-x_2(i)$ decreases. So, after some iterations, they will be close enough for the ceiling function to map to the same integer.

If this is granted, the rest of the result is easy to prove. By considering all pairings of adjacent children, it is easily shown that all of them will have the same number of coins once they have shared half of their coins. It follows that the child about to share his coins must have double the coins everybody has.

Note: This answer is just to present an intuitive understanding of what is happening after each round. I have neglected the ceiling function while analyzing the rounds, although ceilings and floors usually hasten convergence, by ironing out small differences. What remains to be proved is that any two adjacent children will eventually have the same number of coins, even when odd numbers are taken care of by ceiling/teacher. Working on that!!

Answer 4

A partial attempt:

Assume the teacher gives out $n$ coins, and let $n=2^px$, where $p$ is the biggest such number. We can safely ignore $x$ and assume $n=2^p$. So the first child will give out $2^{p-1}$ and keep the same amount for himself.

Assume for now that there are a lot of kids and we only look at the first round of the giving and taking. Child 2 will have $2^{p-1} + 2^{p}=\frac{3}{2}2^{p}=(1 +\frac{1}{2})2^{p}$, and then give out half to next child, remaining with $(\frac{1}{2} + \frac{1}{4})2^{p}$. Child 3 will have then $2^{p}(1 + \frac{1}{2} + \frac{1}{4})$. So child k will have right after receiving the money from the left, $$2^{p}(\sum_{i=0}^{k-1}2^{-i})=2^{p}(\frac{\sum_{i=0}^{k-1}2^{i}}{2^{k-1}})=$$

$$2^{p}(\frac{2^k -1}{2^{k-1}})=2^{p-k-1}(2^k-1):=g_k $$ So $g_k$ is divisible by 2 as long as $p-k-1>0 \leftrightarrow p>k+1$. This is true in the beginning, so the first coin giving will happen at $k=p-1$. So the p'th child will have: $$g_p=(2^{p-(p-1)-1}(2^{(p-1)}-1)+1)\frac{1}{2}+2^p= 2^{p-2}+2^p=(1+2^2)2^{p-2}$$

In my earlier calculations the money passed along was $2^p$ instead of $2^{p-2} $, which ended the problem right there, so I don't have the rest. However it seems you can just go along in the same way, noticing how there's always this sum building up as you go along. I'm posting anyway, maybe someone will be in the mood to continue it. Remember this only works for the first round of givings.