Dimostrazione scacchiera - SNS 1965

[elios]

"Si dispongano sulle 64 caselle di una scacchiera i numeri 1,2,3,...,64. Chiamiamo contigue due caselle che hanno un lato in comune. Si dimostri che esistono almeno due caselle contigue i cui numeri differiscono per più di 4."

Come devo impostare il problema? Grazie.

[WiZaRd]

[giammaria]

Bè, ma se la soluzione fosse quella di Wizard non sarebbe un problema da SNS. Il testo di elios non è chiaro, ma io lo interpreterei modificando l'ultima frase in "Si dimostri che, comunque siano disposti i numeri, esistono almeno due caselle contigue ..." in modo da complicare le cose. Per ora non vedo la soluzione; debbo pensarci.

[WiZaRd]

Le caselle contigue sono definite come caselle che hanno un lato in comune: di tutti i pezzi degli scacchi l'unico che si muovono unicamente attraversando caselle contigue è la torre.
Si prenda la seguente scacchiera e si supponga di sostituire alle lettere da \( \displaystyle {A} \) a \( \displaystyle {H} \) i numeri da \( \displaystyle {1} \) a \( \displaystyle {8} \), rispettivamente:

Se \( \displaystyle {A} \) è la casella di coordinate \( \displaystyle {\left({i},{j}\right)} \) e \( \displaystyle {B} \) quella di coordinate \( \displaystyle {\left({h},{k}\right)} \), nel gioco degli scacchi di definisce distanza di Manhattan la quantità
\( \displaystyle {d}{\left({A},{B}\right)}={\left|{i}-{h}\right|}+{\left|{j}-{k}\right|} \).
Questa distanza esprime il numero minimo di caselle contigue che una torre deve attraversare per passare da \( \displaystyle {A} \) a \( \displaystyle {B} \). Il massimo di questa quantità si ha quando le caselle \( \displaystyle {A} \) e \( \displaystyle {B} \) sono agli estremi di una diagonale principale: in tal caso il numero di caselle che si attraversano è \( \displaystyle {14} \).
Si considerino le caselle con \( \displaystyle {1} \) e \( \displaystyle {64} \) e si supponga che per ogni coppia di caselle contingue la differenza tra i numeri loro associati è al più \( \displaystyle {4} \). Una torre, nella peggiore delle ipotesi, ha un percorso minimo di \( \displaystyle {14} \) caselle, sicché c'è una differenza tra \( \displaystyle {1} \) e \( \displaystyle {64} \) al più di \( \displaystyle {4}\cdot{14}={56} \): assurdo. \( \displaystyle \boxempty \)

[elios]

cioè, per risolvere i problemi della SNS è necessario sapere le regole degli scacchi?

[ViciousGoblin]

@elios Non mi pare che Wizard dica che e' necessario conoscere le regole degli scacchi - pero' puo' essere utile conoscerle per visualizzare il significato di quella distanza, che comunque
rimane intuitiva anche se non e' una torre a percorrerla.


Pero' quello che non ho capito nel discorso di Wizard e' se sia lecito sommare tutte le differenze, che invece (mi sembra) potrebbero compensarsi tra loro. Forse ci vole un ragionamento
piu' articolato.

Mi ritiro a meditare

[ViciousGoblin]

Ehh forse sarebbe meglio che io leggessi bene il testo prima di pronunciarmi - avevo capito che bisognasse dimostrare che le caselle confinanti non possono avere tutte differenza
maggiore di quattro.
Capito correttamente il problema mi pare che la dim. di Wizard sia perfetta.

[elios]

sicché c'è una differenza tra \( \displaystyle {1} \) e \( \displaystyle {6} \) al più di \( \displaystyle {4}\cdot{14}={56} \): assurdo. \( \displaystyle \boxempty \)

"sicché c'è una differenza fra \( \displaystyle {1} \) e \( \displaystyle {64} \)", giusto?

[elios]

Una torre, nella peggiore delle ipotesi, ha un percorso minimo di \( \displaystyle {14} \) caselle

non è stato detto prima che è il percorso massimo?

[WiZaRd]

Non ho capito cosa non hai capito...