scacchiere da completare

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
blackdie
Messaggi: 34
Iscritto il: 07 dic 2005, 18:26

scacchiere da completare

Messaggio da 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
Messaggi: 106
Iscritto il: 14 mag 2008, 19:43

Messaggio da 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
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da 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)
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
blackdie
Messaggi: 34
Iscritto il: 07 dic 2005, 18:26

Messaggio da blackdie »

eli9o ha scritto: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?
Avatar utente
Fedecart
Messaggi: 522
Iscritto il: 09 mar 2008, 22:49
Località: Padova

Messaggio da 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)³²¹º]¼+½=¾
Messaggi: 849
Iscritto il: 22 ott 2006, 14:36
Località: Carrara/Pisa

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

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

.
blackdie
Messaggi: 34
Iscritto il: 07 dic 2005, 18:26

Messaggio da 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 8) ?) vedi come funzionano le regole.!
Avatar utente
Gargantua
Messaggi: 20
Iscritto il: 03 set 2006, 22:24
Località: Sassari

Messaggio da 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... :shock:

Comunque proviamoci! :P
Ultima modifica di Gargantua il 28 mag 2008, 18:02, modificato 1 volta in totale.
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph »

Gargantua ha scritto: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...
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da 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?).
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Avatar utente
Gargantua
Messaggi: 20
Iscritto il: 03 set 2006, 22:24
Località: Sassari

Messaggio da Gargantua »

fph ha scritto:
Gargantua ha scritto: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! :cry: Grazie per avermelo fatto notare! :D
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... :?
Rispondi