Caramelle per tutti

Dimostrerò un risultato più generale: per un qualunque numero di persone n e di caramelle iniziali P, se tutti hanno un numero pari di caramelle, a ogni passo ne danno metà al vicino di destra ed eventualmente ricevono una caramella per averne un numero pari, prima o poi tutti ne avranno lo stesso numero. Innanzitutto vediamo che il numero massimo di caramelle che ha una singola persona non può crescere da un passo all'altro. Infatti se a un certo passo questo numero è C, chi ha C caramelle al passo successivo non ne può avere di più, e chi ne aveva meno di C al massimo ne avrà C (nel caso ne avesse C-2, e il vicino di sinistra C; in questo caso viene assegnata una caramella) In secondo luogo, supponiamo che a un certo passo il numero minore di caramelle per una persona sia c. Se c'è una sola persona che ha c caramelle, al passo successivo tutti ne avranno di più: se ce ne fosse più di una, prendiamo una catena di persone sedute una accanto all'altra, tutte con c caramelle. Se la catena è formata da tutte le persone abbiamo dimostrato la tesi; altrimenti la persona più a sinistra al turno successivo avrà più di c caramelle e quella dopo quella più a destra ne avrà sempre almeno c+2. Quindi il numero totale di persone con c caramelle diminuirà, e prima o poi si arriverà a ridurre la catena a una singola persona. Pertanto, fintantoché tutte le persone non hanno lo stesso numero di caramelle la ridistribuzione continuerà.

Un'ultima parola

Il ruolo del maestro di cerimonia è essenziale per far terminare l'algoritmo: in questo caso poi abbiamo ben due monovarianti, il numero massimo e minimo di caramelle.