OliForum Matematico

Dimostrazione definitiva e ben scritta di questo benedetto problema:
<BR>siano:
<BR>s=numero di spostamenti
<BR>x=numero di prigionieri che si sono spostati
<BR>p=perimetro dell\'insiem di celle con almeno un muro rinforzato
<BR>dalle ipotesi del problema seguono direttamente queste proposizioni:
<BR>(i) ogni prigioniero neccesita di almeno 4 spostamenti per tornare alla posizione inziale sse si muove
<BR>(ii) ad ogni spostamento si muovono 2 prigionieri
<BR>(iii) se un muro viene fortificato significa che entrambi i prigionieri delle celle che avevano questo muro in comune si sono spostati
<BR>(iv) ogni stanza ha 4 pareti
<BR>(v) ogni insieme non vuoto di celle possiede un perimetro esterno maggiore di 0
<BR>
<BR>ora, se tutti i prigionieri sono nella posizione iniziale ne consegue che:
<BR>dalla (iii) e dalla (iv) sappiamo che il numero massimo di pareti attraversate equivale a ((4*x)-p)/2) che nel momento in cui x=\\0 è strettamente minore di 2x (p=\\0 per la (v))
<BR>dalla (i) e dalla (ii) ricaviamo che il numero totale di spostamenti è maggiore o uguale di (4*x)/2
<BR>dunque si ha che 2x<=s<2x per ogni x=\\0 ; ciò è chiaramente impossibile quindi x deve valere 0 e perciò se tutti i prigionieri sono al loro posto iniziale significa che nessuno s\'è mosso.
<BR>
<BR>PS: non ho mai speso cosi tanto tempo dietro un problema dopo aver avuto chiara la soluzione (e che voi ci crediate o no ce l\'ho chiara dal mio secondo post); ma è anche vero che non ho mai scritto una soluzione cosi poco male quindi ringrazio MindFlyer e marco per avermi portato a questo
<BR>PPS: se c\'è ancora qualcosa che non torna faccio quello che fece mio nonno... <IMG SRC="images/forum/icons/icon_razz.gif">

No. Ora torna perfettamente.

Notate che con un leggero ritocco si risolve anche il caso più generale in cui in ogni cella c\'è un numero qualsiasi di prigionieri (anche nessuno).
<BR>Marco, insisto io perché tu pubblichi la tua soluzione.

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-11-30 13:41, MASSO wrote:
<BR>il numero massimo di spostamenti che si possono verificare è uguale al numero di pareti cioè 2*n*(n-1)
<BR>[...]
<BR>ma dunque gli spostamenti totali sono stati al più 2*n*(n-1)/2 ....... Da qui discesa infinita e l\'assurdo che almeno uno sia sia mosso.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Soltanto per la cronaca e per fugare gli ultimi dubbi, volevo spiegare meglio il motivo per cui qui non vale la discesa infinita. Il fatto è che si dimostra solo che si può passare da un numero della forma 2n(n-1) a n(n-1) che, effettivamente, sotto certe ipotesi è più piccolo. Ma da qui non è chiaro come si possa andare avanti, perché n(n-1) non è più necessariamente nella forma 2n\'(n\'-1). Inoltre, anche esaminando il ragionamento che passa da 2n(n-1) a n(n-1), si vede che le quantità di \"partenza\" e di \"arrivo\" sono entrambe intere, dunque si capisce bene che lo stesso argomento non può funzionare fin dove si vuole, ma solo fino ad esaurimento dei fattori 2 in n(n-1).

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-12-02 15:09, MindFlyer wrote:
<BR>Marco, insisto io perché tu pubblichi la tua soluzione.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Ciao. Beh, allora, a grande richiesta...
<BR>
<BR>--------
<BR>[questa dimo è tratta da un carteggio privato tra me e MindFlyer, nata indipendentemente dai messaggi di questo filo. Come vedrete, l\'idea è identica a quella di Masso]
<BR>
<BR><!-- BBCode Start --><B>Lemma dei Muri:</B><!-- BBCode End --> Sia A un insieme di N celle. Se celle contigue di A sono divise da almeno 2N muri, allora A è vuoto.
<BR>
<BR>Dim.: Assegno ogni muro in direzione Est-Ovest alla cella a Nord e ogni muro ortogonale alla cella a Ovest. Ogni cella può avere al massimo due muri assegnati. I muri sono almeno due per cella, quindi sono esattamente due per cella. Ma allora anche la cella più a Est (o Sud, se preferisci...), qualora esista, ha un muro assegnato che la divide da un\'altra cella di A a Est o Sud. Ma allora non era quella estrema, e quindi non può esistere tale cella. Quindi A (che è finito) è vuoto. []
<BR>
<BR>Dim. del problema: Sia A l\'insieme delle celle con prigionieri che si sono spostati. Sia N la sua cardinalità. Il percorso chiuso più breve che non ripassa dallo stesso muro è lungo 4 passi e quindi il numero totale dei passi è almeno 4N. Ogni mossa muove di un passo due prigionieri, quindi il percorso è fatto da almeno 2N mosse e quindi individuo almeno 2N muri tra celle contigue di A. Applico il Lemma dei Muri e ho fatto. []
<BR>--------
<BR>
<BR>A margine aggiungo:
<BR>
<BR><!-- BBCode Start --><B>Lemma dei Muri:</B><!-- BBCode End --> Sia A un insieme di N celle. Se celle contigue di A sono divise da almeno 2N muri, allora A è vuoto.
<BR>
<BR>Dim. con l\'idea di Masso: Sia P il numero di muri perimetrali e I il numero di muri interni. Contando i muri di tutte le celle di A, conto una volta i muri perimetrali e due volte i muri interni. Allora 4N = P + 2I >= P + 4N, quindi P=0, quindi A è vuoto. []
<BR>(anche meglio della mia...)
<BR>
<BR>Morale: per essere rigorosi non è né necessario, né sufficiente essere anche formali.
<BR>
<BR>Ad ogni modo: un bravo a Masso per la soluzione, e un bravino a Boll per averci provato.
<BR>
<BR>Ciao. M.<BR><BR>[ Questo Messaggio è stato Modificato da: marco il 02-12-2004 16:44 ]