OliForum Matematico

Ho spezzato il thread da Combinatoria:
http://olimpiadi.ing.unipi.it/oliForum/ ... php?t=6842
Mind

--------------------------------------------------------------------

E allora proviamoci, con questa induzione transfinita!

Un'idra è un grafo ad albero finito.
Gli spigoli sono i colli, i nodi senza figli sono le teste, i colli che reggono una testa li chiameremo "foglie".
Data un'idra, una mossa è (l'uccisione di) una foglia. Dopo una mossa, l'idra si trasforma nel modo indicato nel post iniziale.
Diciamo che una idra è battibile se non esiste una successione infinita di mosse.

Ora, il nostro Ercole si trova davanti ad un'idra: poveretto, è anche ubriaco!
Vorremmo dimostrare che l'idra che ha davanti è battibile. Per aiutarlo, supponiamo che ogni sotto-idra di quella davanti è battibile - una sottoidra si ottiene prendendo un nodo diverso dalla radice e considerando tutto l'albero che sta sotto (o più probabilmente sopra, se l'idra non è capovolta).

Sarà più comodo ragionare per assurdo: supponiamo che esista una successione infinita di mosse.
Definiamo "collo importante" un collo che nasce da un nodo che è figlio della radice. Insomma, un nipote della radice. Se il collo è una foglia, sarà una "foglia importante".

Ora dimostriamo questo: nel corso del suo combattimento, Ercole taglierà infinite foglie importanti. Osserviamo che tagliare una foglia importante è l'unico modo di far aumentare i figli della radice. Se Ercole, dopo un po' che combatte, non colpisce più foglie importanti, allora da quel punto in poi avremmo:
- ancora un numero infinito di mosse, diverse dalle foglie importanti
- i figli della radice in un numero fissato.
Quindi, avendo infinite mosse e finiti figli, ci sarà un figlio il cui sotto-albero sarà colpito infinite volte.
Questo però, per l'ipotesi induttiva, non è possibile.

Ora dimostriamo che è impossibile che Ercole tagli infinite foglie importanti.
Diciamo che una foglia importante ha importanza k se il nodo che la sostiene, sostiene un sotto-albero con k spigoli.
Tagliando una foglia di importanza k, spunteranno da qualche parte un numero finito (anche 0) di foglie di importanza minore di k.
Anche questa dimostrazione la impostiamo con un'induzione: se la massima importanza tra le foglie importanti è n:
- non possiamo colpire infinite volte foglie di importanza n perchè diminuiscono costantemente
- quindi dobbiamo colpire infinite volre foglie di importanza < n, che per ipotesi induttiva è impossibile.
Con questo concludiamo l'assurdo.

Ora applichiamo l'induzione transfinita: consideriamo l'insieme degli alberi finiti (sì, è un insieme), la relazione definita sopra "essere sottoalbero di" è una relazione d'ordine stretta (soddisfa le prop. antiriflessiva, antisimmetrica, riflessiva), anzi, è un buon ordine (prendiamo un insieme non vuoto di alberi, prendiamo un qualsiasi albero x di questo insieme, consideriamo il sottoinsieme di tutti gli alberi con numero di nodi minore o uguale di x,è un insieme finito, quindi ha minimo, che è anche minimo dell'insieme originale).
Quindi, se esiste un'idra imbattibile, ne esiste una tale che tutti i suo sotto-alberi siano battibili... ma questo è assurdo per quello che abbiamo dimostrato fino ad adesso.

Speriamo che funzioni! Viva l'ardore guerriero di Ercole!

edriv ha scritto: Anche questa dimostrazione la impostiamo con un'induzione: se la massima importanza tra le foglie importanti è n:
- non possiamo colpire infinite volte foglie di importanza n perchè diminuiscono costantemente

questo non e' molto vero eh!!!!!!!

xche' se ercole ammazza una foglia che e' attaccata a un collo che e' attaccata a un collo che e' attaccato alla radice quella foglia cade e il collo che e' sul collo che e' sulla radice diventa una foglia e poi si duplica cosi' sul collo che e' attaccato alla radice nascono un mucchio di nuove foglie importanti che potrebbero avere qualunque importanza!!!!! perche' sono tante eh......

ma secondo me sei sulla strada buona eh....

presempio prima potremmo dare qualche definizione tipo cosi'



e si vede che l'idra si fabbrica sempre a partire da 0 con dei + e delle f eh.... eppoi si vede anche che se a e b periscono anche a+b perisce miseramente eh....

ecco e l'unica cosa adesso e' vedere che se a schiatta neanche f(a) campa poi tanto...

ora devo prendere il pulman [color=indigo]ma pensaci che secondo me e' propio vero eh...[/color]

CIa eh.....[/i][/u]

Sì mi ero complicato troppo la soluzione... ora riprovo.
Chiamo "sotto-albero proprio" un sotto albero dell'idra che ha come radice un figlio della radice dell'idra.
I sotto-alberi originari sono di generazione 1, un sottoalbero creato da una foglia appartenente a uno di generazione 1 ha generazione 2 e così via.
Per ipotesi induttiva, non posso colpire un sottoalbero di generazione 1 infinite volte.
Quindi da un certo punto in poi non colpirà più sottoalberi di generazione 1.
Ma allora di generazione 2 infinite volte... ma neanche quelli vanno bene.

Visto che con le generazioni gli spigoli dei sottoalberi diminuiscono costantemente. Ercole ha vinto.

Posto la mia (anche se è più o meno uguale a quella di katerina):

Sia $ G $ un grafo ad albero, con radice nel punto $ r $.

Sia $ g(p) $ il grafo ad albero avente per radice il vertice $ p $ e contenente tutta la sua discendenza.

Sia $ h(p) $ il grafo ad albero avente per radice il padre di $ p $ e contenente tutti gli elementi di $ g(p) $

Un grafo è imbattibile se può sopravvivere in eterno, altrimenti è battibile.

1) "Se per ogni $ p\in G $ con $ p\neq r $ si ha che $ g(p) $ è battibile, allora anche $ G $ è battibile": questa implicazione implica che ogni idra è battibile (induzione transfinita).

2) Se $ g(p) $ è battibile, allora anche $ h(p) $ è battibile.

Dimostrazione:

Se $ h(p) $ fosse imbattibile, allora $ A) $ si genererebbero infiniti $ g(.) $ dove $ . $ è un "fratello" di $ p $ oppure $ B) $ si genererebbe un $ g(.) $ imbattibile.

Mettiamo in un grafo ad albero (chiamiamolo $ F $) tutte le posizioni raggiungibili da $ g(p) $ dove il nodo rappresentante $ g(p) $ è la radice di $ F $.

Se almeno una tra $ A) $ e $ B) $ fosse vera, allora in $ F $ ci sarebbe una discesa infinita, quindi otterremmo che anche $ g(p) $ è imbattibile.

3) Siano $ a_1,...,a_n $ i figli di $ r $

Se $ g(a_1),...,g(a_n) $ sono tutti battibili, allora anche $ h(a_1),...,h(a_n) $ sono battibili. Quindi, essendo questi sottografi "indipendenti" tra loro, anche la loro unione (cioè $ G $) è battibile. Per cui, per il passo 1), ogni idra è battibile.

cia e' raga!

allora. la soluzione di edriv non funzia, e si vede perche' ammazzando cose di una generazione possono nascere nuove cose di un'atra eh!!!! il problema e' propio lo stesso della dimostrazione che avevi proposto prima!!!


quella di piver pero' funziona! (anche se non l'ho propio capita tantissimo... voglio dire la cosa dell'albero dei sottopezzi dell'idra eh... io non lo so propio fare...
e poi quella cosa della discesa infinita... ma non dire che e' uguale alla mia eh... la mia era solo un'idea a caso, mica una soluzione

pero' pensavo
se ci fidiamo di minde che dice che coll'induzione, diciamo, aritmetica il prob non funzia. allora si vede che nessuna delle soluzioni che ha fatto edriv poteva funzionare eh... perche' se usa solo argomenti tipo prendo il minimo n tale che oppure dimostro che se vale a una genrazione allora vale anche alla successiva e queste sono tutte cose che si fanno per induzione no?

anche piva pero' quando scrive induzzione transfinita sta solo facendo questo argomento --- se ho una certa propieta' che ogni volta che vale per ogni sottoalbero di un albero allora vale per tutto l'albero allora quella propieta vale per ogni albero. e questo argomento si fa anche per induzione col numero dei nodi dell'albero. voglio dire propio l'induzione normale eh!!!!!!

Ma allora dove sta la cosa trasifita???

Provo a riscrivere meglio la mia soluzione...
Suppongo sempre che ogni sottoalbero sia battibile.
Divido i sottoalberi (propri) in generazioni, come prima.

Sui (finiti) sottoalberi di generazione 1, posso fare un numero finito di mosse, quindi nel corso di un combattimento, dal momendo x1 in poi, diciamo, non ci saranno più mosse sui sottoalberi di generazione 1.
Quindi, da x1 in poi abbiamo ancora infinite mosse da fare. Ma sugli alberi di generazione 2 possiamo farne solo una quantità finita (e gli alberi di generazione 2 non aumentano! Possono aumentare solo se tagliamo una foglia (importante) da un albero di generazione 1, ma dal momendo x1 in poi gli alberi di generazione 1 non li tocchiamo più!)
Quindi dal momento x2 in poi Ercole non colpisce più alberi di generazione 1 o 2.
Allo stesso modo ci sarà un punto x3 (e gli alberi di generazione 3 non aumentano, da x2 in poi)... e così via.
Ma siccome i rami degli alberi calano di generazione in generazione, questo è assurdo.

Katerina89 ha scritto:anche piva pero' quando scrive induzzione transfinita sta solo facendo questo argomento --- se ho una certa propieta' che ogni volta che vale per ogni sottoalbero di un albero allora vale per tutto l'albero allora quella propieta vale per ogni albero. e questo argomento si fa anche per induzione col numero dei nodi dell'albero. voglio dire propio l'induzione normale eh!!!!!!

Ma allora dove sta la cosa trasifita???

Quel passaggio non l'ho esplicitato, ma non mi pare che basti un'induzione "di Peano", comunque se credi si riesca, prova a formalizzare. Con l'induzione transfinita invece si riesce facilmente, perché basta che tu prendi un'idra qualunque. Costruisci un grafo ad albero uguale all'idra dove ogni nodo $ p $ del grafo corrisponde a $ g(p) $ nell'idra. A questo punto, nel nuovo grafo, ogni nodo è battibile se lo è tutta la discendenza, quindi, proprio per induzione transfinita anche la radice (ovvero l'idra) è battibile.

Chiaro ora?

Credo che Katerina avesse da dire qualcosa non sulla tua soluzione, ma sull'affermazione di Mind: "Questo problema non si risolve con l'induzione di Peano".

Però, se risolviamo il problema in questo modo:
"un'idra con un solo nodo è battibile"
"se sono battibili tutte le idre con n nodi o meno, è battibile anche un'idra con n+1 nodi"
E sembra che funzioni... (sembra).
Quindi non è chiaro cosa volesse dire Mind.

[edit, visto che mind ha già risposto... io ho solo letto questo http://it.wikipedia.org/wiki/Induzione_transfinita]

Ma lo sapete cos'è l'induzione transfinita?
Ad ogni modo credo che abbiate frainteso quello che dice katerina. Non sta mettendo in dubbio la mia affermazione: dice soltanto che in forza di essa, le vostre argomentazioni sono errate.

edriv ha scritto:"se sono battibili tutte le idre con n nodi o meno, è battibile anche un'idra con n+1 nodi"

Esatto, il cruccio è proprio qui. Questo non lo puoi dimostrare con l'induzione standard.
Prova...

cia eh....

in realta' come l'ha fatto piva va bene eh.... si, cioe', almeno l'inizio lo capisco e poi boh???....

solo che quando dice di aver fatto quella cosa tranifinitfuturistica, in realta', sta solo facendo questo eh... : dimostro per induzione che ogni idra krepa: 0 nodi ok, n+1 nodi, mi basta dimostrare che se ogni sottoidra krepa lei krepa, e questo mi basta perche' le sottoidre hanno necessariamente n o meno nodi e krepano per ipotesi induttiva.

ora provo a riscrivere l'inizio della dimostrazione di piva. insomma quando fa quell'albero con le idre e poi dice discesa infinita e poi non si capisce piu' niente. eh........

scusami piv se ho cambiato un po' i simboli, ma e' solo perche' altrimenti non capisco l'operazione che tu hai chiamato h e' sostanzialmente quella che io ho chiamato f, solo che produce un'idra dato un nodo che individua una sottoidra di un'idra che c'e' gia'. erdonami ma mi incasina davvero


noto che ogni idra A si puo' scrivere come f(A_1)+f(A_2)+...+f(A_n) e che l'insieme delle idre f(A_1) e f(A_2) etc. e' determinato da A quindi a buon diritto posso decidere di chiamare le idre f(A_1) e f(A_2) etc. le componenti di A.

sappiamo che ci basta mostrare che se X stianta, allora f(X) stianta

immaginiamo di essere li' davanti a ettore e l'idra a vedere il combattimento e ci scriviamo i colpi che da e disegnamo tutte le idre che vengono ad ogni colpo. all'inizio c'e' X_0 che e' propio f(X) poi si becca un colpo e cambia un po' e diventa X_1 poi giasone molla un altra botta e l'idra diventa X_2 eccetra. magari dopo un po' finiscono, magari no.

adesso faccio una successione di grafi ad albero G_0 G_1 G_2 G_3 ecc che hanno queste prpieta'
* i nodi di tutti i G sono idre
** per ogni numero n le componenti di X_n sono foglie di G_n
*** per ogni numero n G_(n+1) si ottiene connettendo una quantita' finita di nuove foglie a precisamente una foglia di G_n

ecco e si fa cosi'

G_0 ha un solo nodo che e' X_0 e verifica le prop. * ** e ***

G_(n+1) si fa guardando quale componente di X_n e' stata vulnerata da dall'n+1-esimo colpo di achille sia questa f(A) vediamo che X_(n+1) sara' fatta dalla somma delle altre componenti di X_n + quello che resta di f(A) dopo il colpo sia questo rimasuglio f(B_1)+f(B_2)+etc. ebbene G_(n+1) si ottiene collegando a f(A) che e' una foglia di G_n per ** le nuove foglie f(B_1) f(B_2) &c e' facile vedere che questo G_(n+1) verifica ancora ***e***.

ci siamo ora gefiniamo GG il grafo ottimo massimo che e' l'unione di tutti i grafi G_0 G_1 G_2 etcetera intedo dire l'unione degli insiemi eh... considerando che G_0 e' un sottoinsieme di G_1 e G_1 un sottoinsieme di G_2 e via dicorrendo eh...

osserviamo che GG ha almeno tanti nodi quanti sono i colpi che enkidu ha dato, e che quindi, se sono in numero finito sigurdr avra' ucciso il bahamuth in un numero finito di turni eh!!!!!! wink:

era cosi' che iniziava la tua dimostrazione piva???

cia e' raga


ah e l'ho fatto apposta a non usare quella cosa del tex xche sul mio compiuter si vede malissimo!!!!!!!!! eh!!!!!!!!

@ mind: in effetti anch'io non ne so molto di induzione transfinita...

@ katerina e edriv: in effetti è vero, il passo 1 si fa anche solo con l'induzione classica, ora provo a riscrivere un po' meglio l'intera soluzione. (magari cercando di non cambiar la notazione, né il nome dell'eroe..)

1) Sia $ G $ l'idra imbattibile con il minor numero di nodi. Siccome essa è composta dai vari $ h(a_1),...,h(a_n) $ dove $ a_1,...,a_n $ sono i figli di $ r $ (la radice di $ G $), essendo queste componenti indipendenti tra loro, l'idra è imbattibile sse una di esse lo è. Supponiamo che $ a_1 $ sia imbattibile. Essendo $ G $ la minor idra imbattibile, abbiamo che $ G=h(a_1)>g(a_1) $

Ora dimostro che se $ g(a_1) $ è battible allora anche $ h(a_1) $ lo è, che è un assurdo.

Da notare che questa dimostrazione, per essere corretta deve contenere questa stramaledetta induzione transfinita...

Sia $ F $ con radice $ a_1 $ il grafo ad albero rappresentante tutte le posizioni raggiungibili a partire da $ g(a_1) $

Diciamo che $ p $ è i figlio di $ q $ sse $ g(q) $ con una mossa diventa $ g(p) $ mentre $ p $ è discendente di $ q $ sse $ g(q) $ con un numero finito e nonnullo di mosse diventa $ g(p) $

Ora questo grafo, essendo $ g(a_1) $ battibile, non contiene rami che scendono all'infinito.

Diciamo che un punto $ p $ è simpatico sse "se $ g(p) $ è battibile, anche $ h(p) $ lo è"

Dunque possiamo provare a dimostrare che, se ogni $ p $ discendente di $ q $ è simpatico, allora anche $ q $ è simpatico. Questo, per induzione, implicherebbe la tesi.

Supponiamo che $ q $ non sia simpatico. Allora Ercole tocca $ g(q) $ un numero finito di volte. Essendo $ h(q) $ imbattibile, si deve generare un $ h(p) $ imbattibile, oppure si generano infiniti $ h(p) $ (e quindi infiniti $ g(p) $), dove $ p $ è un discendente di $ q $.

Nel primo caso abbiamo che $ g(p) $ è raggiungibile da $ g(q) $ e quindi è battibile, mentre $ h(p) $ è imbattibile. Per cui $ p $ non è simpatico.

Nel secondo caso, esiste una serie infinita $ p_1,p_2,... $ dove $ p_1 $ è un discendente di $ q $ e, se $ m>n $, allora $ p_m $ discende da $ p_n $

Ma questo è assurdo perché $ g(q) $ è battibile, e se esistesse questa serie Ercole potrebbe passare da un elemento al successivo senza finire mai.

QED

Ok, ora mi è ripreso l'interesse per questo problema!

Terminologia
Le componenti dell'idra, definite da Katarina, sono le sottoidre che nascono da un collo che nasce dalla radice.
La generazione di una componente, durante il combattimento, è definita in questo modo: all'inizio la generazione di ogni componente è 1, e una componente è di generazione n+1 se è stata creata dopo un colpo su una di generazione n.

Intanto correggo la mia dimostrazione che era palesemente falsa, ma correggibile. L'errore era questo: per dimostrare che una certa componente non poteva essere tagliata infinite volte, dicevo che aveva meno nodi della componente iniziale, falsissimo! Non può perchè è una idra ottenibile dalla componente iniziale, che è battibile. Ora la riscrivo velocemente.
Prima dimostro che ogni generazione da un certo punto in poi non e' piu' toccata in combattimento. Per induzione, da un certo punto in poi le generazioni < n non sono più toccate. Se tocco infinite volte la generazione n, da un certo punto in poi le componenti di questa generazione non aumentano e sono finiti, quindi ne becco uno infinite volte. Ma questo è impossibile perchè è una sottoidra della componente iniziale, per ipotesi battibile.
Quindi ogni generazione dopo un po' scompare o viene lasciata in pace, ma i colpi sono infiniti, quindi ci sono infinite generazioni. Ma questo è assurdo, perchè scendendo di generazione in generazione è come se continuassi a dare colpi alla componente principale, che poveretta prima o poi crepa.
Remark. Più in basso dimostro che è sbagliata.

Ora ridescrivo l'albero di Kate che ci fa vedere molto bene dentro il problema. Parto dalla componente iniziale, e ogni volta che un colpo su una certa componente A ottengo una nuove componenti B, attacco le varie B come foglie di A. L'albero è ottenuto continuando questa costruzione per tutta la durata del combattimento, anche se è infinito.

Proprietà dell'albero di Kate
- se c'è un combattimento infinito, ha infiniti nodi.
Dim. ogni colpo di spada colpisce un nodo dell'albero. Se sono infiniti, c'è una componente tartassata infinite volte, ma ogni componente si può ottenere combattendo dalla componente iniziale, che è battibile
- non ha rami infiniti
Dim. Se ha un ramo infinito, considero tutti i colpi sul nodo di generazione 1 finchè non nasce quello di generazione 2, poi tutti i colpi su quello finchè non nasce quello di generazione 3 e così via. Immagino che tutti questi colpi siano stati dati alla componente iniziale. Purtroppo questa prima o poi crepa.
- ogni nodo ha solo finiti figli
Dim. Quel nodo non lo posso tartassare infinite volte, quindi prima o poi Ercole smette di colpirlo. Ogni volta che ho tagliato su quella componente, ho aggiunto finiti figli, e lo ho tagliato finite volte. Quindi alla fine ha finiti figli.

Confronto delle dimostrazioni di piever ed edriv
Pietro dice: "Beh, la componente principale è battibile, quindi prima o poi smette di beccarla. Ora ho infiniti colpi, ognuno discendente di una tra le idre di generazione 2. Quindi, c'è un'idra di generazione 2, i cui discendenti beccano infiniti colpi. Ripetendo questo ragionamento, trovo un ramo infinito di idre."
Riscrivo la sua dimostrazione in altro modo:
"Nell'albero di Kate, ci sono infiniti nodi. Cerco quali sono i nodi con infiniti discendenti. Beh, la radice c'è. E se ho un nodo in questo insieme, siccome i suoi figli sono finiti, almeno uno dei suoi figli è in questo insieme. Quindi è facile trovare un ramo infinito, assurdo."

Edriv dice: "Beh, supponiamo che le generazioni siano finite. Allora chiaramente ci sarebbero finiti nodi, ognuno colpito finite volte. Assurdo. Allora ci sono infinite generazioni, e trovo un ramo infinito, assurdo."
Niente di più sbagliato. Se ci sono infinite generazioni, potrebbe benissimo avere rami arbitrariamente lunghi e nessuno infinito!!
Ricordiamo infatti che è l'idra a decidere in quante copie duplicarsi!
Resta la seguente domanda: è vero che l'idra può far diventare il combattimento lungo quanto vuole? Sì, chiaramente, basta pensare con due colli uno sopra l'altro. Ercole taglia il primo e l'idra ne fa crescere tantomila.
Il problema è che quando combatto lungo più rami, ho tante idre uguali alla prima componente che decrescono in parallelo (pensate come susseguirsi di generazioni), ma ognuna a modo suo, e decide lei quanto tempo ci metterà Ercole a farla fuori. Questo secondo me è uno dei motivi per cui l'induzione non puù funzionare.

E ora aggiungiamo qualcos'altro di tremendamente interessante.

1) viewtopic.php?t=7468
2) viewtopic.php?p=69103
3) viewtopic.php?t=6579

Tesi: sono la stessa cosa.
Il problema è (thread numero 1) il seguente:
In un albero, ogni nodo ha finiti figli e in totale ci sono infiniti nodi. Dimostrare che ha un ramo infinito.

Problema dell'idra:
Considero f(A), dove A è un'idra battibile. Considero l'albero delle componenti descritto da Katerina, e guardo il combattimento attraverso questo albero. Ogni nodo viene beccato finite volte e le spadate sono infinite, quindi ci sono infiniti nodi. Ogni nodo genera finiti figli ad ogni colpo e viene colpito finite volte, quindi alla fine ha finiti figli. Quindi c'è un ramo infinito. Ma se considero i colpi su quel ramo infinito, è come se facess infiniti colpi sulla componente principale, assurdo.
Si conclude con l'induzione di Peano, usando le f(x) e i + come descritto da Katarina.

Problema delle piastrelle:
Considero tutti i piastrellamenti di quadrati centrati nell'origine, ordinati per inclusione. I nodi sono infiniti perchè posso piastrellare ogni quadrato. Le piastrelle sono finite, quindi posso bordare un quadrato solo in un numero finito di modi. Quindi esiste un ramo infinito, ovvero un modo di pavimentare correttamente il piano.