SNS 2008/2009 problema 3

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Avatar utente
Algebert
Messaggi: 330
Iscritto il: 31 lug 2008, 20:09
Località: Carrara
Contatta:

SNS 2008/2009 problema 3

Messaggio da Algebert » 03 set 2008, 17:49

Allora vediamo se riesco a ricordarmelo bene:

"Abbiamo un foglio quadrato di lato $ $n$ $, con $ $n$ $ intero positivo. Suddividiamolo in quadratini di lato uguale a $ $1\ \textrm{cm} $. Costruiamo poi un "labirinto" con le seguenti proprietà:
- le pareti del labirinto contengono il bordo del foglio e sono costituite dai lati dei quadrati più piccoli;
- muovendosi sulle pareti di tale labirinto è sempre possibile raggiungere il bordo del foglio;
- ciascun punto del labirinto è raggiungibile da ogni altro punto;
- ogni quadrato 2 X 2 interno al foglio quadrato contenga almeno una parete del labirinto.
Dimostrare che se il labirinto soddisfa le condizioni sopra date, allora la sua lunghezza è indipendente dalla sua forma."


Chi ha la memoria più lunga della mia per favore mi corregga se ho sbagliato e/o dimenticato qualcosa, così provvedo subito :P .
"[i]What is a good Olympiad problem?[/i] Its solution should not require any prerequisites except cleverness. A high scool student should not be at a disadvantage compared to a professional mathematician."

Pigkappa
Messaggi: 1208
Iscritto il: 24 feb 2005, 13:31
Località: Carrara, Pisa

Messaggio da Pigkappa » 03 set 2008, 21:06

La mia dimostrazione (spiegata malissimo in gara =_=) è sostanzialmente questa:

Un albero con $ \displaystyle n $ vertici ha esattamente $ \displaystyle n-1 $ archi.

Questo si dimostra facilmente per induzione (all'indietro). Lascio a voi di costruire quello che manca intorno alla mia frase per risolvere il problema :wink: .

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 03 set 2008, 21:40

Pigkappa ha scritto:
Questo si dimostra facilmente per induzione (all'indietro).
All'indietro o avanti così è brutta... propenderei per un "scelgo una radice, e ad ogni vertice diverso dalla radice associo il primo arco dell' (unico) percorso che lo collega alla radice" :wink:

Pigkappa
Messaggi: 1208
Iscritto il: 24 feb 2005, 13:31
Località: Carrara, Pisa

Messaggio da Pigkappa » 04 set 2008, 00:54

Non mi ricordo cos'è una radice :oops:

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 04 set 2008, 12:16

In quel contesto significa un nodo a caso... non è poi così complicato :lol:

mrossi
Messaggi: 58
Iscritto il: 31 lug 2009, 16:07

Messaggio da mrossi » 25 ago 2009, 16:44

:shock:
Una soluzione per ignoranti? :D

didudo
Messaggi: 123
Iscritto il: 22 mag 2009, 10:45
Località: pisa

Messaggio da didudo » 25 ago 2009, 17:06

non capisco bene quel "ogni quadrato 2 X 2 interno al foglio quadrato contenga almeno una parete del labirinto" ( si intende almeno 1 su 4 tratti di parete o su 12??)
pensavo fosse il forum "belli e abbronzati"....

mrossi
Messaggi: 58
Iscritto il: 31 lug 2009, 16:07

Messaggio da mrossi » 25 ago 2009, 17:17

Penso che sia nei 4 tratti interni, altrimenti esistono dei controesempi alla tesi.

Ho pensato, non sapendo praticamente niente di teoria dei grafi alberi ecc, che si può dire che il numero massimo di tratti è $ (n-1)^2 $ altrimenti cadrebbe la terza ipotesi (non ho trovato un modo esattamente rigoroso di dimostrarlo però...).
Quindi si può dimostrare che il numero minimo di pareti è proprio $ (n-1)^2 $ (che viene facendo alcune prove con n = 2,3,4) sfruttando la proprietà dei quadrati 2x2.

didudo
Messaggi: 123
Iscritto il: 22 mag 2009, 10:45
Località: pisa

Messaggio da didudo » 25 ago 2009, 17:24

beh,supponiamo che si intenda che ogni "+" all'interno di un quadratino 2X2 debba contenere almeno una parete.questo equivale a dire che ogni punto è raggiunto da almeno un segmeno.inoltre non esistono percorsi chiusi (tranne ovviamente quello esterno)e se pensiamo di togliere un tratto unitario della parete esterna esiste uno e un solo percorso sulle pareti che congiunge due punti qualsiasi del labirinto.quindi quello creato è un albero con$ (n+1)^2 $ vertici e che per induzione si dimostra avere esattamente $ n^2+2n $ archi,a cui si aggiunge quello he abbiamo tolto,in tutto $ (n+1)^2 $ pareti,indipendentemente dalla loro disposizione.basta giustificare un'attimo la parte in cui demoliamo una parete e la dimostrazione dovrbbe essere giusta...
pensavo fosse il forum "belli e abbronzati"....

didudo
Messaggi: 123
Iscritto il: 22 mag 2009, 10:45
Località: pisa

Messaggio da didudo » 25 ago 2009, 17:34

non so se va bene mrossi,non devi dare retta a me,io qui ho più o meno il ruolo dell'inserviente di scrubs,potrei benissimo aver detto un sacco di schifezze
pensavo fosse il forum "belli e abbronzati"....

mrossi
Messaggi: 58
Iscritto il: 31 lug 2009, 16:07

Messaggio da mrossi » 25 ago 2009, 17:44

didudo ha scritto: se pensiamo di togliere un tratto unitario della parete esterna esiste uno e un solo percorso sulle pareti che congiunge due punti qualsiasi del labirinto.quindi quello creato è un albero con$ (n+1)^2 $ vertici
eh non riesco ene a capire questo passaggio
didudo ha scritto:non so se va bene mrossi,non devi dare retta a me,io qui ho più o meno il ruolo dell'inserviente di scrubs,potrei benissimo aver detto un sacco di schifezze
beh io potrei tranquillamente fare l'inserviente dell'inserviente... :D

didudo
Messaggi: 123
Iscritto il: 22 mag 2009, 10:45
Località: pisa

Messaggio da didudo » 25 ago 2009, 17:53

in pratica in un labirinto che soddisfa non puoi avere "percorsi chiusi" cioè parti del labirinto racchiuse da una linea chiusa,altrimenti i punti interni ad esso non sarebbero raggiungibili.quindi puoi sempre trovare 2 percorsi distinti che da unqualunque punto vadano ad un qualunque altro (percorsi "sopra" i muri,non so se mi intendo),ma se togli un segmento unitario del bordo esterno avrai uo e un solo percorso che congiunge 2 punti qualunque,perchè l'alternativa prima era data dal fatto che il bordo esterno è una line chiusa.quindi ti ritrovi con un grafo minimale,cioè un albero,in cui puoi raggiungere ogni punto ma solo con un percorso,e perciò avrai k-1 archi con k vertici.
pensavo fosse il forum "belli e abbronzati"....

mrossi
Messaggi: 58
Iscritto il: 31 lug 2009, 16:07

Messaggio da mrossi » 25 ago 2009, 17:56

ok adesso è chiaro, però non avendo particolari nozioni di teoria dei grafi che mi sembra inutile imparare a 2 giorni dalla prova, non avrei potuto ragionare così. Esiste un altro tipo di dimostrazione?

didudo
Messaggi: 123
Iscritto il: 22 mag 2009, 10:45
Località: pisa

Messaggio da didudo » 25 ago 2009, 18:12

io non ho alcuna nozione di teoria dei grafi,ma per induzione si vede bene che è così,infatti un albero a 2 vertici ha di certo 1 solo segmento che li congiunge,supponiamo he questo valga per n vertici:l'n+1 esimo vertice deve necessariamente essere connesso ad un solo vertice (se fosse connesso a più vertici avremmo più percorsi possibili,e questo non lo vogliamo),perciò aggiungiamo un solo segmeno.beh,cmq siamo sulla stessa barca,gli utlimi 20 giorni li ho passati a studiarmi da zero l'halliday senza toccare mate e tutto ciò che so di elettromagnetismo e ottica lo so da una decina di giorni,puoi immaginarti come andrà il mio test.in effetti un po' mi rompe che informatici,fisici e matematici facciano tutti lo stesso test,ma contando che i corsi che si seguono alla normale includono sia mate che fis ha senso.cmq mi sa che ci vedremo presto allora,io sarò quello col cappellino a fiori!
pensavo fosse il forum "belli e abbronzati"....

mrossi
Messaggi: 58
Iscritto il: 31 lug 2009, 16:07

Messaggio da mrossi » 26 ago 2009, 09:03

OK, grazie mille per la spiegazione... Niente allora mi sa che ci vediamo domani in quel di Pisa. Cercherò uno con il cappellino a fiori! :D

Rispondi