Ercole e l'idra

[3m0o]

Il gioco del idra è un gioco che funziona nel seguente modo:

- Un idra qualunque è data, un idra è un albero finito, ovvero un grafo connesso senza cicli e un nodo specificato è chiamato $R$ ed esso è la radice del albero. Ciascun nodo ha un singolo parente (tranne la radice che non ha parenti) e un numero di figli. L'obbiettivo è rimanere con soltanto la radice $R$. In altre parole il giocatore vince il gioco se dopo un numero finito di mosse rimane solo $R$. Come si gioca?

Step 1) A ciascuna mossa il giocatore seleziona una foglia $z$ e un numero naturale $n>0$. Una foglia è semplicemente un nodo che non possiede figli.

Step 2) Selezionata la foglia $z$, il giocatore cancella $z$ e l'arco che la connette al suo parente. Denotando $x$ il parente di $z$, se $x=R$ allora il gioco continua allo step 1), altrimenti se \(x \neq R\) allora guardiamo il sotto grafo che cresce da $x$ (dopo aver cancellato $z$) e sia $y$ il parente di $x$. Attacchiamo $n$ copie del sotto grafo che cresce da $x$ al vertice $y$. Un immagine sarà più chiara

Nel immagine, il nodo nero è la radice $R$, i nodi blu sono le foglie, il nodo cancellato è quello tratteggiato,
$n$ è scelto essere uguale a $2$.

E' possibile perdere questo gioco?

[Quinzio]

Alcune cose.
Intanto direi che parente e' genitore... dall'inglese "parent".
Ma soprattutto non capisco: questo gioco e' un solitario, cioe' c'e' solo un giocatore ?
Chi decide $n$. E' un numero aleatorio ?
Quando finisce esattamente il gioco ? Vince chi fa l'ultima mossa ?

[hydro1]

Ti ringrazio 3m0o perchè mi hai sbloccato un ricordo: quando ero un teenager lessi una versione molto più complessa di questo problema e ovviamente non capii nulla della soluzione. Immagino che questa sia la versione base.

@Quinzio: per come la interpreto io, $n$ è fissato all'inizio del gioco. Il gioco è un solitario, si vince se si riesce ad uccidere l'idra, ovvero a tagliarle tutte le teste.

Voglio provare che Ercole uccide sempre l'idra, indipendentemente dalla scelta delle mosse. L'idea è di usare un monovariant, ovvero una quantità che può solo diminuire ad ogni mossa. Fisso una costante $M>n+1$ ed assegno ad ogni foglia un peso di $M^f$, dove $f$ è il numero di fratelli della foglia (compresa la foglia stessa). Chiamo $W$ il peso totale di tutte le foglie. Adesso fisso una foglia $F$. L'apporto di $F$ e i suoi fratelli al peso totale è $fM^f$. Guardiamo ora che succede quando Ercole taglia $F$. Se $f=1$, ovvero se $F$ non ha altri fratelli, il peso totale diventa $W-M$. Se $F$ invece ha $f$ fratelli, il peso dato dagli $f-1$ fratelli di $F$ diventa $(f-1)M^{f-1}$, e al peso totale delle foglie va aggiunto $n(f-1)M^{f-1}$. Prima avevamo $fM^f$, adesso abbiamo $(n+1)(f-1)M^{f-1}$. Ma per come abbiamo scelto $M$, il primo è sempre strettamente maggiore del secondo. Questo significa che qualsiasi foglia tagli Ercole, il peso totale delle foglie diminuisce. Ma siccome il peso è un intero non negativo, ad un certo punto diventerà $0$, e chiaramente è $0$ solo quando l'idra è morta.