[C] I prigionieri di Gabriel Carroll

MASSO · Messaggio da **MASSO** » 01 gen 1970, 01:33

Dimostrazione definitiva e ben scritta di questo benedetto problema:
 siano:
 s=numero di spostamenti
 x=numero di prigionieri che si sono spostati
 p=perimetro dell\'insiem di celle con almeno un muro rinforzato
 dalle ipotesi del problema seguono direttamente queste proposizioni:
 (i) ogni prigioniero neccesita di almeno 4 spostamenti per tornare alla posizione inziale sse si muove
 (ii) ad ogni spostamento si muovono 2 prigionieri
 (iii) se un muro viene fortificato significa che entrambi i prigionieri delle celle che avevano questo muro in comune si sono spostati
 (iv) ogni stanza ha 4 pareti
 (v) ogni insieme non vuoto di celle possiede un perimetro esterno maggiore di 0
 
 ora, se tutti i prigionieri sono nella posizione iniziale ne consegue che:
 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))
 dalla (i) e dalla (ii) ricaviamo che il numero totale di spostamenti è maggiore o uguale di (4*x)/2
 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.
 
 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
 PPS: se c\'è ancora qualcosa che non torna faccio quello che fece mio nonno... <IMG SRC="images/forum/icons/icon_razz.gif">

Marco · Messaggio da **Marco** » 01 gen 1970, 01:33

No. Ora torna perfettamente.

MindFlyer · Messaggio da **MindFlyer** » 01 gen 1970, 01:33

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).
 Marco, insisto io perché tu pubblichi la tua soluzione.

MindFlyer · Messaggio da **MindFlyer** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-11-30 13:41, MASSO wrote:
 il numero massimo di spostamenti che si possono verificare è uguale al numero di pareti cioè 2*n*(n-1)
 [...]
 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.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 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).

Marco · Messaggio da **Marco** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-12-02 15:09, MindFlyer wrote:
 Marco, insisto io perché tu pubblichi la tua soluzione.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Ciao. Beh, allora, a grande richiesta...
 
 --------
 [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]
 
 Lemma dei Muri: Sia A un insieme di N celle. Se celle contigue di A sono divise da almeno 2N muri, allora A è vuoto.
 
 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. []
 
 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. []
 --------
 
 A margine aggiungo:
 
 Lemma dei Muri: Sia A un insieme di N celle. Se celle contigue di A sono divise da almeno 2N muri, allora A è vuoto.
 
 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. []
 (anche meglio della mia...)
 
 Morale: per essere rigorosi non è né necessario, né sufficiente essere anche formali.
 
 Ad ogni modo: un bravo a Masso per la soluzione, e un bravino a Boll per averci provato.
 
 Ciao. M. [ Questo Messaggio è stato Modificato da: marco il 02-12-2004 16:44 ]