Puzzle di matematica / logica
Qualcuno ha qualche idea su come risolvere questo problema? Il mio amico me ne ha chiesto e mi ha infastidito per alcuni giorni. Ho provato ad avvicinarlo per induzione (il case base con due persone è semplice, ma sono rimasto bloccato sul gradino induttivo). Comunque, ho pensato che fosse un problema divertente ed ero curioso di come affrontarlo. Eventuali suggerimenti su possibili soluzioni sarebbero adorabili!
Alcune persone stanno in cerchio scambiando oggetti. Ognuno di loro inizia con un numero pari di cioccolatini, non necessariamente lo stesso. Ogni minuto, ciascuna delle persone passa metà dei propri oggetti alla persona alla sua destra. Se qualcuno finisce con un numero dispari di cioccolatini, prende un altro oggetto da un barattolo al centro. Dimostrare che indipendentemente dalla distribuzione iniziale dei cioccolatini, dopo un numero finito di passaggi tutti si ritrovano con un numero uguale di oggetti.
Risposte
Possiamo descrivere una situazione con tre numeri $(M,m,r)$, dove $2M$ è l'importo massimo che un giocatore ha, $m$ è la quantità minima, e $r$ è il numero di giocatori con $2m$.
Se un giocatore come $2a$ pezzi e il loro vicino di sinistra ha $2b$ pezzi, nel prossimo round, questo giocatore avrà $ (2a-a)+b= a+b\le 2M$pezzi. Anche se$a+b$ è strano, lo è $\le 2M-1$ e così dopo il riempimento dal barattolo, è fermo $\le 2M$. Allo stesso modo, il nuovo importo è$\ge 2m$ con uguaglianza se e solo se $a=b=m$. Concludiamo che una situazione$(M,m,r)$ diventa $(M',m',r')$ con $m\le m'\le M'\le M$. Inoltre, se$m'=m$, poi $r'\le r$.
Ma non può succedere $(M',m',r')=(M,m,r)$ salvo che $M=m$. Infatti, se$m<M$, allora deve esserci una persona con $2m$pezzi mentre il loro vicino di sinistra ne ha di più. Allora questa persona avrà$>2m$ pezzi nel round successivo, il che significa anche quello $m'>m$ o quantomeno $r'<r$.
In ogni caso, se $M>m$, quindi ci vogliono solo passi finitamente mann fino a quando $M-m$diminuisce di almeno uno. Poi ancora dopo infinitamente molti passaggi, arriviamo$M=m$.
Considera una persona con il minor numero di cioccolatini in un passaggio. Passa metà dei suoi cioccolatini ma riceve metà dei cioccolatini da qualcuno che ne ha almeno la stessa quantità. Quindi il suo numero di cioccolatini aumenta o rimane lo stesso se anche la persona alla sua sinistra ha lo stesso numero di cioccolatini. Quindi il minor numero di cioccolatini in un passaggio non scende mai.
Supponiamo ora che una persona abbia più del minimo. Se il numero minimo di cioccolatini è$L$ e la persona con più del minimo ha $L + 2a$ poi si dà via $\frac 12L + a$ ma almeno ottiene $\frac 12L$ e così è $L + a > L$. Quindi una persona che non ha il minimo in un passaggio non può arrivare a quel minimo importo nel passaggio successivo.
Quindi il numero minimo di cioccolatini in un passaggio non può mai diminuire a un numero inferiore nel passaggio successivo. E se il numero minimo di cioccolatini in un passaggio è uguale al numero minimo di cioccolatini nel passaggio successivo, ciò può verificarsi solo se una persona con il minor numero di cioccolatini era alla destra di una persona con lo stesso numero di cioccolatini e quella persona finisce con lo stesso numero di cioccolatini.
[Nota: una persona con più del numero minimo precedente può finire nel passaggio successivo con il nuovo numero minimo che è maggiore del numero minimo precedente, ma quella persona può notare finire con il numero minimo precedente .]
Ma se tutte le persone non hanno lo stesso numero di cioccolatini (se lo fanno abbiamo finito) allora c'è una catena massima di persone con il minor numero di cioccolatini $n$le persone a lungo. Ad ogni passaggio la persona all'estremità della catena avrà più cioccolatini e la catena si accorcia di uno. (E dal paragrafo precedente sappiamo che nessuna nuova persona finirà con quella quantità minima precedente .) Quindi dopo$n$ passi ognuno avrà più cioccolatini e il minor numero possibile aumenterà.
Quindi, se esiste un limite superiore al numero massimo di cioccolatini possibile, il numero minimo alla fine di un passaggio alla fine raggiungerà un punto in cui tutti hanno lo stesso numero di cioccolatini per un numero uguale o inferiore a quel massimo potenziale.
Quindi considera il maggior numero di cioccolatini che una persona ha alla fine di un passaggio. Chiamalo$M$Nel turno successivo quella persona dà metà dei cioccolatini e riceve metà o meno cioccolatini. Se ne riceve tanti quanti ne ha regalati, ha un importo pari e finisce con lo stesso numero di$M$. Se ne riceve di meno, anche se aggiunge un cioccolatino si ritrova al massimo con quello con cui ha cominciato.
Quindi ... il maggior numero di cioccolatini che una persona può avere è limitato $M=$ il maggior numero di cioccolatini che qualcuno aveva al passo $1$. Il minimo di cioccolatini che una persona può avere è$L=$ il minimo di cioccolatini che qualcuno aveva al passo $1$ma quel minimo aumenterà sempre in un numero finito di passi a meno che tutte le persone non abbiano lo stesso numero. Poiché esiste un limite a quanto può essere alto il minimo, il processo deve terminare con l'uguaglianza. Infine.