Pagina 1 di 1

Curse of the Labyrinth

Inviato: 01 feb 2018, 16:19
da Gerald Lambeau
Dato un intero $n$ e un foglio quadrato costituito da $n^2$ quadrati di lato $1$, considera un “labirinto” con le seguenti proprietà:
(a) le pareti del labirinto sono costituite da lati dei quadrati e contengono il bordo del foglio;
(b) partendo da qualsiasi punto su una parete del labirinto si può sempre arrivare, muovendosi lungo le pareti del labirinto, al bordo del foglio;
(c) ogni punto (qui si intende le caselle) del labirinto è raggiungibile da ogni altro punto;
(d) ogni quadrato $2 \times 2$ contiene almeno una parete del labirinto al suo interno.
Dimostra che la lunghezza totale delle pareti non dipende dalla forma del labirinto.

Re: Curse of the Labyrinth

Inviato: 14 feb 2018, 18:59
da Vinci
Ma questo è un vecchio SNS?

Re: Curse of the Labyrinth

Inviato: 14 feb 2018, 20:53
da Lasker
dunque? Questo è carino lo stesso.

Re: Curse of the Labyrinth

Inviato: 14 feb 2018, 20:57
da Vinci
Lasker ha scritto:
14 feb 2018, 20:53
dunque? Questo è carino lo stesso.
Sisi, è un bellissimo problema, mi sembrava di aver già provato a farlo, tutto qui

Re: Curse of the Labyrinth

Inviato: 17 feb 2018, 10:44
da Sirio
Testo nascosto:
Consideriamo il grafo che ha per vertici tutti i punti che sono vertici di uno dei quadratini e tale che due vertici sono collegati da uno spigolo se e solo se quei due vertici sono consecutivi nel labirinto e sono direttamente collegati da un muro. Tale grafo ha quindi $\left(n+1\right)^2$ vertici. Per la (d) e per la (b), questo grafo è connesso: vale perciò, se il grafo è piano, quella formula che si chiama formula di Eulero, ma che ho memorizzato come "fatti vedere sabato alle 2", come era scritto sulla maglietta di uno che purtroppo non ricordo chi fosse al TF del 2016. Si ha perciò, ricordando quanti sono i vertici, $S=F+\left(n+1\right)^2-2$. Ora, tale grafo è sicuramente piano, perché ammette esattamente un ciclo (quello formato da tutti i muri del bordo). Se per assurdo ne ammettesse altri, violeremmo la (c). Inoltre, dal fatto che c'è un solo ciclo, abbiamo $F=2$, perciò $S=\left(n+1\right)^2$. Evidentemente $S$ dipende solo da $n$, c.v.d.

Re: Curse of the Labyrinth

Inviato: 20 feb 2018, 07:25
da Sirio
Giusto per sapere: qualcuno l'ha fatto in altri modi?

Re: Curse of the Labyrinth

Inviato: 20 feb 2018, 15:19
da Gerald Lambeau
Allora, intanto è giusta, poi un altro metodo è dimostrare che il grafo che ha come vertici le stanze, le quali sono collegate da un arco sse sono adiacenti e non c'è un muro, è un albero.

Re: Curse of the Labyrinth

Inviato: 20 feb 2018, 15:59
da Lasker
Sirio ha scritto:Giusto per sapere: qualcuno l'ha fatto in altri modi?
Io avevo fatto esattamente come te