Invarianti - Dispense di matematica olimpionica

[-Elisewin-]

Salve a tutti!
Temo che con questa domanda abbasserò notevolmente il livello del forum, comunque mi serve una mano... Ho appena iniziato ad approcciarmi alla matematica delle olimpiadi e, sulle dispense che ho trovato linkate sul sito (in particolare qui http://www.dmi.units.it/divulgazione/ma ... oniche.pdf ), parlando degli invarianti, riporta il seguente esempio:

Alberto per sconfiggere la solitudine ha inventato un gioco. All’inizio vi sono n bastoncini in pila, e poi Alberto può 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 queste mosse, raggiungere una configurazione in cui tutte le pile hanno un solo bastoncino. Per quali n Alberto può vincere la partita? Con quale strategia?


Chiamiamo n il numero totale di bastoncini presenti su tutte le pile, e m il numero
di pile. All’inizio, m = 1 ed n è 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ò 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.


Non ho capito il passaggio che fa per porre uguali le due quantità, e poi come sa che (n-1)mod3=(n0-m0)mod3 siano anche uguali a 0?

Poi qualcuno conosce qualche altro sito dove posso trovare una spiegazione sugli invarianti? Magari mettendole insieme posso capirci qualcosa in più

[Lasker]

Non so spiegare granché bene, quindi è più facile che tu capisca prima riguardando la dimostrazione della dispensa (secondo me ottima) che leggendo questo messaggio, ma provo lo stesso ad aiutarti:
Hai presente la conservazione dell'energia in fisica? Quando non te ne può proprio importare di meno del percorso fatto, e ti bastano alcune "variabili di stato", iniziale e finale, per trovare la risposta?
Il ragionamento che si deve fare in questo caso è molto simile:

-Valuto la quantità $Q_{iniziale}=n-m \pmod 3$ all'inizio; per farlo mi servo della mia "variabile di stato", ovvero il fatto che $m=1$ (ovviamente abbiamo una sola colonna di $n$ monete), da cui $n-m= n-1\equiv n-1 \pmod 3$.

--Valuto la quantità $Q_{finale}=n-m \pmod 3$ alla fine; per farlo mi servo dell'altra "variabile di stato", ovvero il fatto che $n=m$ (ovviamente, visto che abbiamo una moneta per ogni colonna, monete e colonne saranno nello stesso numero), da cui $n-m=n-n=0\equiv 0\pmod 3$.

Ora, in analogia con la conservazione dell'energia, non ce ne può importare proprio nulla del modo (l'ordine, il numero ed il tipo delle mosse) in cui siamo arrivati dall'istante iniziale a quello finale, in quanto dopo ogni mossa la nostra quantità è invariante!
Mostrarlo è molto semplice:
Mossa a): La mossa $a)$ ("Scegliere una pila con almeno 4 bastoncini e spezzarla in 4 pile") non influisce sul numero $n$ di monete, ma solo sul numero $m$ di pile, aggiungendone $3$.
$$n'-m'\longrightarrow n''-m''=(n')-(m'+3)\equiv n'-m'\pmod 3$$
Mossa b): La mossa $b)$ ("Scegliere una pila con $y$ bastoncini, toglierle un numero di bastoncini $k\leq \frac{y}{2}$ e spostarli su un’altra pila") non influisce sul numero $n$ di monete, e neanche sul numero $m$ di pile.
$$n'-m'\longrightarrow n''-m''=(n')-(m')\equiv n'-m'\pmod 3$$
Mossa c): La mossa $c)$ ("Scegliere una pila con almeno 2 bastoncini, spezzarla in 2 pile e quindi aggiungere una nuova pila con 5 bastoncini") opera le trasformazioni: $n'\longrightarrow n'+5$ e $m'\longrightarrow m'+2$.
$$n'-m'\longrightarrow n''-m''=(n'+5)-(m'+2)\equiv n'-m' \pmod 3$$

Ripescando il fatto che $Q_{iniziale}=Q_{finale}$, possiamo dunque scrivere:
$$n-1\equiv 0 \pmod 3 \Rightarrow n\equiv 1 \pmod 3$$
E concludiamo con l'esempio, che ci mostra la strategia vincente di Alberto in questo caso.

Spero di non aver confuso ulteriormente le idee, e mi scuso per il paragone da fisico su un forum di matematica

P.S. Per gli invarianti non mi viene in mente nulla di meglio che cercare il PSS di Engel, cartaceo oppure sul pdf disponibile in internet.

[-Elisewin-]

Credo di aver capito :3
Grazie mille! Il paragone fisico è servito ahahah