[C] I prigionieri di Gabriel Carroll

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

MindFlyer

Messaggio da MindFlyer »

Una prigione consiste in una griglia di nxn celle quadrate, ognuna occupata da uno ed un solo prigioniero. Ogni giorno, 2 prigionieri in celle con un muro in comune si scambiano di posto, e quel muro viene poi fortificato in modo che nessun prigioniero lo possa più attraversare. Dimostrare che, se ad un certo punto i prigionieri si trovano tutti contemporaneamente nella loro cella originaria, allora nessun prigioniero si è mai spostato.
Avatar utente
MASSO
Messaggi: 134
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza\Pisa

Messaggio da MASSO »

Dunque; il numero massimo di spostamenti che si possono verificare è uguale al numero di pareti cioè 2*n*(n-1); ogni detenuto che si sposti e che torni successivamente al suo posto deve ovviamente attraversare almeno 4 pareti; dunque se tutti alla fine sono al proprio posto significa che se ne sono mossi al massimo 2*n*(n-1)/4 ma se si sono mossi solo loro vuol dire che sono state attraversate al massimo 2*n*(n-1)/4 *4 /2 pareti (per quattro perchè ogni cella ha quattro pareti e diviso due perchè ogni parete usata divideva due dei detenuti considerati); 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.
MindFlyer

Messaggio da MindFlyer »

No, la dimostrazione ha degli errori.
<BR>Ottima l\'idea iniziale, ma poi non ti seguo più: dici che si sono mossi al massimo 2n(n-1)/4 prigionieri, ma in realtà dovresti dire 2n(n-1)/2, perché ogni spostamento coinvolge 2 prigionieri. E così hai dimostrato che almeno n prigionieri stanno fermi.
<BR>Da qui, la discesa infinita non regge (e comunque, l\'hai applicata in un contesto sbagliato...). Infatti torneresti a dire che gli spostamenti sono stati al massimo 2n(n-1), che è il punto di partenza.
Avatar utente
MASSO
Messaggi: 134
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza\Pisa

Messaggio da MASSO »

mmmm..ok, riparto dai miei errori per tentare la giusta soluzione: se in tutto si muovono n prigionieri, essi si muovono attraverso un numero di pareti che è sicuramente minore di 2n (quattro per ogni stanza ma le stanze devono averne una in comune); ed in tutto devono fare al meno 2n passaggi (quattro a testa ma ad ogni passaggio se ne muovono due); da ciò deriva che il numero di passaggi è p --> 2n<=p<2n e ciò è chiaramente impossibile<BR><BR>[ Questo Messaggio è stato Modificato da: MASSO il 30-11-2004 20:24 ]
Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll »

Manca un pò di formalizzazione, forse dovrei usare l\'induzione, espongo l\'idea poi sappiatemi dire che se è buona cerco di formalizzare.
<BR>
<BR>Chiamiamo A<SUB>1</SUB>,A<SUB>1</SUB>,...,A<SUB>n</SUB> le caselle del primo rigo, B<SUB>1</SUB>,B<SUB>2</SUB>,..,B<SUB>n</SUB> le caselle del secondo rigo e così via.
<BR>Dimostriamo ora che A<SUB>1</SUB> non si può spostare. Abbiamo due casi, A<SUB>1</SUB> si può scambiare con A<SUB>2</SUB> o B<SUB>1</SUB>, ma i due casi sono uguali per simmetria, se avviene lo spostamento, per tornare alla postazione originale A<SUB>1</SUB> deve passare per la riga B o per la colonna 1, ciò impedisce ad A<SUB>2</SUB> e B<SUB>1</SUB> di tornare nelle posizioni originali, poichè tornando A<SUB>1</SUB> chiude una delle due caselle necessarie al \"rientro\" dei due. Ora abbiamo quindi che i quattro vertici sono punti fissi. Dimostriamo quindi che il reticolo è fisso. Preso A<SUB>2</SUB> esso si può scambiare con A<SUB>3</SUB> o B<SUB>2</SUB>, in entrambi i casi lo \"scambiato\" si troverebbe in una casella inutilizzabile pioichè A<SUB>3</SUB> per \"tornare alla base\" ha bisogno di una della direzione lasciata libera, ma anche lo \"spostato\" ha bisogno della stessa direzione poichè A<SUB>1</SUB> è fisso. Con lo stesso ragionamento possiamo \"scalare\" per tutti gli n punti e successivamente \"scalare\" all\'interno nel rettangolino di lato n-2, finchè non arriviamo all\'interno e dimostriamo la tesi (per discesa infinita, azzarderei...)
<BR>
<BR>Fammi sapere Mind, se non comprendi i miei deliri provo ad abbozzare uno schemino, ma non so come riuscirebbe <IMG SRC="images/forum/icons/icon_wink.gif">...
<BR>
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco »

<!-- 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 20:00, MASSO wrote:
<BR>mmmm..ok, riparto dai miei errori per tentare la giusta soluzione: se in tutto si muovono n prigionieri, essi si muovono attraverso un numero di pareti che è sicuramente minore di 2n (quattro per ogni stanza ma le stanze devono averne una in comune); ed in tutto devono fare al meno 2n passaggi (quattro a testa ma ad ogni passaggio se ne muovono due); da ciò deriva che il numero di passaggi è p --> 2n<=p<2n e ciò è chiaramente impossibile
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->Consiglio: se devi introdurre un nuovo numero (n), è fortemente consigliabile che tu scelga un simbolo <!-- BBCode Start --><B>diverso</B><!-- BBCode End --> da quelli del testo del problema (n)... Altrimenti corri il forte richio di essere frainteso. (ci ho messo un paio di minuti a capire che i due \"n\" erano diversi...).
<BR>
<BR>Inoltre mi sembra che c\'è qualcosa che non va: esiste una soluzione (non accettabile) al problema: quella con zero spostamenti. La tua dimostrazione esclude anche n=0. Strano...
<BR>
<BR>Vai avanti: l\'idea è buona...
<BR>
<BR>Ciao. M.[addsig]
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco »

<!-- 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 20:08, Boll wrote:
<BR> ciò impedisce ad A<SUB>2</SUB> e B<SUB>1</SUB> di tornare nelle posizioni originali, poichè tornando A<SUB>1</SUB> chiude una delle due caselle necessarie al \"rientro\" dei due [...]
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Diamine Boll: in che lingua è scritto? In Assiro-Babilonese? Non ho capito nulla. (a parte che usi la notazione degli Scacchi...) Va bene dare \"giusto l\'idea\", ma almeno quella, diamola...
<BR>
<BR>Non sono nemmeno tanto convinto della dimostrazione che l\'angolo a1 non si muove. Puoi spiegare meglio, anche solo quel lemmino?
<BR>
<BR>Ciao.
<BR>
<BR>M.<BR><BR>[ Questo Messaggio è stato Modificato da: marco il 01-12-2004 10:57 ]
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
MindFlyer

Messaggio da MindFlyer »

<!-- 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 20:00, MASSO wrote:
<BR>se in tutto si muovono n prigionieri, essi si muovono attraverso un numero di pareti che è sicuramente minore di 2n (quattro per ogni stanza ma le stanze devono averne una in comune)
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Ecco l\'errore: hai dimostrato che il numero di pareti è minore <!-- BBCode Start --><I>o uguale</I><!-- BBCode End -->, non minore. Quindi l\'assurdo finale non regge, ma ci sei quasi.
MindFlyer

Messaggio da MindFlyer »

Boll, non ascoltare Marco: io ho capito benissimo quello che hai scritto, sarà per affinità di linguaggio...
<BR>
<BR><!-- 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 20:08, Boll wrote:
<BR>Dimostriamo ora che A<SUB>1</SUB> non si può spostare. Abbiamo due casi, A<SUB>1</SUB> si può scambiare con A<SUB>2</SUB> o B<SUB>1</SUB>, ma i due casi sono uguali per simmetria, se avviene lo spostamento, per tornare alla postazione originale A<SUB>1</SUB> deve passare per la riga B o per la colonna 1, ciò impedisce ad A<SUB>2</SUB> e B<SUB>1</SUB> di tornare nelle posizioni originali, poichè tornando A<SUB>1</SUB> chiude una delle due caselle necessarie al \"rientro\" dei due.</BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Ecco, questo non va. A parte che non dimostrerebbe che A1 è fisso, ma al più che A1 o A2 o B1 sono fissi... Il guaio però è che non dimostra nemmeno questo, perché non è affatto vero che A1 chiude la via del ritorno ad A2 o B1 in modo così banale, pensaci bene.
MindFlyer

Messaggio da MindFlyer »

Altro piccolo appunto: sia MASSO che Boll hanno citato la discesa infinita a sproposito, o in modo dubbioso.
<BR>La discesa infinita altro non è che una parafrasi del principio di induzione: non esiste una successione strettamente decrescente di naturali. Ora, se questo enunciato serve per la vostra dimostrazione, lo usate. Altrimenti no. Fine.
Avatar utente
MASSO
Messaggi: 134
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza\Pisa

Messaggio da MASSO »

@MindFlyer: scrissi minore senza l\'uguale proprio perchè se no non torna, cmq non l\'ho giustificato esplicitamente quindi hai ancora una volta ragione tu; in ogni caso il numero di pareti deve essere strettamente minore perchè sul piano non è possibile che tutte le pareti in questione appartengano a due stanze considerate, dovrà pur esistere un perimetro esterno dell\'insieme di queste stanze no?
<BR>@marco: effettivamente nella dimostrazione considero n (la prossima volta lo chiamerò x <IMG SRC="images/forum/icons/icon_smile.gif"> ) uguale al numero di prigionieri che si spostano, ebbene occorre appunto la dovuta precisazione che questo vale solo per n>1; difatti non si può muovere un solo prigioniero per definizione e se se ne muovono zero ovviamente ognuno è al posto di partenza
<BR>
<BR>mi auguro che ora sia corretta (sarebbe ora) <IMG SRC="images/forum/icons/icon_razz.gif">
Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll »

Boh, a me la dimostrazione di masso non torna, abbandono l\'idea degli scacchi perchè è troppo \"incasinata\" e dovrei considerare troppi casi, inoltre non riesco a esprimerla in un linguaggio accettabile <IMG SRC="images/forum/icons/icon_wink.gif">.
<BR>
<BR>Abbiamo n(n-1) pareti (n-1 per ogni riga, n colonne), quindi n(n-1) spostamenti possibili. Ogni pedone deve spostarsi di almeno 4 \"mosse\" per tornare alla sua posizione originaria, tuttavia quando un pedone si muove di 4 mosse, ne muove automaticamente altri tre di una mossa, quindi il numero delle mosse minime è 1 per pedone, cioè n<sup>2</sup>.
<BR>n<sup>2</sup> > n<sup>2</sup>-n
<BR>0 > -n
<BR>n>0, poichè con 0 il problema non si pone, in tutti gli altri casi ci sono più mosse necessarie che mosse possibili, quindi la tesi è dimostrata.<BR><BR>[ Questo Messaggio è stato Modificato da: Boll il 01-12-2004 22:01 ]
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)
Avatar utente
MASSO
Messaggi: 134
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza\Pisa

Messaggio da MASSO »

Cosè che non ti torna nella mia dimostrazione?
<BR>A parte che nella tua non hai considerato che ad ogni mossa si muovono due pedoni e perciò si possono muovere tutti con (n^2)/2 mosse <IMG SRC="images/forum/icons/icon_razz.gif"> <IMG SRC="images/forum/icons/icon_razz.gif"> <IMG SRC="images/forum/icons/icon_razz.gif">
Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll »

Ho considerato che con ogni ciclo se ne muovono quattro <IMG SRC="images/forum/icons/icon_wink.gif">
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco »

Buongiorno ragazzi.
<BR><!-- 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-01 21:41, Boll wrote:
<BR>[...]quando un pedone si muove di 4 mosse, ne muove automaticamente altri tre di una mossa, quindi il numero delle mosse minime è 1 per pedone, cioè n².
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Ok. Ora il linguaggio è molto migliore. Non sono però sicuro di aver ben compreso: credo che così supponi che tutti gli n² prigionieri si muovano (o mi sbaglio?). Tuttavia qualcuno potrebbe stare fermo... Con il tuo ragionamento dimostri solo che <!-- BBCode Start --><B>almeno 4</B><!-- BBCode End --> prigionieri si devono spostare (e quindi hai incidentalmente risolto il caso n=2).
<BR>
<BR><!-- 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-01 20:41, MASSO wrote:
<BR>scrissi minore senza l\'uguale proprio perchè se no non torna
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Masso, scusami, ma non è che puoi scegliere se mettere il minore stretto o largo a tuo piacimento: se metti \"<\" lo devi dimostrare. Altrimenti ti devi accontentare di \"<=\". Giustamente M.F. ti ha fatto notare che il tuo ragionamento dimostra solo la disuguaglianza larga.
<BR><!-- 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>MASSO again wrote further:
<BR>in ogni caso il numero di pareti deve essere strettamente minore perchè sul piano non è possibile che tutte le pareti in questione appartengano a due stanze considerate, dovrà pur esistere un perimetro esterno dell\'insieme di queste stanze no?
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->Ottima, questa idea, per arrivare al minore stretto: ogni insieme finito di celle ha un perimetro.... O no? Meditate, gente, meditate...
<BR>
<BR>Le idee giuste a questo punto le hai tutte. Hai voglia di scrivere la stesura definitiva, che sistema i dettagli? (senza le ampollosità di Hitleuler, mi raccomando!<IMG SRC="images/forum/icons/icon_wink.gif">)
<BR>
<BR>Scusatemi se insisto un po\', sulla \"bella calligrafia\". Comunque, ascoltate il consiglio di uno stupido, che però un po\' di esperienza se l\'è fatta: è incredibile quanto ci si chiarisca le idee cercando di scrivere la bella copia di una dimostrazione appena accennata... e soprattutto di quanti buchi di ragionamento saltino fuori. Non è un caso, che la matematica sia così rigorosa.
<BR>
<BR>Quando hai fatto, e solo se ti va, ti vorrei far vedere la mia, (che, btw, sfrutta le medesime idee).
<BR>
<BR>Ciao.
<BR>
<BR>M.
<BR>
<BR>[addsig]
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
Bloccato