OliForum Matematico

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 .

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 .

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"

Non mi ricordo cos'è una radice

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

Una soluzione per ignoranti?

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

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.

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

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

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

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.

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?

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!

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!