수학 / 논리 퍼즐
누구든지이 문제를 해결하는 방법에 대한 통찰력이 있습니까? 내 친구가 그것에 대해 물었고 며칠 동안 나를 괴롭 혔습니다. 나는 귀납법으로 접근하려고했다 (두 사람이있는 기본 케이스는 간단하지만 귀납적 단계에 갇혔다). 어쨌든 재미있는 문제라고 생각하고 어떻게 접근해야할지 궁금했습니다. 가능한 솔루션에 대한 모든 팁은 멋질 것입니다!
어떤 사람들은 원을 그리며 물건을 교환합니다. 그들 각각은 짝수의 초콜릿으로 시작합니다. 반드시 동일하지는 않습니다. 매분, 각 사람들은 자신의 물건의 절반을 오른쪽에있는 사람에게 전달합니다. 누군가가 홀수 개의 초콜릿을 갖게되면 중앙에있는 항아리에서 다른 물건을 집습니다. 초콜렛의 초기 분포에 관계없이 한정된 수의 단계를 거치면 모든 사람이 동일한 수의 개체를 갖게된다는 것을 증명하십시오.
답변
상황을 세 가지 숫자로 설명 할 수 있습니다 $(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$ 아니면 적어도 $r'<r$.
어쨌든 $M>m$, 그러면 유한 한 맨 단계 만 거치면 $M-m$적어도 하나 감소합니다. 그런 다음 여전히 유한 한 많은 단계를 거쳐$M=m$.
한 번에 초콜릿 수가 가장 적은 사람을 생각해보십시오. 그녀는 자신의 초콜릿 절반을 전달하지만 최소한 그녀만큼 많은 초콜릿을 가진 사람으로부터 절반의 초콜릿을받습니다. 따라서 그녀의 왼쪽 사람도 같은 수의 초콜릿을 가지고 있다면 그녀의 초콜릿 수는 증가하거나 동일하게 유지됩니다. 따라서 한 단계에서 최소 초콜릿 수는 줄어들지 않습니다.
이제 사람이 가장 적은 것 이상을 가지고 있다고 가정합니다. 최소 초콜릿 수가$L$ 그리고 가장 적은 것 이상을 가진 사람은 $L + 2a$ 그런 다음 그는 포기 $\frac 12L + a$ 하지만 적어도 $\frac 12L$ 그래서 $L + a > L$. 따라서 최소한 한 단계를 가지고 있지 않은 사람은 다음 단계에서 그 최소한의 양으로 갈 수 없습니다.
따라서 한 단계에서 최소 초콜릿 수는 다음 단계에서 더 적은 수로 줄어들 수 없습니다. 그리고 한 단계의 최소 초콜릿 수가 다음 단계의 최소 초콜릿 수와 같으면 초콜릿 수가 가장 적은 사람이 같은 수의 초콜릿을 가진 사람의 오른쪽에있는 경우에만 발생할 수 있습니다. 그 사람은 같은 수의 초콜릿을 갖게됩니다.
[참고 : 이전 최소 숫자 보다 더 많은 사람은 이전 최소 숫자 보다 많은 새로운 최소 숫자로 다음 단계에서 끝날 수 있지만, 그 사람은 이전에 가장 적은 숫자로 끝날 수 있습니다.]
그러나 모든 사람들이 같은 수의 초콜릿을 가지고 있지 않다면 (만약 우리가 할 수 있다면) 초콜릿의 수가 가장 적은 사람들의 최대 체인이 있습니다. $n$사람들이 오래. 체인의 끝에있는 사람은 각 단계마다 더 많은 초콜릿을 갖게되고 체인은 하나씩 짧아집니다. (이전 단락에서 우리는 새로운 사람들이 이전의 최소 금액으로 끝나지 않을 것이라는 것을 알고 있습니다.)$n$ 모든 사람들이 더 많은 초콜릿을 가지게 될 것이고, 가능한 최소한의 숫자가 늘어날 것입니다.
따라서 가능한 최대 초콜릿 수에 대한 상한선이있는 경우 단계 끝에있는 최소 수는 결국 모든 사람이 잠재적 인 최대 수보다 같거나 적은 수에 대해 동일한 수의 초콜릿을 갖는 지점에 도달합니다.
따라서 한 단계가 끝날 때 가지고있는 초콜릿을 가장 많이 고려하십시오. 불러라$M$다음 차례에 그 사람은 초콜릿 절반을주고 절반 이하의 초콜릿을받습니다. 그가 준만큼 많이 받으면 그는 짝수 금액을 가지고 결국 같은 수의$M$. 그가 더 적게 받으면, 그가 초콜릿을 추가하더라도 그는 기껏해야 자신이 시작한 것으로 끝납니다.
그래서 .... 한 사람이 가질 수있는 가장 많은 초콜릿은 $M=$ 누구든지 가장 많이 먹은 초콜릿 $1$. 사람이 가질 수있는 최소한의 초콜릿은$L=$ 단계에서 가장 적은 초콜릿 $1$그러나 모든 사람들이 같은 수를 가지지 않는 한 그 최소값은 항상 유한 한 단계에서 증가 할 것입니다. 최소값이 얼마나 높은지에 대한 한계가 있기 때문에 프로세스는 동등하게 끝나야합니다. 결국.