Labirinto

[Caradhras]

Salve, mi sono imbattuto in questo problema (il terzo di del 2008/2009 per l'ammissione alla Normale) e non ho idea di dove partire per risolverlo: qualcuno mi sa dare uno spunto?
Dato un intero n e un foglio quadrato costituito da $n^2$ quadrati di lato 1cm, 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 del labirinto è raggiungibile da ogni altro punto;
(d) ogni quadrato 2x2 contiene almeno una parete del labirinto al suo interno.
Dimostra che la lunghezza totale delle pareti non dipende dalla forma del labirinto.

[milizia96]

Prima di tutto ho fatto delle simulazioni con $n$ piccoli per prendere confidenza.
Poi ho pensato: se devo dimostrare che la lunghezza delle pareti, fissata la dimensione, è sempre la stessa, quanto deve valere? Quindi ho trovato una costruzione di labirinto che è possibile fare per ogni $n$, e ho misurato la lunghezza delle pareti.
La strategia successiva è stata togliere una alla volta le proprietà elencate per vedere cosa esse causano, cercando di capire perché la tesi non vale più.
Dopo di che non è stato difficile concludere...

[Caradhras]

Non sono sicuro che la dimostrazione sia rigorosa, ma ho pensato questo: le pareti non possono essere più di una per vertice, ovvero $(n+1)^2$, perché altrimenti ci sarebbe almeno un punto che viola il principio c. I quadrati 2x2 sono $(n-1)^2$ ($n-1$ per ogni riga e $n-1$ colonne) e, per il punto d, ognuno di essi deve avere al suo interno almeno una parete, che sommata alla superficie dei bordi (necessariamente inclusa per il punto a) dà, come numero minimo di pareti, $(n-1)^2 +4n=(n+1)^2$: da questo segue che le pareti devono essere esattamente $(n+1)^2$. Tu hai trovato una dimostrazione più rigorosa (tra l'altro mi sembra strano che non servisse il principio b)?

[xXStephXx]

le pareti non possono essere più di una per vertice

Sembra quasi filare, forse l'unica cosa sottile è questa. Il punto b) lo usi per dire implicitamente che da ogni vertice puoi raggiungere gli altri, altrimenti magari con 2 lati potresti corpire 3 vertici scollegati dal resto. (E ti cade la cosa che ad ogni vertice associ un lato).

Un'alternativa potrebbe essere questa.
Immagina di evidenziare tutti i 4 vertici di ogni quadratino 1x1 che compone il labirinto. Sicuramente ognuno di quei vertici è collegato ad altri (e di conseguenza alle mura perimetrali), altrimenti se non lo fosse il quadrato 2x2 centrato in quel vertice non avrebbe mura.

Ora immagina di fare un taglio su uno dei 4 vertici del perimetro del labirinto e di separare le estremità, sdoppiando quel vertice. Ottieni un albero con $(n+1)^2 +1$ vertici. Dove i vertici sono i punti che hai evidenziato prima e i lati le mura. Ed è un albero perchè le mura non possono chiudersi.

[Caradhras]

Ora immagina di fare un taglio su uno dei 4 vertici del perimetro del labirinto e di separare le estremità, sdoppiando quel vertice. Ottieni un albero con $(n+1)^2 +1$ vertici. Dove i vertici sono i punti che hai evidenziato prima e i lati le mura. Ed è un albero perchè le mura non possono chiudersi.

Grazie, ma non ho capito molto bene questo passaggio; aggiungendo quello che hai scritto tu comunque la mia dimostrazione è "salvabile"?

[milizia96]

Concentriamoci nel contare solo i pezzi di parete "interni", cioè non perimetrali. Tanto il perimetro è sempre lo stesso.

Considera questo insieme di oggetti:
- ogni punto che appartiene esattamente a 4 quadratini (in pratica i vertici, ma solo interni)
- il bordo.

Consideriamo gli elementi di questo insieme come nodi di un grafo.
Due nodi sono collegati da un arco se e solo se c'è un pezzo unitario di parete nel labirinto che collega i due rispettivi oggetti.
Per non violare (c) il grafo non può avere cicli.
Per non violare (b) o (d) il grafo deve essere connesso.
Quindi è un albero. Il numero di nodi dipende unicamente da $n$, quindi anche il numero di archi, che è esattamente uguale al numero di pareti nel labirinto.

Della tua dimostrazione non ho capito perché le pareti non possono essere più di una per vertice (mi sembra falso).

[Caradhras]

Grazie, adesso ho capito; per quanto riguarda la mia "dimostrazione", effettivamente era quello il punto su cui avevo più dubbi; comunque non intendevo che per ogni vertice non ci può essere più di una parete, ma che il numero complessivo di queste non può superare quello dei vertici, dato che altrimenti "da qualche parte" (ecco il punto di cui non sono riuscito a dare una dimostrazione rigorosa) delle pareti si chiuderebbero (formerebbero un ciclo).

[xXStephXx]

il numero complessivo di queste non può superare quello dei vertici, dato che altrimenti "da qualche parte" (ecco il punto di cui non sono riuscito a dare una dimostrazione rigorosa) delle pareti si chiuderebbero (formerebbero un ciclo).

Forse potresti sistemarlo quel pezzo.
Prima di tutto ad ogni lato del perimetro esterno associ il proprio vertice che trovi andando in senso orario. Mentre per ogni parete interna puoi partire dal punto in cui si stacca dalle mura (visto che tutte le pareti partono dalle mura) e ci associ il proprio vertice che non appartiene alle mura. Dopodichè segui il cammino lungo quella parete associando ad ogni lato l'unico suo vertice che puoi associare (visto che uno dei due (quello più vicino alle mura) è sempre stato già assegnato). Se ad un certo punto raggiungi un lato dove anche l'altro vertice è già stato assegnato, vuol dire che da quel vertice passava pure un'altra parete diversa da quella che stavi percorrendo e che le due pareti si toccano. Inevitabilmente dalla nuova parete puoi raggiungere le mura seguendo un percorso diverso da quello da cui sei partito e completare un ciclo, ma non ci sono clici, quindi hai che il numero di lati è sicuramente minore o uguale di quello dei vertici.
Per dimostrare che è uguale devi aggiungere che se ad un vertice non è associato nessun lato vuol dire che i 4 lati che lo contengono non hanno mura e che è assurdo per le ipotesi.

[Caradhras]

Ho capito, grazie