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

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

-
And your question is...? Are you asking for a proof of the first block quote, or to confirm the logic of your code? If the latter, perhaps you can explain what your code is "saying"... – amWhy Nov 2 '12 at 22:08
@amWhy This is a math site, so I'm obviously looking for a mathematical proof of the block quote. The code is just to show that the hypothesis is true. – user31280 Nov 2 '12 at 22:13
I didn't intend to come across as off-putting or sarcastic. My apologies if my comment/question struck you as such. – amWhy Nov 2 '12 at 22:22
It may not matter, but are they given the same amount of cent? – Jean-Sébastien Nov 4 '12 at 1:32
@Jean-Sébastien I don't think so. In fact I think the statement holds even if we start with arbitrary numbers of cents for each child, i.e. not necessarily even. – EuYu Nov 4 '12 at 1:43

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.

-
Thank you, this is wonderful. – EuYu Nov 8 '12 at 16:42

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.

-
but even if this sequence continues, the division by two becomes invalid until one "ceils" it $x_1' = \left \lceil \cfrac 12 x_1 \right \rceil+ x_2$ since we can guarantee that $x_1$ is even. – user31280 Nov 7 '12 at 0:01
@F'OlaYinka That's why a proof that the sequence stabilizes is needed. This holds only after the teacher stops giving out coins. – EuYu Nov 7 '12 at 0:19

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!!

-
Thank you for the answer. While I certainly appreciate the alternative approach, this shows ultimately the same thing as Christian's answer: Assuming the sequence stabilizes, it converges to the desired outcome. I am much more interested in a proof that the sequence does eventually stabilize, i.e. the teacher eventually stops giving the children coins. – EuYu Nov 7 '12 at 19:30
I have tried to prove that the sequence stabilizes, i.e. after a finite number of steps $x_1(i)$ and $x_2(i)$ will be equal for any two adjacent children. More precisely, I have (roughly) outlined a procedure that may show that any starting configuration converges to a situation where the teacher does not need to give any more coins. I believe this is exactly what you are looking for. – dexter04 Nov 7 '12 at 20:56
I have another approach, but I am not sure how to formalize it. Try to model the process as a Markov Chain, and show that the answer is an absorbing state. You can give it a try. – dexter04 Nov 7 '12 at 21:00
Sorry I should've been more clear. If you read the bounty statement that I wrote, I made it clear that Christian has already shown $x_1 = x_2$ in the long run given a situation where the teacher does not give out any more coins. I am looking for a proof that the teacher does indeed stop giving out coins at some point. – EuYu Nov 7 '12 at 21:00
For the Markov state approach, that's pretty much what Christian did in his answer. – EuYu Nov 7 '12 at 21:01

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.

-