Puzzle mathématique / logique
Quelqu'un a-t-il une idée de la façon de résoudre ce problème? Mon ami m'a posé des questions à ce sujet et cela me dérange depuis quelques jours. J'ai essayé de l'aborder par induction (le cas de base avec deux personnes est simple, mais je suis resté coincé sur l'étape inductive). Quoi qu'il en soit, je pensais que c'était un problème amusant et j'étais curieux de savoir comment l'aborder. Tout conseil sur les solutions possibles serait adorable!
Certaines personnes forment un cercle en échangeant des objets. Chacun d'entre eux commence par un nombre pair de chocolats - pas nécessairement le même. Chaque minute, chacune des personnes passe la moitié de ses objets à la personne à sa droite. Si quelqu'un se retrouve avec un nombre impair de chocolats, il prend un autre objet dans un pot au centre. Prouvez qu'indépendamment de la distribution initiale des chocolats, après un nombre fini d'étapes, tout le monde se retrouve avec un nombre égal d'objets.
Réponses
On peut décrire une situation par trois nombres $(M,m,r)$, où $2M$ est le montant maximal d'un joueur, $m$ est le montant minimal, et $r$ est le nombre de joueurs avec $2m$.
Si un joueur comme $2a$ morceaux et leur voisin de gauche a $2b$ pièces, au prochain tour, ce joueur aura $ (2a-a)+b= a+b\le 2M$pièces. Même si$a+b$ c'est bizarre, c'est $\le 2M-1$ et donc après le remplissage du pot, il est toujours $\le 2M$. De même, le nouveau montant est$\ge 2m$ avec égalité si et seulement si $a=b=m$. Nous concluons qu'une situation$(M,m,r)$ se transforme en $(M',m',r')$ avec $m\le m'\le M'\le M$. De plus, si$m'=m$, puis $r'\le r$.
Mais il ne peut pas arriver que $(M',m',r')=(M,m,r)$ sauf si $M=m$. En effet, si$m<M$, alors il doit y avoir une personne avec $2m$morceaux tandis que leur voisin de gauche en a plus. Alors cette personne aura$>2m$ pièces au tour suivant, ce qui signifie que soit $m'>m$ ou au moins $r'<r$.
En tout cas, si $M>m$, alors il ne faut que des étapes infinies jusqu'à ce que $M-m$diminue d'au moins un. Puis encore après un nombre fini d'étapes, on atteint$M=m$.
Considérez une personne avec le moins de chocolats à une étape. Elle passe la moitié de ses chocolats mais reçoit la moitié des chocolats de quelqu'un qui a au moins autant de chocolat qu'elle. Ainsi, son nombre de chocolats augmente ou reste le même si la personne à sa gauche a également le même nombre de chocolats. Ainsi, le moindre nombre de chocolats à une étape ne diminue jamais.
Supposons maintenant qu'une personne ait plus que le moindre. Si le moins de chocolats est$L$ et la personne avec plus que le moins a $L + 2a$ puis il donne $\frac 12L + a$ mais obtient au moins $\frac 12L$ et ainsi a $L + a > L$. Donc, une personne qui n'a pas le moins à une étape ne peut pas aller à cette moindre quantité à l'étape suivante.
Ainsi, le plus petit nombre de chocolats dans une étape ne peut jamais diminuer à un plus petit nombre à l'étape suivante. Et si le plus petit nombre de chocolats dans une étape est le même que le plus petit nombre de chocolats dans l'étape suivante, cela ne peut se produire que si une personne avec le moins de chocolats était à droite d'une personne avec le même nombre de chocolats et cette personne se retrouve avec le même nombre de chocolats.
[Remarque: une personne avec plus du plus petit nombre précédent peut se retrouver à l'étape suivante avec le nouveau plus petit nombre qui est plus grand que le plus petit nombre précédent, mais cette personne peut noter se retrouver avec le plus petit nombre précédent .]
Mais si tout le monde n'a pas le même nombre de chocolats (si c'est le cas, nous en avons terminé) alors il y a une chaîne maximale de personnes avec le moins de chocolats $n$les gens longtemps. À chaque pas, la personne au bout de la chaîne aura plus de chocolats et la chaîne se raccourcit d'un. (Et à partir du paragraphe précédent, nous savons qu'aucune nouvelle personne ne se retrouvera avec ce montant précédent .) Donc, après$n$ étapes tout le monde aura plus de chocolats et le moins possible augmentera.
Donc, s'il y a une limite supérieure au nombre maximum de chocolats possible, alors le plus petit nombre à la fin d'une étape atteindra éventuellement un point où tout le monde aura le même nombre de chocolat pour un nombre égal ou inférieur à ce maximum potentiel.
Considérez donc le plus de chocolats qu'une personne a à la fin d'une étape. Appeler$M$Au tour suivant, cette personne donne la moitié des chocolats et reçoit la moitié ou moins de chocolats. S'il en reçoit autant qu'il en a donné, il a un montant pair et il se retrouve avec le même nombre de$M$. S'il en reçoit moins, alors même s'il ajoute un chocolat, il finit avec tout au plus ce avec quoi il a commencé.
Donc ... le plus de chocolats qu'une personne puisse avoir est limité $M=$ le plus de chocolats que quiconque avait à l'étape $1$. Le moins de chocolats qu'une personne puisse avoir est$L=$ le moins de chocolats que quiconque ait eu à l'étape $1$mais ce minimum augmentera toujours en un nombre fini d'étapes à moins que tout le monde n'ait le même nombre. Comme il y a une limite à la hauteur du minimum, le processus doit se terminer par l'égalité. Finalement.