数学/論理パズル

Question

誰かがこの問題を解決する方法について何か洞察を持っていますか？私の友人はそれについて私に尋ねました、そしてそれは私を数日間悩ませてきました。私は帰納法でそれにアプローチしようとしました（2人の基本ケースは簡単ですが、帰納法のステップで立ち往生しました）。とにかく、それは楽しい問題だと思い、どうやってアプローチするのか興味がありました。考えられる解決策に関するヒントは素敵です！

円を描くように立って物を交換する人もいます。それらのそれぞれは偶数のチョコレートで始まります-必ずしも同じではありません。毎分、各人はオブジェクトの半分を右側の人に渡します。チョコレートの数が奇数になったら、中央の瓶から別の物を拾います。チョコレートの最初の配布に関係なく、有限のステップ数の後、全員が同じ数のオブジェクトになってしまうことを証明します。

Answer 1

状況は3つの数字で表すことができます $(M,m,r)$、 どこ $2M$ プレイヤーが持っている最大量です、 $m$ は最小量であり、 $r$ のプレイヤー数です $2m$。

プレイヤーが $2a$ ピースとその左隣には $2b$ ピース、次のラウンドでは、このプレーヤーは $ (2a-a)+b= a+b\le 2M$ピース。たとえ$a+b$ 奇妙です、それは $\le 2M-1$ そして、瓶から補充した後、それはまだです $\le 2M$。同様に、新しい金額は$\ge 2m$ 平等で $a=b=m$。私たちは状況が$(M,m,r)$ になる $(M',m',r')$ と $m\le m'\le M'\le M$。また、$m'=m$、その後 $r'\le r$。

しかし、それは起こり得ない $(M',m',r')=(M,m,r)$ そうでなければ $M=m$。確かに、$m<M$、それなら誰かがいるに違いない $2m$彼らの左隣がより多くを持っている間、部分。その後、この人は$>2m$ 次のラウンドのピース、つまりどちらか $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.