edriv ha scritto:2 - Dimostrare che se in un albero ogni nodo ha un numero finito di figli, e in totale c'è un numero infinito di nodi, esiste un ramo infinito
Mi lancio:
Ora e in seguito considero ramo un insieme di nodi tali che:
-la radice appartiene al ramo;
-il padre di ogni nodo diverso dalla radice e appartenente al ramo, appartiene al ramo;
-per ogni nodo appartenente al ramo, al piu' un figlio di quel nodo appartiene al ramo.
ALLORA:
Dato un nodo, esiste uno e un solo ramo tale che quel nodo appartiene al ramo ma suo figlio no.
Quindi esistono infiniti rami.
Dato un nodo appartenente a n rami, esiste per il pigeonhole un figlio appartenente a almeno, detto k il numero dei figli, $ \lceil\frac{n-1}{k}\rceil $ rami.
Dato un nodo x, sia f(x) il figlio di x appartenente a piu' rami (rispetto agli altri figli di x); se ce n'e' piu' d'uno a parimerito, ne scelgo uno qualunque (assioma di scelta).
Chiamiamo r la radice.
Sia F l'insieme dei nodi esprimibili come f(f...f(r)..))
F e' un ramo.
Ogni elemento di F e' contenuto in infiniti rami.
Ora supponiamo per assurdo che la cardinalita' di F sia finita.
Prendiamo il nodo che richiede il maggior numero di f per essere scritto. Questo nodo non ha figli, quindi appartiene a un solo ramo. Assurdo.
Rilancio: trovare il problema nel forum che si risolve utilizzando esclusivamente questo fatto.
