La scacchiera

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

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 2005-01-05 14:36, MASSO wrote:
<BR>il \"diametro-cavallo\" mi risulta 6, perchè ogni volta che ci si sposta si cambia la parità delle coordinate e perciò bisogna spostarsi per un numero pari di volte, inoltre con quattro spostamenti ci si sposta al più di 12 caselle-torre che è chiaramente troppo poco; <!-- BBCode Start --><B>in un gara la soluzione potrebbe finire qua o bisognerebbe fornire anche la serie di 6 mosse che risolvono il quesito?</B><!-- BBCode End -->
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Ovviamente non basta, perché così dimostri solo che non si può con meno di 6 mosse (oltre a tutto quello che ha detto Marco sull\'aver supposto che gli estremi della scacchiera siano il \"caso pessimo\").
<BR>
<BR>(a-->b) -/-> (b-->a), anche voi l\'avete studiato a scuola, vero?
bobby_fischer
Messaggi: 153
Iscritto il: 01 gen 1970, 01:00
Località: Imola

Messaggio da bobby_fischer »

A occhio, il gioco è impossibile perchè vi sono tantissimi diametri-torre, tutti che devono essere possibli, e quindi ad un certo punto non si riuscirà a giungere a 64.
<BR>Si tratterebbe di calcolare il numero di percorsi-torre e dimostrare che ve ne è almeno uno impercorribile.
<BR>
<BR>Ciao
<BR>Nick
<BR>
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 2005-01-06 13:04, bobby_fischer wrote:
<BR>A occhio, il gioco è impossibile perchè vi sono tantissimi diametri-torre, tutti che devono essere possibli, e quindi ad un certo punto non si riuscirà a giungere a 64.
<BR>Si tratterebbe di calcolare il numero di percorsi-torre e dimostrare che ve ne è almeno uno impercorribile.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Er.... temo che almeno uno di noi due non abbia capito...
<BR>
<BR>0) Il \"gioco\" è quello di Masso, vero??
<BR>
<BR>1) \"vi sono tantissimi diametri-torre, tutti che devono essere possibli\"
<BR>
<BR>Beh, se vogliamo, i diametri-Torre sono esattamente due, ma non ho capito che cosa stai intendendo con questa frase.
<BR>
<BR>2) \"non si riuscirà a giungere a 64\". Questo non capisco che cosa voglia dire.
<BR>
<BR>3) \"ne è almeno uno impercorribile\" Che significa impercorribile?
<BR>
<BR>No, guardate, il problema è davvero più semplice di così. Senza volerlo vi ho complicato la vita buttandovi lì i percorsi di Torre, ma era solo un modo per dire sinteticamente:
<BR>
<BR>\"successioni di caselle in cui coppie di caselle adiacenti hanno un lato in comune\"
<BR>
<BR>Se vi fa più confusione, lasciate perdere scacchi e torri: cercate di mettere i numeri sulla scacchiera e basta...
<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."
gian
Messaggi: 114
Iscritto il: 01 gen 1970, 01:00
Località: Brugine (PD)

Messaggio da gian »

<!-- 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>1) \"vi sono tantissimi diametri-torre, tutti che devono essere possibli\"
<BR>
<BR>Beh, se vogliamo, i diametri-Torre sono esattamente due, ma non ho capito che cosa stai intendendo con questa frase.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>forse tu considerei (restando in ambito scacchi) quelle percorse dalle case
<BR>a1-h1-h8 e a1-a8-h8, ma come dice Bobby_Fisher ne esistono altri come quelli dei percorsi a1-a2-h2-h8, a1-a3-h3-h8, a1-a4-h4-h8, ecc che sono comunque di 14 caselle. Perciò dovrebbero esserci molti \"percorsi\" per poter arrivare a 64, il che probabilmente non è vero.
<BR>
<BR>ciao a tutti
<BR> gian
ciao by gian
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco »

Ah, ecco! Questa è una cosa interessante che forse torna buona per risolvere il quesito.
<BR>
<BR>Ora capisco meglio anche che cosa intendesse Bobby. (btw, un nick scacchistico, ora che noto...). Io sarò anche un po\' zuccone, ma certo è che ci ha messo del suo per non farsi capire...
<BR>
<BR>Allora, l\'idea sembra essere che, prese due case lontane (quanto lontane?), ci sono tanti percorsi di lunghezza minima che le congiungono. Beh, diciamo che sapere esattamente <!-- BBCode Start --><I>quanti sono</I><!-- BBCode End --> non vi serve (anche se quelli bravi dovrebbero saperlo fare...). Tuttavia...
<BR>
<BR>Avanti, avanti, any idea?
<BR>
<BR>M.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
DB85
Messaggi: 145
Iscritto il: 01 gen 1970, 01:00
Contatta:

Messaggio da DB85 »

Non me ne intendo di scacchi, ma una cosa che mi viene in mente è dimostrare che x+2y+3z+4k+5k=63 ha un numero di soluzioni minore dei percorsi possibili, per x+y+z+k+h <= 14 (visto che come si è detto 14 è la lunghezza massima e considerando i percorsi ad esempio da 1 a 64). Marco che dici è una castroneria o è fattibile?
<BR><BR><BR>[ Questo Messaggio è stato Modificato da: DB85 il 07-01-2005 16:00 ]
"Le vite degli uomini famosi ci ricordano
Che possiamo rendere sublimi le nostre esistenze
E, morendo, lasciare dietro di noi
Le nostre impronte sulle sabbie del tempo"
Henry Wadsworth Longfellow
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 2005-01-07 15:41, DB85 wrote:
<BR>Non me ne intendo di scacchi, ma una cosa che i viene in mente è dimostrare che x+2y+3z+4k+5k=63 ha un numero di soluzioni minore dei percorsi possibili, per x, y, z, k, h < 14 (visto che come si è detto 14 è la lunghezza massima e considerando i percorsi ad esempio da 1 a 64). Marco che dici è una castroneria o è fattibile?
<BR>
<BR>[ Questo Messaggio è stato Modificato da: DB85 il 07-01-2005 15:42 ]
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Mumble.... let me see...
<BR>
<BR>Boh... anche se fosse, poi come lo usi? x è il numero di passi con differenza uno, y con diff. due, ecc...? Allora il vincolo giusto sarebbe x+y+bla bla =< 14 (decisamente più forte...); tuttavia a quel punto avresti solo dimostrato che devono esistere due percorsi con la stessa composizione di differenze, ma ancora non vedo come arrivare da qui ad un assurdo.
<BR>
<BR>Ah, e poi noto che state tacitamente supponendo che 1 e 64 debbano per forza stare in angoli diametralmente opposti. E chi l\'ha detto?
<BR>[addsig]
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
DB85
Messaggi: 145
Iscritto il: 01 gen 1970, 01:00
Contatta:

Messaggio da DB85 »

<!-- 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 2005-01-07 15:51, marco wrote:
<BR>
<BR> Allora il vincolo giusto sarebbe x+y+bla bla =< 14 (decisamente più forte...);
<BR>
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Sì scusami, è questa la relazione che intendevo.
"Le vite degli uomini famosi ci ricordano
Che possiamo rendere sublimi le nostre esistenze
E, morendo, lasciare dietro di noi
Le nostre impronte sulle sabbie del tempo"
Henry Wadsworth Longfellow
Avatar utente
info
Messaggi: 903
Iscritto il: 01 gen 1970, 01:00

Messaggio da info »

Proviamo...
<BR>
<BR>
<BR>se n<=5, allora
<BR>
<BR>i numeri >=57 devono essere in una casella k tale che d(1,k)>=12. Esistono 8 di questi numeri <=64 ma, anche mettendo l\'1 in un angolo solo 6 caselle sarebbero candidate, da quì l\'assurdo...
<BR>
<BR>Funzia?
<BR>
<BR>Se è corretto, provo a generalizzare l\'idea...
<BR>
<BR>
<BR><BR><BR>[ Questo Messaggio è stato Modificato da: info il 08-01-2005 22:58 ]
Avatar utente
what
Messaggi: 158
Iscritto il: 01 gen 1970, 01:00
Località: roma

Messaggio da what »

Non ho ben capito l\'idea di info... che rappresenta il tuo n?
<BR>e perché deve essere <=5?
<BR>
<BR>Provo io (anche se io stesso non sono convinto della \"bontà\" della mia soluzione <IMG SRC="images/forum/icons/icon_cool.gif"> ):
<BR>
<BR>Consideriamo le possibili posizioni per i numeri 1 e 64. La distanza fra le loro case è forzatamente >=13. Risulta allora chiaro guardando la scacchiera che uno dei due numeri si trova in un angolo (es a1) e l\'altro in una delle tre caselle ad esso più lontane (es g8, h8, h7).
<BR>
<BR>Per simmetria della scacchiera poniamo 1 in a1. Allora le tre case già elencate contengono 62, 63, 64, poichè tali numeri non potrebbero stare in nessun altra casa (le altre sono infatti troppo vicine).
<BR>
<BR>Analogamente il 61 non può non stare in una fra e8, g7, h6. Ora, la distanza fra una qualunque di queste case e a1 è 12, quindi 61 è il più grande intero che le può occupare.
<BR>
<BR>Poiché esistono almeno due sequenze distinte di case che portano da a1 a e8,g7,h6 con solo 12 mosse, e poiché esiste una sola sequenza numerica in accordo con le limitazioni del problema che va da 1 a 61 in 12 passaggi, abbiamo l\'assurdo.
<BR>
<BR>Ovviamente il ragionamento è \"rovesciabile\", nel senso che possiamo anche sistemare 64 in un angolo e ragionare su 1,2,3,4.
<BR>
<BR>Andrebbe formalizzato ma i concetti sono in linea di massima questi.
Avatar utente
info
Messaggi: 903
Iscritto il: 01 gen 1970, 01:00

Messaggio da info »

<!-- 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 2005-01-09 09:42, what wrote:
<BR>Non ho ben capito l\'idea di info... che rappresenta il tuo n?
<BR>e perché deve essere <=5?
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>n rappresenta una qualsiasi distanza tra le caselle. Questa deve essere strettamente minore di 6, ovvero <=5. 1+5*11=56, quindi i numeri >56 devono avere almeno dodici caselle di distanza da quella dell\'1. Questi numeri sono 8 (57,58,...,64). Le caselle con distanza 14 sono 1, quelle con distanza 13 sono 2, quelle con distanza 12, sono 3 (mi sono messo nel caso peggiore con 1 nell\'angolo). 1+2+3=6 e 6<8... Questo era il mio ragionamento....ti pare errato?
<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>Analogamente il 61 non può non stare in una fra e8, g7, h6. Ora, la distanza fra una qualunque di queste case e a1 è 12, quindi 61 è il più grande intero che le può occupare.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>I nomi delle caselle mi paiono errati (le caselle equi-distanti da un vertice mi pari si dispongano \"in diangonale\"..intendevi forse f8?), cmq quà nn hai già quà un assurdo?
<BR>Poi credo vada bene anche ciò che hai trovato dopo (basato sul fatto che il 61 DEVE stare a distanza max)...
<BR>
<BR><BR><BR>[ Questo Messaggio è stato Modificato da: info il 09-01-2005 17:12 ]
Avatar utente
what
Messaggi: 158
Iscritto il: 01 gen 1970, 01:00
Località: roma

Messaggio da what »

<!-- 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 2005-01-09 16:49, info wrote:
<BR>n rappresenta una qualsiasi distanza tra le caselle. Questa deve essere strettamente minore di 6, ovvero <=5.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Penso che l\'equivoco nasca dalla definizione di distanza: in base a quello che dici il tuo n rappresenta la differenza max fra numeri in case adiacenti (quindi \"distanza numerica\"), mentre io pensavo alla distanza intesa come lunghezza (misurata in case) del percorso minimo che va da una casella A ad una casella B. Comunque, tutto chiarito.
<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>Questo era il mio ragionamento....ti pare errato?
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>No, mi pare corretto. Inoltre, è più elegante del mio, e soprattutto sembra più facilmente generalizzabile ad una scacchiera nxn con la diff tra case adiacenti strettamente minore di k. Ovviamente, attendiamo conferme dai piani alti... <IMG SRC="images/forum/icons/icon_razz.gif">
<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>intendevi forse f8? cmq quà nn hai già quà un assurdo?
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Sì, intendevo f8. La dimostrazione poteva in effetti concludersi in maniera diversa, anche se le differenze mi sembrano minime.
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco »

Ovvìa, bene.
<BR>
<BR>Sia la soluzione di Info, che quella di What tornano. Per completezza, vi posto la mia, che è un po\' diversa (guardo le case sulla diagonale, ma l\'idea è sempre quella: non c\'è abbastanza spazio per sistemare i numeri alti lontano da quelli bassi.
<BR>
<BR><!-- BBCode Start --><B>Dim.:</B><!-- BBCode End --> Abbiamo già discusso che 1 e 64 devono distare (distanza-Torre) almeno tredici case; quindi o sono negli angoli opposti, o uno è in un angolo e l\'altro è in una casa adiacente all\'angolo opposto. A meno di simmetrie/rotazioni/complementazione a 65, posso supporre 1 nella casa a1 e 64 nella casa h8 o h7.
<BR>
<BR><!-- BBCode Start --><I>1o caso: 64 in h8</I><!-- BBCode End -->
<BR>
<BR>Le case della diagonale a8-h1 distano 7 da entrambi gli angoli con 1 e 64. Questo significa che devono contenere numeri non maggiori di 1+7*5 = 36 e non minori di 64-7*5 = 29. Dato che la diagonale contiene otto case, e i numeri compresi tra 29 e 36 sono proprio otto, significa che la diagonale contiene tutti e soli i numeri da 29 a 36. Consideriamo ora la casa che contiene 36. Essa ha almeno una casa adiacente che dista 6 dall\'angolo a1. Per ipotesi essa deve contenere un valore non inferiore a 36-5=31, ma non superiore a 1+6*5=31, ma abbiamo già dimostrato che 31 sta sulla diagonale. Assurdo.
<BR>
<BR><!-- BBCode Start --><I>2o caso: 64 in h7</I><!-- BBCode End -->
<BR>
<BR>Il procedimento è simile, ma devo considerare la diagonale a7-g1. Le sue case distano 6 da 1 e 7 da 64, quindi devono essere comprese tra 1+6*5 = 31 e 64-7*5 = 29. Ma tra 29 e 31 non ci sono abbastanza numeri per riempire le sette case della diagonale in questione. []
<BR>
<BR>Bene. E ora, per la gioia di grandi e piccini, ecco il promesso carico da undici (che Masso, senza volerlo, ha già anticipato...):
<BR>
<BR><!-- BBCode Start --><B>Problema generale:</B><!-- BBCode End -->
<BR>
<BR>Dimostrare che è impossibile riempire la scacchiera 8x8 con i numeri da 1 a 64 una e una sola volta in modo tale che caselle Torre-adiacenti differiscano per al più di 7. (su una generica scacchiera k x k, 7 diventa k-1)
<BR>
<BR>Quindi 5 non è affatto il risultato migliore possibile. Invece 7 (oppure k-1) lo è, dato che è abbastanza facile riuscire a numerare la scacchiera con differenza massima 8.
<BR>
<BR>Chi ci vuole provare a risolvere questo problema più generale?
<BR>
<BR>Ciao.
<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
info
Messaggi: 903
Iscritto il: 01 gen 1970, 01:00

Messaggio da info »

Si...in effetti ho utilizzato la stessa espressione per 2 cose diverse! Sorry!
<BR>
<BR>Purtroppo nn ho molto tempo da dedicare al problema generale, che sembra ben più sottile (vi confesserò che già il caso n=5 nn mi è parso immediato!!)<BR><BR>[ Questo Messaggio è stato Modificato da: info il 11-01-2005 14:02 ]
Hammond
Messaggi: 110
Iscritto il: 01 gen 1970, 01:00
Località: Verona

Messaggio da Hammond »

Intanto che uppo il problema generalizzato, ne approfitto per riproporre un esercizio correlato che marco aveva accennato: come si calcola il numero di differenti percorsi-torre di distanza minima tra due caselle?
Bloccato