Skip to content

10 1 e Distanza in un albero

11 novembre 2011

Stavo per perdermi una ricorrenza carina! La data di oggi si scrive con ben 5 numeri 11: è uno spasso da pronunciare se uno pizzica la “c”! Per un blog di matematica ricreativa, questa data rappresenta un po’ una festa comandata, e festeggiarla è quasi d’obbligo.

Non è facile inventarmi un gioco su due piedi, tanto più che le ragazze hanno formato una lobby per impedirmi di creare giochi con date o con orari. È una sorta di razzismo ludico, ma capisco il loro punto di vista. Pensavo che avrei potuto fare uno di quei giochetti autoreferenziali del tipo “completa la frase: in questo articolo la cifra 1 compare _ volte”. E invece per fortuna è uscito qualcosa di un po’ più tosto. Diciamo che darebbe del filo da torcere anche a Marta. Forse.

Questo articolo è stato pianificato per essere pubblicato alle 11:11 dell’11/11/11. Forse verrà pubblicato all’ora inglese, il mio attuale fuso orario, ma spero che sul sito salvi comunque questa sfilza di 1.

Il numero 1111111111 è più di un miliardo! Però però… potremmo pensare che sia scritto in base due. Se escludiamo i secondi, è proprio il più grande numero binario che può saltare fuori dall’agenda e dall’orologio. Nella nostra numerazione decimale, corrisponde a 2^{10} - 1 = 1023, un numeretto molto più alla buona.

Ora facciamo un saltino di palo in frasca. O meglio, di palo in albero. Disegniamo su un foglio di carta un albero, in modo tale che dal tronco partano due grossi rami, che ogni ramo si biforchi a sua volta in due rami minori, e così via: ogni ramo si divide sempre in due rametti più piccoli. Effettuiamo un totale di 9 biforcazioni.


Ebbene sì, non è un albero qualunque. Infatti, non a caso, contando quanti rami ha in totale incluso il tronco, otteniamo proprio 1023. Scegliamo ora invece a caso, in modo equiprobabile, due rami distinti dell’albero. Possiamo scegliere anche il tronco.

Fatto? Quanto distano in media?

La distanza tra due rami si calcola contando quanti salti occorre fare partendo da uno dei due rami, e risalendo fino al primo ramo antenato in comune, per poi raggiungere il secondo ramo. Può essere un po’ più chiaro dai seguenti esempi. Uno dei due rami viola di sinistra dista 1 dal ramo arancione di sinistra. Dista 2 dall’altro ramo viola di sinistra, poiché il percorso passa per il ramo arancione. Dista 2 anche dal ramo nero. Dista invece 4 da ciascuno degli altri due rami viola, perché il percorso passa per il ramo nero.

Per come l’ho risolto io, la risposta si potrebbe trovare anche con la sola calcolatrice. Con qualche riga di codice in un linguaggio di programmazione sarebbe ancora meglio, anche se non strettamente necessario, ma non prescinderei dalla calcolatrice…

Distanza in un albero


Qual è la distanza media di due nodi diversi scelti a caso tra i 1023 di un albero binario completo?

Annunci

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: