Dimostrazione scacchiera - SNS 1965

elios2
"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.

Risposte
G.D.5

giammaria2
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.

G.D.5
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 $A$ a $H$ i numeri da $1$ a $8$, rispettivamente:

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

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

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.

elios2
"WiZaRd":
sicché c'è una differenza tra $1$ e $6$ al più di $4\cdot14=56$: assurdo. $\square$


"sicché c'è una differenza fra $1$ e $64$", giusto?

elios2
"WiZaRd":
Una torre, nella peggiore delle ipotesi, ha un percorso minimo di $14$ caselle


non è stato detto prima che è il percorso massimo?

G.D.5
Non ho capito cosa non hai capito...

elios2
Facendo riferimento alla mia prima domanda, tu hai scritto che "la differenza tra $1$ e $6$".. Cioè intendi la differenza di caselle da attraversare fra la casella con l'$1$ e la casella col $64$?

G.D.5
No. Intendo proprio 64-1.

elios2
Perché "64-1"?

G.D.5
Faccio riferiemento alla seconda scacchiera che ho postato.

Per definizione, le case contigue sono quelle con un lato in comune: queste case si possono attraversare solo con dei movimenti lungo gli assi della scacchiera e i pezzi capaci di questi movimenti sono il Re, la Donna e la Torre. Il Re e la Donna sono capaci anche di movimenti in diagonale, sicché utilizzare le distanze per questi pezzi è inutile: si andrebbero a trovare le distanze diagonali. Allora usiamo la distanza della Torre: la distanza di Manhattan ci dice che il minimo numero di case da attraversare è $d(A,B)=|i-h|+|j-k|$. Ovviamente la Torre potrebbe percorre molte più case, basterebbe farle fare dei giri assurdi, invece quella formula esprime il numero di case da attraversare compiendo un solo movimento in orizzonatale e uno solo in verticale. Il massimo delle minime distanze è $14$ case. Prendiamo la casa con l'$1$ e quella col $64$: la Torre per andare dalla casa con il $64$ alla casa con l'$1$ deve attraversare, nella peggiore delle minori distanze, ben $14$ case, ci cui la quattordicesima reca il numero $1$.

Se calcoliamo la domma delle differenze tra i numeri segnati di casa in casa si ha:

$(64 - x_{1}) + (x_{1} - x_{2}) + (x_{2} - x_{3}) + \cdots + (x_{12} - x_{13})+(x_{13}-1)=64-1=63$

Se per assurdo tra due case contigue c'è uno scarto tra i numeri ad esse associati di al più $4$ unità, otterremmo che la precedente somma varrebbe al più $56$, con l'evidente assurdo $56=64$.

elios2
tutto chiaro adesso, grazie!

G.D.5
Di niente.

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.