Enigma Matemático / Lógico
Alguém tem alguma ideia de como resolver este problema? Meu amigo me perguntou sobre isso e isso está me incomodando há alguns dias. Tentei abordá-lo por indução (o caso básico com duas pessoas é direto, mas fiquei preso na etapa indutiva). De qualquer forma, achei o problema divertido e estava curioso em saber como abordá-lo. Quaisquer dicas sobre possíveis soluções seriam ótimas!
Algumas pessoas formam um círculo trocando objetos. Cada um deles começa com um número par de chocolates - não necessariamente iguais. A cada minuto, cada uma das pessoas passa metade de seus objetos para a pessoa à sua direita. Se alguém terminar com um número ímpar de chocolates, eles pegam outro objeto de uma jarra no centro. Prove que, independentemente da distribuição inicial dos chocolates, após um número finito de etapas, todos acabam com um número igual de objetos.
Respostas
Podemos descrever uma situação por três números $(M,m,r)$, Onde $2M$ é a quantidade máxima que um jogador tem, $m$ é a quantidade mínima, e $r$ é o número de jogadores com $2m$.
Se um jogador como $2a$ peças e seu vizinho esquerdo tem $2b$ peças, na próxima rodada, esse jogador terá $ (2a-a)+b= a+b\le 2M$peças. Mesmo se$a+b$ é estranho é $\le 2M-1$ e assim, após encher do frasco, ainda é $\le 2M$. Da mesma forma, o novo valor é$\ge 2m$ com igualdade se e somente se $a=b=m$. Concluímos que uma situação$(M,m,r)$ torna-se em $(M',m',r')$ com $m\le m'\le M'\le M$. Além disso, se$m'=m$, então $r'\le r$.
Mas não pode acontecer que $(M',m',r')=(M,m,r)$ a menos que $M=m$. Na verdade, se$m<M$, então deve haver alguma pessoa com $2m$peças enquanto seu vizinho esquerdo tem mais. Então essa pessoa terá$>2m$ peças na próxima rodada, o que significa que qualquer um $m'>m$ ou pelo menos $r'<r$.
De qualquer forma, se $M>m$, então são necessários apenas passos finitos até $M-m$diminui em pelo menos um. Então, ainda depois de finitamente muitos passos, alcançamos$M=m$.
Considere uma pessoa com o menor número de chocolates por etapa. Ela passa metade dos chocolates, mas recebe metade dos chocolates de alguém que tem pelo menos a mesma quantidade de chocolate que ela. Portanto, seu número de chocolates aumenta ou permanece o mesmo se a pessoa à sua esquerda também tiver o mesmo número de chocolates. Portanto, o menor número de chocolates em uma etapa nunca diminui.
Agora, suponha que uma pessoa tenha mais do que o mínimo. Se o menor número de chocolates for$L$ e a pessoa com mais do que o mínimo tem $L + 2a$ então ele dá $\frac 12L + a$ mas consegue pelo menos $\frac 12L$ e então tem $L + a > L$. Portanto, uma pessoa que não tem o mínimo de uma etapa não pode fazer o mínimo na próxima etapa.
Portanto, o menor número de chocolates em uma etapa nunca pode diminuir para um número menor na próxima etapa. E se o menor número de chocolates em uma etapa for igual ao menor número de chocolates na próxima etapa, isso só pode ocorrer se uma pessoa com o menor número de chocolates estiver à direita de uma pessoa com o mesmo número de chocolates e essa pessoa acaba com a mesma quantidade de chocolates.
[Observação: uma pessoa com mais do que o menor número anterior pode terminar na próxima etapa com o novo menor número que é maior do que o menor número anterior, mas essa pessoa pode notar que termina com o menor número anterior .]
Mas se todas as pessoas não têm o mesmo número de chocolates (se tiverem, estamos prontos), então há uma cadeia máxima de pessoas com o menor número de chocolates $n$as pessoas desejam. A cada passo a pessoa no final da corrente terá mais chocolates e a corrente encurta em um. (E a partir do parágrafo anterior, sabemos que nenhuma nova pessoa vai acabar com a menor quantidade anterior .) Então, depois$n$ passos todos terão mais chocolates e o menor número possível aumentará.
Portanto, se houver um limite superior para o número máximo de chocolates possível, o menor número no final de uma etapa eventualmente chegará a um ponto em que todos têm o mesmo número de chocolate para algum número igual ou inferior ao máximo potencial.
Portanto, considere o máximo de chocolates que uma pessoa consome no final de uma etapa. Chame-o$M$Na próxima jogada, essa pessoa dá metade dos chocolates e recebe metade ou menos chocolates. Se ele receber tantos quantos deu, ele tem uma quantia par e acaba com o mesmo número de$M$. Se ele receber menos, mesmo que acrescente um chocolate, ele acaba com, no máximo, o que começou.
Então .... o máximo de chocolates que uma pessoa pode comer é um limitado $M=$ o maior número de chocolates que alguém comeu $1$. O mínimo de chocolates que uma pessoa pode comer é$L=$ o mínimo de chocolates que alguém comeu $1$mas esse mínimo sempre aumentará em um número finito de etapas, a menos que todas as pessoas tenham o mesmo número. Como há um limite para quão alto o mínimo pode ser, o processo deve terminar com igualdade. Eventualmente.