sabato 28 gennaio 2012

96. Labirinti

Wikipedia definisce labirinto una struttura, solitamente di vaste dimensioni, costruita in modo tale che risulti difficile per chi vi entra trovare l'uscita.
In Inghilterra il più popolare dei labirinti da giardino fatto di alte siepi fu progettato nel 1690 per il Palazzo di Hampton Court vicino a Londra.



Da un punto di vista matematico un labirinto e’ un problema di topologia. Anche se il foglio viene deformato il percorso non cambia, cioè e’ un invariante topologico.
Se esiste un solo ingresso e lo scopo e’ di trovare la via d’uscita, la cosa può essere risolta tenendo il dito a contatto con la parete destra mentre si cammina. Anche se il percorso non sarà sempre il più breve, si arriverà sempre all’uscita. Nel caso in cui la meta si trovi all’interno del labirinto, vale lo stesso discorso, purché non vi sia un percorso lungo il quale si possa girare intorno alla meta e tornare al punto di partenza.
L'algoritmo di Tremaux consiste nel seguire un percorso scelto a caso fino a raggiungere un incrocio, marcando la via che è stata percorsa fino a quel momento (nel caso in cui il corridoio conduca a un vicolo cieco, è necessario tornare indietro fino all'incrocio precedente, marcando la via all'andata e al ritorno). A ogni incrocio  si prende preferibilmente un corridoio non segnato come percorso in precedenza, e se ciò non è possibile, si prende una via percorsa una sola volta. In ogni caso non è permesso scegliere una via che è stata già marcata due volte. Iterando il procedimento per ogni incrocio che si trova sul proprio percorso, l'algoritmo permette di raggiungere l'uscita (o se il labirinto non ha altre uscite oltre a quella imboccata per entrare, di tornare all'entrata).

Ma quanto è lungo un labirinto?  Se per comodità di calcolo lo pensiamo con corridoi larghi un metro e se ricoprisse l’area di un campo di calcio ( 105 x 68 = 7140 metri2 ) avrebbe un’estensione lineare di 7,14 km, mentre con un'area equivalente ad una città come Milano (superficie 181 km2 = 181.000.000 m2 ) sarebbe lungo 181.000 km, più di 4 volte la misura dell’equatore terrestre.

Infine la superficie della Terra ( 5,1 x 1014 m2 ) e’ per il 70,8% coperta da acqua, mentre il rimanente 29,2% emerso consiste di montagne, deserti, pianure e altipiani.
Un labirinto che ricoprisse il 10% della superficie terrestre si estenderebbe per 340 Unità Astronomiche (UA), cioè indicativamente una decina di volte la distanza da percorrere per raggiungere Plutone.

http://utenti.quipo.it/base5/combinatoria/labirinti.htm

Martin Gardner, Enigmi e giochi matematici, Vol. II, Sansoni, 1973
.
Abstract -  Labyrinth: how to exit from it.
.

Nessun commento:

Posta un commento