SNS 2008/2009 problema 3
SNS 2008/2009 problema 3
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 .
"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 .
"[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."
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 .
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 .
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.
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.
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"....
eh non riesco ene a capire questo passaggiodidudo 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
beh io potrei tranquillamente fare l'inserviente dell'inserviente...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
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"....
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"....