Curse of the Labyrinth

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Gerald Lambeau
Messaggi: 308
Iscritto il: 17 mag 2015, 13:32

Curse of the Labyrinth

Messaggio da Gerald Lambeau » 01 feb 2018, 16:19

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.
"Non ho rispetto per i miei superiori, figurati se ho rispetto per i miei pari: il rispetto di un uomo lo merita solo chi è a lui inferiore."
Cit. Marco (mio vero nome)

The Game.

Ci sono cose che non si possono confutare; per tutto il resto, c'è la fisica.

Vinci
Messaggi: 153
Iscritto il: 30 gen 2015, 18:38

Re: Curse of the Labyrinth

Messaggio da Vinci » 14 feb 2018, 18:59

Ma questo è un vecchio SNS?

Avatar utente
Lasker
Messaggi: 408
Iscritto il: 02 mag 2013, 20:47
Località: Udine

Re: Curse of the Labyrinth

Messaggio da Lasker » 14 feb 2018, 20:53

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: 153
Iscritto il: 30 gen 2015, 18:38

Re: Curse of the Labyrinth

Messaggio da Vinci » 14 feb 2018, 20:57

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: 268
Iscritto il: 08 set 2016, 22:01

Re: Curse of the Labyrinth

Messaggio da Sirio » 17 feb 2018, 10:44

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}$
"Sirio Passirio" cit. Nicola S.

Avatar utente
Sirio
Messaggi: 268
Iscritto il: 08 set 2016, 22:01

Re: Curse of the Labyrinth

Messaggio da Sirio » 20 feb 2018, 07:25

Giusto per sapere: qualcuno l'ha fatto in altri modi?
シリオ
$T=\sqrt{\dfrac l g 12\pi}$
"Sirio Passirio" cit. Nicola S.

Gerald Lambeau
Messaggi: 308
Iscritto il: 17 mag 2015, 13:32

Re: Curse of the Labyrinth

Messaggio da Gerald Lambeau » 20 feb 2018, 15:19

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.
"Non ho rispetto per i miei superiori, figurati se ho rispetto per i miei pari: il rispetto di un uomo lo merita solo chi è a lui inferiore."
Cit. Marco (mio vero nome)

The Game.

Ci sono cose che non si possono confutare; per tutto il resto, c'è la fisica.

Avatar utente
Lasker
Messaggi: 408
Iscritto il: 02 mag 2013, 20:47
Località: Udine

Re: Curse of the Labyrinth

Messaggio da Lasker » 20 feb 2018, 15:59

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