Giochi matematici #053 — Sprouts: quante mosse possono nascere da pochi punti?

Invece di contare le linee già tracciate, conta quanti rami potrebbero ancora terminare in ciascun punto.

Un punto senza linee ha tre possibilità residue; uno con due rami incidenti ne ha una; uno con tre non ne ha più nessuna. A questi posti disponibili possiamo dare il nome di vite.

Ogni mossa consuma due vite, ma crea anche un punto nuovo. Quante vite possiede quel punto appena nato?

La linea passante per il nuovo punto produce già due rami incidenti: il nuovo punto dispone quindi di una sola vita. Il saldo della mossa è negativo di una unità.

Un invariante che diminuisce

Chiamiamo grado di un punto il numero dei rami di linea che vi terminano; un cappio contribuisce due al grado del punto in cui si chiude. Definiamo le sue vite residue come 3 − grado. Per le regole del gioco questa quantità è sempre un intero non negativo.

All’inizio ci sono n punti isolati, tutti di grado zero, quindi le vite disponibili sono esattamente L(0) = 3n. Non importa dove si trovino i punti nel piano.

Il bilancio di una mossa

Una mossa collega due estremità, che possono anche coincidere nello stesso punto: questo consuma due vite sui punti preesistenti. La curva riceve un punto nuovo nel proprio interno; i due segmenti che lo raggiungono conferiscono a quel punto grado 2, quindi una vita ancora disponibile. Il saldo complessivo è dunque −2 + 1 = −1.

Se m è il numero di mosse già eseguite, il numero totale di vite residue è perciò L(m) = 3n − m. È un’identità esatta per ogni posizione raggiungibile, indipendentemente da quanto si siano intrecciate le regioni del foglio.

La mossa finale non può consumare tutte le vite

Supponiamo che la partita sia durata m mosse. Il punto creato nell’ultima mossa ha ancora una vita, perché su di esso terminano soltanto i due tratti della nuova curva. Per questo, anche se non esistono ulteriori mosse legali, alla fine vale L(m) ≥ 1.

Sostituendo la formula: 3n − m ≥ 1, cioè m ≤ 3n − 1. La dimostrazione è conclusa. Inoltre, ogni partita finisce: a ogni mossa L diminuisce di una unità e non può scendere sotto zero.

Perché non basta vedere due punti con una vita

Non è vero il viceversa: due vite disponibili non garantiscono necessariamente una mossa. Le curve già disegnate possono aver suddiviso il foglio in regioni diverse, impedendo di collegare due punti senza attraversare linee. L’invariante fornisce quindi un limite superiore, non una formula per il numero preciso di turni.

C’è anche un risultato più forte e classico: ogni partita di Sprouts con n punti iniziali dura almeno 2n mosse. Dunque 2n ≤ m ≤ 3n − 1. Il limite inferiore richiede un’argomentazione topologica ulteriore, non implicata dal solo bilancio delle vite; si veda Joseph Malkevitch, Sprouts (CUNY).

La descrizione di Sprouts mediante punti e curve è quella di un grafo piano costruito per mosse successive. Ogni vertice ha grado al più tre. Non servono coordinate né misure degli angoli: contano adiacenza, disposizione nel piano e possibilità di tracciare una curva senza intersezioni.

La quantità L è una funzione potenziale: a ogni mossa cambia di un ammontare determinato. È lo stesso genere di idea che compare nelle dimostrazioni di terminazione degli algoritmi: si individua una quantità intera limitata inferiormente che decresce a ogni passo.

La vita residua è una risorsa necessaria, ma non sufficiente: la topologia delle regioni può proibire una connessione. Ecco perché un gioco che sembra basato soltanto sui gradi dei vertici richiede anche ragionamento geometrico.

Per regole e limite superiore si veda Wolfram MathWorld, Sprouts.

Parti da un solo punto. La prima mossa possibile deve essere un cappio che torna al punto iniziale, con un punto nuovo sulla curva. Il punto iniziale e quello nuovo dispongono ora ciascuno di una vita. Essendo entrambi sul bordo dello stesso cappio, possiamo collegarli sul lato interno oppure esterno, senza attraversare la linea.

Dopo questa seconda mossa, i primi due punti avranno grado 3; il punto nuovo, nato sull’ultimo tratto, avrà una sola vita. Non si può più giocare: con n = 1 il limite superiore dà 3·1 − 1 = 2, ed è raggiunto. Chi vince con la regola dell’ultima mossa? Il secondo giocatore.

Variante strategica: con due punti iniziali, prova sia una mossa che li collega sia un cappio su uno solo dei punti. Puoi già dedurre dal limite generale che la partita durerà quattro o cinque mosse, pur senza conoscere ancora la strategia ottimale.

Sprouts fu inventato nel 1967 da John Horton Conway e Michael Paterson. Il suo fascino sta nel contrasto fra una regola elementare, accessibile anche a ragazzi con carta e matita, e problemi di strategia complessi, che richiedono spesso analisi di molte posizioni.

Se invece di far vincere chi gioca l’ultima mossa si applica la convenzione misère, cioè l’ultima mossa fa perdere, le stesse posizioni possono avere strategie vincenti diverse. Il conteggio delle vite e il limite alla durata restano però invariati.

Per altre formulazioni, riferimenti e varianti su superfici differenti: MathWorld e Lemoine–Viennot, Sprouts Game on Compact Surfaces.