Conway\'s Soldiers

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

Bloccato
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 01 gen 1970, 01:33

<!-- 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>Mi misi le mani in tasca, Toby mi salì in mano e io gli diedi due granetti di cibo che presi dalla cartella; tenni stretto il coltellino svizzero nell\'altra mano e cominciai a gemere per coprire il rumore, adesso che le orecchie non erano più protette, ma non tanto forte, per non farmi sentire dagli altri ed evitare che qualcuno si avvicinasse e mi rivolgesse la parola.
<BR>
<BR>Poi cercai di riflettere sul da farsi, ma non riuscivo a pensare perché c\'erano troppe cose nella mia testa, così decisi di risolvere un problema di matematica per sgombrare la mente. Si chiamava il prblema dei Soldati di Conway. In questo problema c\'è una scacchiera che prosegue all\'infinito in tutte le direzioni e ogni quadrato sotto una linea orizzontale mostra una tessera colorata così
<BR>
<BR>......................
<BR>......................
<BR>......................
<BR>......................
<BR>......................
<BR>xxxxxxxxxxxxxxxxxxxxxx
<BR>xxxxxxxxxxxxxxxxxxxxxx
<BR>xxxxxxxxxxxxxxxxxxxxxx
<BR>xxxxxxxxxxxxxxxxxxxxxx
<BR>xxxxxxxxxxxxxxxxxxxxxx
<BR>
<BR>
<BR>E\' possibile muovere una tessera colorata solo se si può farla saltare oltre un\'altra tessera colorata in linea orizzontale o verticale (non in diagonale) e posizionarsi in una casella vuota due spazi più in là. E quando si muove una tessera colorata in questo modo bisogna spostare la tessera colorata che è saltata, secondo questo schema
<BR>
<BR>
<BR>......... .........
<BR>......... .........
<BR>......... .........
<BR>......... .........
<BR>....x.... ....x....
<BR>xxxx^xxxx xxxx.xxxx
<BR>xxxx|xxxx xxxxx<-xx
<BR>xxxxxxxxx xxxxxxxxx
<BR>xxxxxxxxx xxxxxxxxx
<BR>xxxxxxxxx xxxxxxxxx
<BR>
<BR>E si deve capire quanto si riesce ad andare oltre la linea orizzontale iniziale con le tessere colorate, e si comincia facendo una cosa così
<BR>
<BR>[...illustrazione...]
<BR>
<BR>E poi si fa una cosa così
<BR>
<BR>[...altra illustrazione...]
<BR>
<BR>E io conosco la risposta perché comunque si muovano le tessere colorate non si potrà mai andare oltre 4 caselle al di sopra della linea orizzontale iniziale, ma è davvero un bel problema di matematica da risolvere per riempirsi il cervello quando non si vuole pensare a nient\'altro perché lo si può rendere difficile finché si vuole allargando la scacchiera e complicando le mosse a piacimento.
<BR>
<BR>(Mark Haddon, Lo strano caso del cane ucciso a mezzanotte, cap. 191)
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Ciao a tutti.
<BR>
<BR>Non crocifiggetemi per questo, ma oggi vi propongo questo vecchio classico (dico vecchio, perché è +/- mio coetaneo...) che però forse non tutti conoscono. Chi conoscesse la soluzione, per cortesia, lasci divertire gli altri <IMG SRC="images/forum/icons/icon_wink.gif"> . Di questo problema mi è piaciuta la formulazione letteraria e così ve l\'ho riportata. Chiedo scusa per le illustrazioni. Se i diagrammi sono illeggibili, leggeteli con un font a larghezza fissa (oppure compratevi il libro!). Comunque su <a href="http://mathworld.wolfram.com/ConwaysSoldiers.html" target="_blank" target="_new">http://mathworld.wolfram.com/ConwaysSoldiers.html</a>, trovate una spiegazione migliore, che non contiene la soluzione.
<BR>
<BR>E\' vietato cercare la dimostrazione in Internet!!
<BR>
<BR>Ciao.
<BR>
<BR>M.
<BR>
<BR>P.S.: Il romanzo è molto bello. Se avete due pomeriggi liberi, lo consiglio a chiunque.[addsig]
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Avatar utente
Catraga
Messaggi: 302
Iscritto il: 01 gen 1970, 01:00
Località: Trieste (Univ)

Messaggio da Catraga » 01 gen 1970, 01:33

Su, nessuna idea per questo bellissimo problema?
Aladin to the genius: "Oh, great spirit! My desire is that you do not fullfill my desire"
The genius was enlightened.

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 01 gen 1970, 01:33

<IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif">
<BR>
<BR>Booohh!!! Nessuno sta filando il mio bellissimo problema <IMG SRC="images/forum/icons/icon27.gif">
<BR>
<BR>Sarà perché:
<BR>
<BR>a) lo conoscono anche i sassi
<BR>b) non gliene frega niente a nessuno
<BR>c) è troppo difficile (ma non mi era sembrato...)
<BR>d) il libro lo avete letto e vi ha fatto onco
<BR>e) il libro non lo avete letto e, grazie alla mia recensione, non lo leggerete
<BR>f) come diavolo fa un libro ad avere un capitolo centonovantuno??
<BR>
<BR>Via ragazzi: offro pane e nutella a casa mia a chiunque posterà un tentativo di soluzione.
<BR>
<BR>A presto.
<BR>
<BR>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
FrancescoVeneziano
Site Admin
Messaggi: 601
Iscritto il: 01 gen 1970, 01:00
Località: Pisa
Contatta:

Messaggio da FrancescoVeneziano » 01 gen 1970, 01:33

Il problema E\' troppo complesso, chi lo conosce giustamente non interviene e chi non lo conosce difficilmente potrà risolverlo.
<BR>Concordo sul fatto che è un problema bellissimo, ma a mio avviso è anche estremamente difficile.
<BR>
<BR>CaO
<BR>Francesco
<BR>
<BR>(leggete il libro, merita)
Wir müssen wissen. Wir werden wissen.

Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll » 01 gen 1970, 01:33

<!-- 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-09-07 08:19, marco wrote:
<BR>f) come diavolo fa un libro ad avere un capitolo centonovantuno??
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Ad ogni capitolo, in ordince crescente, è associato un numero primo e non naturale, come nei libri normali... il libro è davvero bello, ma non ho la più vaga idea di come si risolva il problema
"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 » 01 gen 1970, 01:33

Ciao.
<BR>
<BR>Dici? Boh, vorrà dire che risparmierò la nutella.
<BR>
<BR>Io non conoscevo il problema, lo ho incontrato leggendo il libro; ho cercato la soluzione e ne ho trovata una rapidamente.
<BR>
<BR>Onestamente non mi è sembrato assolutamente stratosferico e inarrivabile, magari un po\' tricky, questo sì; ma chi ha un po\' di esperienza olimpica dovrebbe arrivarci agile...
<BR>
<BR>Boh, è sempre difficile sapere se un problema è facile o difficile. Può anche darsi che abbia preso una cantonata.
<BR>
<BR>Beh, l\'offerta di pane & nutella è ancora valida...
<BR>
<BR>M.
<BR>
<BR>EDIT: mentra postavo questo mio, se ne è inserito un altro. In verità sto rispondendo a FV.
<BR>
<BR>
<BR>-------
<BR>
<BR>\"Well, master, we\'re in a fix and no mistake.\"
<BR><BR><BR>[ Questo Messaggio è stato Modificato da: marco il 07-09-2004 10:12 ]
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Avatar utente
Franchifis
Messaggi: 149
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da Franchifis » 01 gen 1970, 01:33

Sono d\'accordo sul fatto che il libro sia stupendo.
<BR>Davvero hai trovato una soluzione \"semplice\" al problema?

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 01 gen 1970, 01:33

Ciao.
<BR>
<BR>Gasp, ora mi fate venire il dubbio di avere sbagliato i conti.
<BR>
<BR>Comunque ho usato il vecchio truccaccio di trovare un potenziale: se assegno un punteggio ad ogni casella e sommo i punti delle caselle piene, e lo faccio in modo tale che il punteggio totale resti costante o almeno non crescente, beh, allora sono a posto. Con quest\'idea, il problema è straight. La prima distribuzione di pesi che ho provato ha funzionato, e quindi non mi sembrava tutta quella difficoltà.
<BR>
<BR>Se qualcuno è interessato ai dettagli, me lo dica, che li posto.
<BR>
<BR>Ciao.
<BR>
<BR>M.
<BR>[addsig]
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Avatar utente
MASSO
Messaggi: 134
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza\Pisa

Messaggio da MASSO » 01 gen 1970, 01:33

se li posti mi fai un grande favore perchè dopo aver letto il tuo post ho tentato quella strada per un bel po ed ho fallito miseramente <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif">
<BR>Cmq il libro l\'ho letto anch\'io ed è veramente stupendo <IMG SRC="images/forum/icons/icon_smile.gif">

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 01 gen 1970, 01:33

Ciao.
<BR>
<BR>Ma allora mi inviti a nozze!!!
<BR>
<BR>Allora, si diceva che voglio un potenziale. Ossia una distribuzione di pesi non negativi, che non aumenti facendo mosse e che, possibilmente, sia sufficientemente piccola sul 1/2piano occupato, in modo tale da non avere abbastanza energia per raggiungere la quinta fila.
<BR>
<BR>Qui siamo in presenza di file infinite di pedine, quindi avrò serie infinite. Perché convergano, qual\'è la prima serie che viene in mente?
<BR>
<BR>--- Tutti in coro ---
<BR>LA SERIE GEOMETRICA!!
<BR>
<BR>Esatto. Quindi: fisso una casella bersaglio che voglio raggiungere, sulla quinta riga e assegno ad ogni casella del piano la distanza d dal bersaglio (distanza-Torre). Ad ogni casella associo il punteggio q<sup>d</sup>. Perché sia un potenziale, considerando la mossa possibile, deve succedere che q<sup>2</sup> + q >= 1. Il caso che funziona meglio (lo si vede provando a fare i conti) è quello con l\'uguale. Quindi q viene il numero aureo (o il suo inverso, o lui meno uno, non me lo ricordo mai). Insomma la radice positiva di q<sup>2</sup> + q - 1.
<BR>
<BR>Le mosse possibili, sono fatte avvicinandosi alla casella bersaglio (e il punteggio totale resta costante) oppure sono fatte allontanandosi (per i pignoli, anche in orizzontale, a cavallo della fila verticale del bersaglio) e in questo secondo caso il potenziale diminuisce strettamente.
<BR>
<BR>Io vorrei mettere una pedina sul bersaglio, che ha punteggio 1 ( = q<sup>0</sup> ). Quanto fa il punteggio iniziale? Salta fuori una serie geometrica, che sommata fa, udite, udite, 1. Beh, qui posso avere sbagliato i conti, quindi rifateli per sicurezza (sono uno specialistone a sbagliare i calcoli!!)
<BR>
<BR>Dato però che in un numero finito di mosse non posso che eliminare un numero finito di pedine, non si potrà mai concentrare tutto il potenziale solo nel bersaglio.
<BR>
<BR>Ok, lo dico bene. Ragiono per assurdo e suppongo che ci sia una sequenza finita di mosse che raggiunge il bersaglio. Considero solo l\'insieme delle pedine iniziali che sono mosse almeno una volta dalla sequenza. Queste hanno un punteggio complessivo <1, dato che è maggiorato da tutto il semipiano che vale 1. Ma allora, non è possibile arrivare a mettere una pedina sul bersaglio, che ha punteggio 1, dato che il punteggio è non crescente.
<BR>
<BR>[applausi]
<BR>
<BR>---------------
<BR>
<BR>Ho una congettura in piedi, per chi ci vuole provare (ma non so quanto sia facile e nemmeno quanto sia vera e nemmeno se è inedita). Se invece di un punteggio iniziale 1, metto un punteggio di 1+epsilon (ossia, ho da qualche parte, lontanissimo nel semipiano, una casella \"doppia\" cioè per cui, solo per la prima volta in cui viene vuotata da una mossa, rinasce automaticamente una pedina extra). Allora il punteggio complessivo è maggiore stretto di 1. Ce la faccio a raggiungere la quinta fila? Secondo me sì, ma non so se è facile trovare la costruzione giusta. Boh, pensateci. Pane e nutella anche su questo quesito, e doppia dose, per di più!
<BR>
<BR>Ciao.
<BR>
<BR>M.
<BR>
<BR>-------
<BR>
<BR>\"Well, master, we\'re in a fix and no mistake.\"
<BR><BR><BR>[ Questo Messaggio è stato Modificato da: marco il 08-09-2004 14:59 ]
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Bloccato