Conway\'s Soldiers

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>
 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.
 
 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ì
 
 ......................
 ......................
 ......................
 ......................
 ......................
 xxxxxxxxxxxxxxxxxxxxxx
 xxxxxxxxxxxxxxxxxxxxxx
 xxxxxxxxxxxxxxxxxxxxxx
 xxxxxxxxxxxxxxxxxxxxxx
 xxxxxxxxxxxxxxxxxxxxxx
 
 
 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
 
 
 ......... .........
 ......... .........
 ......... .........
 ......... .........
 ....x.... ....x....
 xxxx^xxxx xxxx.xxxx
 xxxx|xxxx xxxxx<-xx
 xxxxxxxxx xxxxxxxxx
 xxxxxxxxx xxxxxxxxx
 xxxxxxxxx xxxxxxxxx
 
 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ì
 
 [...illustrazione...]
 
 E poi si fa una cosa così
 
 [...altra illustrazione...]
 
 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.
 
 (Mark Haddon, Lo strano caso del cane ucciso a mezzanotte, cap. 191)
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Ciao a tutti.
 
 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.
 
 E\' vietato cercare la dimostrazione in Internet!!
 
 Ciao.
 
 M.
 
 P.S.: Il romanzo è molto bello. Se avete due pomeriggi liberi, lo consiglio a chiunque.[addsig]

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

Su, nessuna idea per questo bellissimo problema?

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

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.
 Concordo sul fatto che è un problema bellissimo, ma a mio avviso è anche estremamente difficile.
 
 CaO
 Francesco
 
 (leggete il libro, merita)

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

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-09-07 08:19, marco wrote:
 f) come diavolo fa un libro ad avere un capitolo centonovantuno??
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 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

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

Ciao.
 
 Dici? Boh, vorrà dire che risparmierò la nutella.
 
 Io non conoscevo il problema, lo ho incontrato leggendo il libro; ho cercato la soluzione e ne ho trovata una rapidamente.
 
 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...
 
 Boh, è sempre difficile sapere se un problema è facile o difficile. Può anche darsi che abbia preso una cantonata.
 
 Beh, l\'offerta di pane & nutella è ancora valida...
 
 M.
 
 EDIT: mentra postavo questo mio, se ne è inserito un altro. In verità sto rispondendo a FV.
 
 
 -------
 
 \"Well, master, we\'re in a fix and no mistake.\"
 [ Questo Messaggio è stato Modificato da: marco il 07-09-2004 10:12 ]

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

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

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

Ciao.
 
 Gasp, ora mi fate venire il dubbio di avere sbagliato i conti.
 
 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à.
 
 Se qualcuno è interessato ai dettagli, me lo dica, che li posto.
 
 Ciao.
 
 M.
 [addsig]

MASSO · 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">
 Cmq il libro l\'ho letto anch\'io ed è veramente stupendo <IMG SRC="images/forum/icons/icon_smile.gif">

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

Ciao.
 
 Ma allora mi inviti a nozze!!!
 
 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.
 
 Qui siamo in presenza di file infinite di pedine, quindi avrò serie infinite. Perché convergano, qual\'è la prima serie che viene in mente?
 
 --- Tutti in coro ---
 LA SERIE GEOMETRICA!!
 
 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 qd. Perché sia un potenziale, considerando la mossa possibile, deve succedere che q2 + 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 q2 + q - 1.
 
 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.
 
 Io vorrei mettere una pedina sul bersaglio, che ha punteggio 1 ( = q0 ). 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!!)
 
 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.
 
 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.
 
 [applausi]
 
 ---------------
 
 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ù!
 
 Ciao.
 
 M.
 
 -------
 
 \"Well, master, we\'re in a fix and no mistake.\"
 [ Questo Messaggio è stato Modificato da: marco il 08-09-2004 14:59 ]