Math/Logic Puzzle

Question

Anybody have any insight on how to solve this problem? My friend asked me about it and it's been bothering me for a few days. I tried to approach it by induction (the base case with two people is straightforward, but I got stuck on the inductive step). Anyway, I thought it was a fun problem and was curious how to approach it. Any tips on possible solutions would be lovely!

Some people stand in a circle exchanging objects. Each of them starts with an even number of chocolates - not necessarily the same. Every minute, each of the people passes half their objects to the person to their right. If anyone ends up with an odd number of chocolates, they pick up another object from a jar in the center. Prove that regardless of the initial distribution of chocolates, after a finite number of steps everyone ends up with an equal number of objects.

Answer 1

We can describe a situation by three numbers $(M,m,r)$, where $2M$ is the maximal amount a player has, $m$ is the minimal amount, and $r$ is the number of players with $2m$.

If a player as $2a$ pieces and their left neighbour has $2b$ pieces, in the next round, this player will have $ (2a-a)+b= a+b\le 2M$ pieces. Even if $a+b$ is odd, it is $\le 2M-1$ and so after refill from the jar, it is still $\le 2M$. Likewise, the new amount is $\ge 2m$ with equality if and only if $a=b=m$. We conclude that a situation $(M,m,r)$ turns into $(M',m',r')$ with $m\le m'\le M'\le M$. Moreover, if $m'=m$, then $r'\le r$.

But it cannot happen that $(M',m',r')=(M,m,r)$ unless $M=m$. Indeed, if $m<M$, then there must be some person with $2m$ pieces while their left neighbour has more. Then this person will have $>2m$ pieces in the next round, meaning that either $m'>m$ or at least $r'<r$.

At any rate, if $M>m$, then it takes only finitely mann steps until $M-m$ decreases by at least one. Then still after finitely many steps, we reach $M=m$.

Answer 2

Consider a person with the least number of chocolates at a step. She passes half her chocolates but receives half the chocolates from someone who has at least as many chocolate as she does. So her number of chocolates increases or stays the same if the person to her left also has the same number of chocolates. So the least number of chocolates at a step never goes down.

Now suppose a person has more than the least. If the least number of chocolates is $L$ and the person with more than the least has $L + 2a$ then he gives away $\frac 12L + a$ but gets at least $\frac 12L$ and so has $L + a > L$. So a person who doesn't have the the least at one step can't go don't to that least amount in the next step.

So the least number of chocolates in a step can never decrease to a smaller number in the next step. And if the least number of chocolates in a step is the same as the least number of chocolates in the next step, that can only occur if a person with the least number of chocolates was to the right of a person with the same number of chocolates and that person ends up with the same number of chocolates.

[Note: a person with more that the previous least number can end up in the next step with the new least number that is more than the previous least number, but that person can note end up with the previous least number.]

But if all people don't have the same number of chocolates (if they do we are done) then there is a maximum chain of people with the least number of chocolates $n$ people long. Each step the person on the end of the chain will have more chocolates and the chain shortens by one. (And from the previous paragraph we know no new people will end up with that previous least amount.) So after $n$ steps everyone will have more chocolates and the least possible number will increase.

So if there is an upper limit to the maximum numbers of chocolates possible, then least number at the end of a step will eventually either reach a point where everyone has the same number of chocolate for some number equal to or less than that potential maximum.

So consider the most chocolates a person has at the end of a step. Call it $M$ On the next turn that person gives half the chocolates and recieves half or fewer chocolates. If he recieves as many as he gave away he has an even amount and he ends up with the same number of $M$. If he receives fewer, then even if he adds a chocolate he ends up with at most what he began with.

So.... the most chocolates a person may ever have is a limited $M=$ the most chocolates anyone had at step $1$. The least chocolates a person may have is $L=$ the least chocolates anyone had at step $1$ but that minimum will always increase in a finite number of steps unless all people have the same number. As theres a limit to how high the minimum can be the process must end with equality. Eventually.