Curse of the Labyrinth

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Curse of the Labyrinth

Messaggio 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.
"If only I could be so grossly incandescent!"
Vinci
Messaggi: 159
Iscritto il: 30 gen 2015, 18:38

Re: Curse of the Labyrinth

Messaggio da Vinci »

Ma questo è un vecchio SNS?
Avatar utente
Lasker
Messaggi: 440
Iscritto il: 02 mag 2013, 20:47
Località: Udine

Re: Curse of the Labyrinth

Messaggio da Lasker »

dunque? Questo è carino lo stesso.
"Una funzione generatrice è una corda da bucato usata per appendervi una successione numerica per metterla in mostra" (Herbert Wilf)

"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)

Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?

PRIMA FILA TUTTI SBIRRI!
Vinci
Messaggi: 159
Iscritto il: 30 gen 2015, 18:38

Re: Curse of the Labyrinth

Messaggio 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
Avatar utente
Sirio
Messaggi: 317
Iscritto il: 08 set 2016, 22:01

Re: Curse of the Labyrinth

Messaggio 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.
$T=\sqrt{\dfrac l g 12\pi}$
Avatar utente
Sirio
Messaggi: 317
Iscritto il: 08 set 2016, 22:01

Re: Curse of the Labyrinth

Messaggio da Sirio »

Giusto per sapere: qualcuno l'ha fatto in altri modi?
$T=\sqrt{\dfrac l g 12\pi}$
Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Re: Curse of the Labyrinth

Messaggio 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.
"If only I could be so grossly incandescent!"
Avatar utente
Lasker
Messaggi: 440
Iscritto il: 02 mag 2013, 20:47
Località: Udine

Re: Curse of the Labyrinth

Messaggio da Lasker »

Sirio ha scritto:Giusto per sapere: qualcuno l'ha fatto in altri modi?
Io avevo fatto esattamente come te
"Una funzione generatrice è una corda da bucato usata per appendervi una successione numerica per metterla in mostra" (Herbert Wilf)

"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)

Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?

PRIMA FILA TUTTI SBIRRI!
Rispondi