Curse of the Labyrinth

[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.

[Vinci]

Ma questo è un vecchio SNS?

[Lasker]

dunque? Questo è carino lo stesso.

[Vinci]

dunque? Questo è carino lo stesso.

Sisi, è un bellissimo problema, mi sembrava di aver già provato a farlo, tutto qui

[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.

[Sirio]

Giusto per sapere: qualcuno l'ha fatto in altri modi?

[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.

[Lasker]

Giusto per sapere: qualcuno l'ha fatto in altri modi?

Io avevo fatto esattamente come te