scacchiere da completare

[blackdie]

Abbiamo una scacchiera 10*10.Partendo da una casella a scelta vi scriviamo uno.
Per scegliere la successiva abbiamo due alternative:
-sulla riga o sulla colonna della casella precendente a due quadratini di distanza da quella ultima segnata.
-sulle diagonali dellla casella precendere, ad una quadratini di distanza dalla precendente.


E' possibile completare questa scacchiera?E per quali n è possibile?


Spero si chiaro il problema,sennò chiedete..!
Ps. Non ho la soluzione.

[eli9o]

Secondo me ho capito male
Si vuole cercare un percorso che passi per tutte le caselle scegliendo tra le 2 possibili mosse?

Se fosse così il fatto che sia una scacchiera e non un semplice quadrato diviso in quadratini tutti uguali è abbastanza illuminante...

[fph]

La 10x10 si fa con un po' di strategia e un po' di tempo libero (ad esempio due ore di filosofia).
l'idea è: divide et impera. Risolvi prima il lemma:
è possibile percorrere una scacchiera 5x5 partendo dalla casella (3,4) e finendo nella casella (4,3)

[blackdie]

Secondo me ho capito male
Si vuole cercare un percorso che passi per tutte le caselle scegliendo tra le 2 possibili mosse?

Se fosse così il fatto che sia una scacchiera e non un semplice quadrato diviso in quadratini tutti uguali è abbastanza illuminante...

Si si deve riempire tutto il quadrato con quelle due mosse(propriamente non è una scacchiera,avevi ragione te).


@fph:proverò!Ma esiste una strategia specifica per risolverli,o si va a tentativi?Perche io non la trovo.Un metodo generale x una scacchiera n*n esiste?

[Fedecart]

Scusami non capisco una parte, quando dici a due quadratini di distanza, devo saltarne 2, lasciandoli vuoti, e mettere il numero nel terzo, o saltarne uno e mettere il numero nel secondo? Grazie...

[¬[ƒ(Gabriel)³²¹º]¼+½=¾]

iuppidu...2 ore di compito di latino sono state sufficenti:

.

[blackdie]

Devo dire che con il suggerimento di fph mi è venuto stamattina pure a me!



Ma per quali n una scacchiera n*n è completabile?


@federcart.Se guardi il link postato da gabriel(nasconderlo di piu no ?) vedi come funzionano le regole.!

[Gargantua]

Il problema può essere posto così:

- consideriamo la successione dei numeri naturali fino a 100; partendo da un numero qualunque e potendo spostarmi solo con queste otto mosse:

-3, +3, -20, +20, -18, +18, -22, +22

è possibile "percorrere" tutti i numeri senza passare due volte sullo stesso numero?

Oppure genericamente, per una scacchiera $ nXm $:

-consideriamo la successione dei numeri naturali fino ad $ n \cdot m $.
Partendo da un numero qualsiasi e potendo spostarmi solo con queste mosse:

-$ 3 $, +$ 3, $ +$ 2n $, -$ 2n $, -$ (2n -2) $, +$ (2n -2) $, - $ (2n +2) $, +$ (2n +2) $

è possibile "percorrere" tutti i numeri senza passare due volte sullo stesso numero?

Andando per tentativi abbiamo visto che nel caso di 10X10 la risposta è si, ma una soluzione a priori, su base teorica, mi sembra tutt'altro che semplice...

Comunque proviamoci!

[fph]

Il problema può essere posto così:
- consideriamo la successione dei numeri naturali fino a 100; partendo da un numero qualunque e potendo spostarmi solo con queste otto mosse:
-3, +3, -20, +20, -18, +18, -22, +22

Non è esatto, per esempio da 10 non puoi andare a 32.

@gli altri: non so cosa succeda per scacchiere di lato diverso da 10. Può essere un problema "self-posed" interessante...

[fph]

La soluzione di gabriel in realtà non è quella che pensavo io, non fa tutta la 5x5 ma ci sono degli "aggiustamenti" alla fine... se si riesce a fare tutta una scacchiera 5x5 partendo da (3,4) e arrivando da (4,3) in un passaggio, allora si ottiene una soluzione del 10x10 con la proprietà aggiuntiva che da 100 si può andare a 1 (chiamiamola "ciclica"). Data una soluzione ciclica, si può passare facilmente a una soluzione che ha l'1 in una qualsiasi posizione (come?) e questo permette di fare alcuni giochini interessanti per fare rettangoli 10nx10m ciclici "incollando" tanti 10x10 ciclici (come?).

[Gargantua]

Il problema può essere posto così:
- consideriamo la successione dei numeri naturali fino a 100; partendo da un numero qualunque e potendo spostarmi solo con queste otto mosse:
-3, +3, -20, +20, -18, +18, -22, +22

Non è esatto, per esempio da 10 non puoi andare a 32.

Si, è vero! Grazie per avermelo fatto notare!
Per spalmare il problema su una sola dimensione come stavo facendo io, bisogna aggiungere dei vincoli.
Indicando con p il numero della casella in cui mi trovo, con $ a $ la quantità $ \frac{p}{10} $ approssimata per eccesso all'intero e con $ b $ la stessa quantità approssimata per difetto all'intero, le mosse corrette per 10X10 sono:

+3, solo se $ 10a-p >=3 $

-3, solo se $ p-10b+1>= 3 $

-20

+20

-18, solo se $ 10a- p>= 2 $

+18, solo se $ p - 10a+1>= 2 $

-22, solo se $ p-10b+1>= 2 $

+22, solo se $ 10a- p>=2 $

In effetti, definite le mosse possibili, il problema si può visualizzare in questo modo: ogni casella è "collegata" a un certo gruppo di caselle, che rappresentano le caselle che si possono raggiungere da quella e le caselle dalle quali si può arrivare a lei; il massimo di collegamenti possibili per una casella è 8.
Si tratta di un grafo, in cui i nodi sono le caselle e sono in numero di 100 (o genericamente di $ m\cdot n $) e gli archi sono i collegamenti fra le caselle e sono descritti dalle regole delle mosse possibili; con questo approccio, il quesito sulla risolvibilità diventa:
un grafo così definito (cioè che ha per nodi gli interi fino a 100, uniti da archi nel modo determinato dalle mosse possibili) è hamiltoniano?
Lo stesso si può fare per la scacchiera generica, scrivendo le mosse generiche con i vincoli generici (ora non ho volgia di farlo, ma è semplice partendo da qello che ho fatto per 10X10).
Se la risposta è si, allora il gioco è possibile, altrimenti è impossibile.
Ora si tratta di rispondere...