Original page: http://www.math.stonybrook.edu/~tony/mazes/levelseq.html
Sokkeloiden kautta matematiikkaan
Perusfakta, joka mahdollistaa yksinkertaisten, vuorottelevien kauttakulkusokkeloiden matemaattisen tutkimuksen, on seuraava. Yksinkertaisen, vuorottelevan kauttakulkulabyrintin topologia määräytyy täysin sen tasosekvenssin perusteella. Miten tämä toimii, selitetään alla; se tarkoittaa, että jos kahdella istuvalla sokkelolla (esimerkiksi molemmilla aukirullatussa muodossa) on sama tasosekvenssi, niin toinen voidaan muuttaa vastaamaan toista tai toisen peilikuvaa jatkuvalla, tasoa säilyttävällä muodonmuutoksella.
Tästä seuraa, että yksinkertaisten vuorottelevien kulkusokkeloiden täydellinen topologinen luokittelu merkitsee sen määrittämistä, mitkä numerosarjat voivat esiintyä tasojonoina, ja itse asiassa on olemassa kolme ehtoa, jotka ovat välttämättömiä ja riittäviä, jotta lukujen permutaatio 0 sta n ään on syvyyden n istutun sokkelon tasosekvenssi.
1. Jakson tulee alkaa 0 lla ja päättyä n ään.
2. Parittomat ja parilliset kokonaisluvut on vaihdettava järjestyksessä.
3. Tarkastellaan tasojonon peräkkäisten lukujen pareja, jotka alkavat parillisella luvulla; nämä vastaavat sokkelon oikealla puolella olevia pystysuoria segmenttejä. (*)Jos kaksi näistä segmenteistä on päällekkäin, toisen on oltava sisäkkäin toisen sisällä. Sama on pätevä parittomalla numerolla alkaviin pareihin; nämä vastaavat pystysuuntaisia polun segmenttejä vasemmalla.
Esimerkki: Konstantinopolin sokkelon tasosekvenssissä segmentit (10,1) ja (2,11) menevät päällekkäin, mutta kumpikaan ei ole sisäkkäin toisessa; joten tämä ei voi olla sat-labyrintin tasosekvenssi.
Näin tämä todistetaan.
Tarve 1: ilmeinen.
Tarve 2: Oletetaan, että kahdella peräkkäisellä kerroksella, jotka on yhdistetty pystysuoralla segmentillä oikealla, on esimerkiksi sama pariteetti; niiden välisessä tilassa on oltava pariton määrä tasoja. Kaikkien polkujen, jotka kulkevat avaruuden läpi, on mentävä ja poistuttava vasemmalta, joten ne voivat käyttää vain parillisen määrän tasoja. Ristiriita.
Tarve 3: Ajattele sokkeloa aukirullatussa muodossa, jossa sisäänkäynti on esimerkiksi oikealla. Polku alkaa oikealta puolelta tasolta 0 ja putoaa jollekin parittomalle tasolle. Sitten se ylittää vasemmalle ja siirtyy seuraavalle tasolle sarjassa, joka on parillinen, sitten risti takaisin oikealle jne. Joten parillisella numerolla alkavat peräkkäisten numeroiden parit vastaavat pystysuoraa segmentit sokkelon oikealla puolella ja ne, jotka alkavat parittomalla numerolla, vasemmalla puolella oleviin segmentteihin. Harkitse nyt mitä tahansa kahta pystysuuntaista polun segmenttiä oikealla. Jos ne menevät päällekkäin, toinen on upotettava toisen sisään. Muuten niitä molempia ei voitaisi yhdistää vasemmalle puolelle vaakasuorilla segmenteillä, koska sokkelopolku ei voi leikkaa itseään; ja saman on pädettävä vasemmalla oleviin pystysuoraan polun segmentteihin.
Riittävyys: Oletetaan, että kokonaislukujen permutaatio 0:sta n:ään täyttää ehdot 1, 2 ja 3. Näin siitä tehdään sokkelo. Numeroi viivalle paperille rivit 0 sta n ään alkaen ylhäältä. Yhdistä kunkin peräkkäisen kokonaislukuparin kohdalla parillisella numerolla alkavassa järjestyksessä vastaavasti numeroidut rivit pystysegmentillä sivun oikealla puolella. Jos kaksi näistä segmenteistä on sisäkkäisiä, piirrä lyhyempi vasemmalle pidemmän puolelle. Tee nyt sama parittoman alkuparin kanssa, paitsi vasemmalla puolella, ja lyhyemmät segmentit sijoitetaan oikealle. Nyt kullakin rivillä numeroitu 1,…,n-1 on kuvion kaksi vapaata päätä. Liity heihin tällä linjalla; tämä jättää vapaan pään ylä-ja alaosaan. Olet piirtänyt Ariadnen langan sa:n aukirullatusta muodosta t sokkelo, joka vastaa aloittamaasi tasosekvenssiä. Nyt on helppo piirtää itse sokkelo. Lisäksi vain piirrä se osa sokkelosta sivun oikealle ja vasemmalle reunalle ja yhdistä nämä kaksi kappaletta toisiinsa piikkien ulkopuolella tuottaa ytimen, josta rullattu muoto voidaan vetää.
Tony Phillips
5. kesäkuuta 2018