Free Worldwide Shipping On All Orders Over $35!

Sequenze di Livello di Semplici Labirinti di Transito Alternati.

 

Sequenze di Livello di Semplici Labirinti di Transito Alternati.


Il fatto fondamentale che consente lo studio matematico di labirinti di transito semplici alternati è il seguente. La topologia di un labirinto di transito semplice e alternato è completamente determinata dalla sua sequenza di livelli. Come funziona è spiegato di seguito; significa che se due s.l.t. alternati (diciamo, entrambi in forma srotolata) hanno la stessa sequenza di livello, quindi uno può essere modificato in modo che corrisponda all'altro, o l'immagine speculare dell'altro, con una deformazione continua, che preserva il livello.
Ne consegue che una classificazione topologica completa di semplici labirinti di transito alternati equivale a determinare quali sequenze di numeri possono verificarsi come sequenze di livelli, e infatti ci sono tre condizioni che sono necessarie e sufficienti per una permutazione dei numeri da 0 a n per essere il livello di sequenza di un s.l.t alternato di profondità n.

1. La sequenza deve iniziare con 0 e terminare con n.
2. Gli interi dispari e pari devono alternarsi nella sequenza.
3. Considera le coppie di numeri consecutivi nella sequenza di livello che iniziano con un numero pari; questi corrispondono ai segmenti verticali sul lato destro del labirinto. (*) Se due di questi segmenti si sovrappongono, uno deve essere annidato all'interno dell'altro. Lo stesso deve valere per le coppie che iniziano con un numero dispari; questi corrispondono ai segmenti del percorso verticale sulla sinistra.

Esempio: nella sequenza di livelli per il labirinto di Costantinopoli, i segmenti (10,1) e (2,11) si sovrappongono, ma nessuno dei due è annidato nell'altro; quindi questa non può essere la sequenza di livello di un s.l.t alternato.

Ecco come è dimostrato.
Necessità di 1: ovvio.
Necessità di 2: Supponiamo che due strati consecutivi uniti da un segmento verticale a destra, diciamo, abbiano la stessa parità; lo spazio tra loro deve avere un numero dispari di livelli. Qualsiasi percorso che attraversa quello spazio deve entrare ed uscire a sinistra, e quindi può utilizzare solo un numero pari di livelli. Contraddizione.
Necessità di 3: Pensa al labirinto in forma srotolata, con ingresso, diciamo, a destra. Il percorso inizia sul lato destro al livello 0 e scende ad alcuni livelli dispari. Quindi attraversa a sinistra e passa al livello successivo nella sequenza, che sarà pari, quindi incrocia nuovamente verso destra, ecc. Quindi le coppie di numeri consecutivi nella sequenza di livello che iniziano con un numero pari corrispondono alla verticale segmenti sul lato destro del labirinto e quelli che iniziano con un numero dispari, a segmenti a sinistra. Considera ora due dei segmenti del percorso verticale sulla destra. Se si sovrappongono, uno deve essere annidato all'interno dell'altro. Altrimenti non potevano essere entrambi collegati al lato sinistro da segmenti orizzontali, poiché il labirinto non può intersecare se stesso; e lo stesso deve valere per i segmenti del percorso verticale sulla sinistra.

Sufficienza: Supponiamo di avere una permutazione degli interi da 0 a n, soddisfacendo le condizioni 1, 2 e 3. Ecco come trasformarlo in un labirinto. Su un foglio di carta a righe, numera le linee da 0 a n, iniziando in alto. Per ciascuna delle coppie consecutive di numeri interi nella sequenza che inizia con un numero pari, unisci le linee numerate in corrispondenza con un segmento verticale sul lato destro della pagina. Se due di questi segmenti sono nidificati, disegnare quello più corto a sinistra del più lungo. Ora fai lo stesso con le coppie di inizio dispari, tranne sul lato sinistro, con i segmenti più corti posizionati a destra. Ora su ciascuna delle righe numerate 1, ..., n-1 ci saranno due estremità libere della figura. Unisciti a loro lungo quella linea; questo lascia una fine libera in alto e in basso. Avrai disegnato il filo di Arianna della forma srotolata del s.l.t alternato corrispondente alla sequenza di livelli con cui hai iniziato. Ora è facile disegnare il labirinto stesso. Inoltre, solo disegnando quella parte del labirinto vicino ai bordi della pagina destra e sinistra, e unendo questi due pezzi insieme lungo le loro spine esterne, produce il nucleo da cui può essere disegnata la forma arrotolata.

Torna alla Pagina Principale del Labirinto

Torna alla Home Page di Tony


Tony Phillips
Dipartimento di matematica SUNY Stony Brook
tony a math.stonybrook.edu
18 novembre 2016