Problema C1 Ammissione Winter camp 2019 [L03\4]

[Stef2008]

Attorno a un tavolo circolare siedono n ≥ 3 bambine, ciascuna con alcune mele (anche nessuna). Se la maestra si accorge che una bambina ha più mele della somma delle
sue due vicine, gliene toglie una e ne dà una ciascuno alle sue due vicine (la maestra ha un cesto infinito di mele da cui attingere). Dimostrare che il processo in ogni caso
terminerà dopo un numero finito di passi.

Ho trovato una soluzione ma mi è sembrata troppo semplice, quindi non sono sicuro sia corretto. Sarei grato a chi ne confermasse la correttezza o in caso di errore per chi mi spiegasse dove è. Questa è la mia soluzione:

Testo nascosto:

Lemma 1: Sia N il numero massimo di mele posseduto da qualcuno, nel corso del processo non ci sarà mai nessuno con più mele
Dimostrazione
Sia k un passaggio con massimo N, allora siano C una bambina che aumenta il suo valore, essa ha inizialmente al più N-1 mele quindi con aumento di uno sara minore o uguale ad N quindi anche nel passaggio k+1 il massimo sarà al più N. Essendo all'inizio N per induzione sarà sempre minore uguale a N. □

Notiamo ora che ogni passaggio il numero totale di mele aumenta di 1, quindi dato che il massimo è fisso non si potrà continuare all'infinito. ■

[ronny]

A me sembra funzionare.

Testo nascosto:

Effettivamente nessuna bambina potrà superare N.
Come dici tu il numero di mele aumenta di 1 ad ogni passo quindi prima o poi il processo si ferma.

[Stef2008]

Grazie mille!!