OliForum Matematico

Sto leggendomi un ebook di esercitazioni alle olimpiadi e mi sono imbattuto in questo rproblrma di logica (non certo di combinatoria, ma non trovo una sezione più consona):

Alberto per sconfiggere la solitudine ha inventato un gioco. All'inizio vi sono n bastoncini in pila, e poi Alberto pu` o fare una di queste tre mosse: a) Scegliere una pila con almeno 4 bastoncini e spezzarla in 4 pile;

b) Scegliere una pila con y bastoncini, toglierle un numero di bastoncini k ≤ y 2 e spostarli su un'altra pila;

c) Scegliere una pila con almeno 2 bastoncini, spezzarla in 2 pile e quindi aggiungere una nuova pila con 5 bastoncini.

Alberto vuole, mediante solo queste mosse, raggiungere una configurazione in cui tutte le pile hanno un solo bastoncino. Per quali n Alberto pu` o vincere la partita? Con che strategia?

Non ho capito la soluzione, qualcuno me lo potrebbe spiegare meglio?

Soluzione: Chiamiamo n il numero totale di bastoncini presenti su tutte le pile, e m il numero di pile. All'inizio, m = 1 ed n ` e assegnato, alla fine n0 = m0. Esaminamo come agiscono su questi due valori le varie mosse. a) n non varia mentre m0 = m + 3.

b) n ed m restano entrambi invariati;

c) n0 = n + 5 ed m0 = m + 2. A questo punto si pu` o notare come l'espressione (n−m) mod 3 sia un invariante in questo gioco; imponendo quindi che resti uguale all'inizio e alla fine abbiamo che (n−1) mod 3 = (n0 − m0) mod 3 = 0 = ⇒ n ≡ 1 (mod 3). Resta poi solo da verificare che ogniqualvolta n ≡ 1 (mod 3) il gioco ha effettivamente soluzione; ma questa soluzione si ottiene semplicemente applicando ripetutamente la mossa a) ogni volta creando 3 nuove pile con 1 bastoncino l'una.

Combinatoria
Conteggi, probabilità, invarianti, logica, matematizzazione, ...

La sezione è quella giusta ^_^


La soluzione proposta cerca innanzitutto due proprietà facili da studiare e le associa a due valori n e m.
Dal testo del problema vengono ricavati i valori di n e m all'inizio e alla fine del gioco.
A questo punto vengono studiati i cambiamenti apportati a queste proprietà dalle tre mosse possibili (a, b, c).
Finita questa osservazione, viene ricavata un'ulteriore proprietà (in questo caso strettamente invariante, in altri casi potrebbe anche essere una proprietà le cui variazioni possono essere facilmente controllate) che valga per tutte e tre le mosse (in questo caso la congruenza mod 3 della differenza tra n e m).
Imponendo l''unica informazione nota sulla situazione di partenza (m=1), si arriva a dire che n (il numero bastoncino nella pila iniziale) deve essere nella forma 3k+1 (o congruo a 1 mod 3).
L'ultima parte della soluzione si preoccupa di verificare che le condizioni trovate oltre ad essere necessarie, siano anche sufficienti. E quindi cerca di fornire una "guida", valida per ogni n teorizzato valido, per concludere il gioco.


Spero sia un po' più chiaro ^_^