SNS 2008/2009 problema 3

[Algebert]

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 .

[Pigkappa]

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 .

[edriv]

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"

[Pigkappa]

Non mi ricordo cos'è una radice

[edriv]

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

[mrossi]

Una soluzione per ignoranti?

[didudo]

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??)

[mrossi]

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]

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...

[didudo]

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

[mrossi]

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

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...

[didudo]

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.

[mrossi]

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]

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!

[mrossi]

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!