Ercole, per sconfiggere l'idra, deve tagliarle tutte le teste. L'unica differenza con il mito è che l'idra è un grafo ad albero finito dove ogni arco è un collo e ogni nodo (tranne la radice) è una testa.
Ad ogni mossa Ercole sceglie una foglia e taglia l'arco che la sostiene (quindi cancella sia la foglia sia l'arco). Sia k un numero arbitrariamente grande (scelto dall'idra). Dal nonno della foglia tagliata spuntano k archi che terminano ciascuno in un nodo e da ognuno di questi nodi si rigenera tutta la discendenza del padre (tranne, ovviamente, la foglia e l'arco deceduti). Ovviamente se la foglia non ha un nonno non rispunta niente.
Dimostrare che Ercole, giocando oculatamente, uccide l'idra in un numero finito di mosse.
Questione bonus (difficilotta, non so assolutamente come si dimostri): riuscirà Ercole a vincere giocando in maniera casuale?
Ercole e l'idra dalle molte teste... (stage senior 2006)
Ercole e l'idra dalle molte teste... (stage senior 2006)
Ultima modifica di piever il 09 nov 2006, 23:00, modificato 1 volta in totale.
"Sei la Barbara della situazione!" (Tap)
Ok, ci provo...
Chiamo ordine di un nodo la lunghezza del percorso che lo collega alla radice.
Chiamo prole di un nodo il numero di figli.
Ora, presa l'idra:
Sia n l'ordine massimo
Sia S l'insieme dei nodi di ordine n-1
Sia k la prole massima tra gli elementi di S
Sia F l'insieme dei nodi di S con prole k.
E ora cominciamo con la doppia induzione:
1 - è possibile far abbassare il k
Preso un nodo f in F, se taglio un suo figlio, tutte le copie di f che nascono dalla testa del padre di f avranno ordine n-1 e prole k-1. Dopo questa mossa, lo stesso f ha prole k-1, e quindi se ne esce da F. Gli elementi di F sono finiti e quindi posso con calma toglierli a uno a uno.
Una volta che F è vuoto, la prole massima è k-1.
2 - è possibile far abbassare il n
Se la prole massima è 1, tagliando un nodo di ordine n, non ricresce nessun nodo di ordine n. Tagliando tutti i nodi (che sono finiti) di ordine n, porto l'ordine massimo a n-1.Altrimenti posso abbassare la prole massima fino a farla diventare 1 e agire.
3 - è possibile battere l'idra
Se l'idra ha grado massimo 1, allora è un ciuffo d'erba, e allora Ercole passa zic zac col decespugliatore. Se ha grado n, posso farlo scendere fino a farlo diventare 1.
Sarà giusto?
Chiamo ordine di un nodo la lunghezza del percorso che lo collega alla radice.
Chiamo prole di un nodo il numero di figli.
Ora, presa l'idra:
Sia n l'ordine massimo
Sia S l'insieme dei nodi di ordine n-1
Sia k la prole massima tra gli elementi di S
Sia F l'insieme dei nodi di S con prole k.
E ora cominciamo con la doppia induzione:
1 - è possibile far abbassare il k
Preso un nodo f in F, se taglio un suo figlio, tutte le copie di f che nascono dalla testa del padre di f avranno ordine n-1 e prole k-1. Dopo questa mossa, lo stesso f ha prole k-1, e quindi se ne esce da F. Gli elementi di F sono finiti e quindi posso con calma toglierli a uno a uno.
Una volta che F è vuoto, la prole massima è k-1.
2 - è possibile far abbassare il n
Se la prole massima è 1, tagliando un nodo di ordine n, non ricresce nessun nodo di ordine n. Tagliando tutti i nodi (che sono finiti) di ordine n, porto l'ordine massimo a n-1.Altrimenti posso abbassare la prole massima fino a farla diventare 1 e agire.
3 - è possibile battere l'idra
Se l'idra ha grado massimo 1, allora è un ciuffo d'erba, e allora Ercole passa zic zac col decespugliatore. Se ha grado n, posso farlo scendere fino a farlo diventare 1.
Sarà giusto?
Ok, giusto.
In alternativa si può dimostrare che ogni padre di ordine n-1 e tutte le sue "copie" possono essere cancellate in un numero finito di mosse per induzione sul numero di figlie.
P.S. Dicono dalla regia che la questione bonus è DECISAMENTE difficile, non so se è matematica olimpica, chi non ci riesce (continuo a rientrare nella categoria) non si scoraggi.
In alternativa si può dimostrare che ogni padre di ordine n-1 e tutte le sue "copie" possono essere cancellate in un numero finito di mosse per induzione sul numero di figlie.
P.S. Dicono dalla regia che la questione bonus è DECISAMENTE difficile, non so se è matematica olimpica, chi non ci riesce (continuo a rientrare nella categoria) non si scoraggi.
"Sei la Barbara della situazione!" (Tap)
-
MindFlyer
Il problema l'ho proposto io allo stage senior, dicendo che la bonus question non si può risolvere con l'induzione di Peano, ma occorre l'induzione transfinita. Questo problema è un classico della teoria degli insiemi, e l'ho proposto alla fine di tutta la lezione come curiosità e per cultura generale, mentre l'esercizio vero era solamente quello di dimostrare che Ercole ha una strategia.
-
MindFlyer
Ho spezzato il thread perché stava diventando non elementare.
Il resto della discussione è qui:
http://olimpiadi.ing.unipi.it/oliForum/ ... php?t=7198
Il resto della discussione è qui:
http://olimpiadi.ing.unipi.it/oliForum/ ... php?t=7198