Sequenze di Livello di Labirinti di Transito Semplici Alternati.

 

Sequenze di Livello di Labirinti di Transito Semplici e 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 (labirinto t.s.a) è completamente determinata dalla sua sequenza di livelli. Come funziona è spiegato di seguito; significa che se due labirintit.s.a. (diciamo, entrambi in forma srotolata) hanno la stessa sequenza di livello, allora uno può essere modificato in modo che corrisponda all'altro, o l'immagine speculare dell'altro,con una deformazione continuache preserva i livelli.

Ne consegue che una classificazione topologica completa di labirinti di transito semplici e 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 la sequenza di livelli di un labirinto t.s.a. 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; queste 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; queste 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 livelli di un labirintot.s.a.

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 allora 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 un livello dispari. In seguito attraversa a sinistra e passa al livello successivo nella sequenza, che sarà pari, dopo di che incrocia nuovamente verso destra, ecc. Quindi le coppie di numeri consecutivi nella sequenza di livello che iniziano con un numero pari corrispondono a segmenti verticali 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 potrebbero 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 di 3: Supponiamo di avere una permutazione degli interi da 0 a n, soddisfacendo le condizioni 1, 2 e 3. Ecco come trasformarla 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. Collega le due lungo quella riga; questo procedimento lascierà una estremità libera in alto e una in basso. Avrai disegnato il filo di Arianna della forma srotolata del labirintot.s.a. 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 destro e sinistro della pagina, e unendo questi due pezzi insieme lungo le loro spine esterne, produrrai il nucleo da cui può essere disegnata la forma arrotolata.

Torna alla Home Page di Tony


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

Steampunkify Your Inbox!

Get on the list to receive the latest steampunk news and exclusive offers!