Newsgroup: it.hobby.enigmi
Titolo: Il Gioco delle cavallette

Si dispongano su una fila lunga 7 caselle, 3 pedine nere da una parte e 3 pedine bianche
dall'altra con in mezzo una casella vuota.
L'obbiettivo e' di far avanzare le pedine in modo da farle scambiare di posto.
Le regole sono che si puo' avanzare di una sola casella alla volta e si puo' saltare
come nella dama.
Un esempio vale piu' di mille parole :
1) X X X _ O O O   (stato iniziale)
2) X X _ X O O O   (avanzamento nero)
3) X X O X _ O O   (salto della cavalletta bianca)
4) X X O X O _ O
5) X X O X O O _   ci si e' bloccati (deadlock), allora si riparte daccapo!
Allora domando :
- Esiste una soluzione ?
- E' unica ?
- A questa si risponde al volo : se esiste una soluzione, quante mosse occorrono ?
- generalizzare le precedenti al caso in cui ci siano B pedine bianche e N nere.
Ciao,
	Crios.

Ciao,	Crios.
Ciao Crios,
Hai proposto un giochino che mi incuriosisce. Ci sto ancora pensando ma ho 
bisogno che tu mi chiarisca se ho ben capito: le pedine non possono tornare 
indietro (cioe' le bianche verso destra e le nere verso sinistra). Confermi?
Ciao, Antonio
_________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at 
http://www.hotmail.com
.
Share information about yourself, create your own public profile at 
http://profiles.msn.com
.
--
Posted from [202.84.239.6] by way of 
f128.law3.hotmail.com
 [209.185.241.128] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 - generalizzare le precedenti al caso in cui ci siano B pedine bianche e N
nere.
Aspetta un'attimo e ti dico anche questa(forse)

 Aspetta un'attimo e ti dico anche questa(forse)
per il momento posso solo dirvi che, nel caso in cui ci sia lo stesso numero
(x) di pedine bianche e nere, il numero di mosse necessarie dovrebbe essere
x^2+2x
cioč si muove 1 volta la bianca, 2 volte le nere, 3 volte le bianche... x
volte quello che capita(bianche se x č pari, nere se x č dispari), x volte
l'altro colore, x volte l'altro colore(non č una ripetizione erronea), x-1
volte l'altro, x-2 volte l'altro... 1 volta la bianca rimanente ed il gioco
č fatto.

forse ce l'ho fatta:
innanzitutto anzichè utilizzare N e B per individuare le nere e le bianche
utilizziamo m ed M per individuare il numero delle pedine di numero
inferiore ed M per le altre(es. 4 bianche e 6 nere: m = 4 ed M = 6)
il numero minimo di mosse, se non vado errato è:
caso 1: M - m è pari) (m^2+m)/2+M
caso 2: M - m è dispari) (m^2+3m)/2+M
vi chiedo scusa in anticipo se è errato ma non ho avuto il tempo di
controllare

 indietro (cioe' le bianche verso destra e le nere verso sinistra). Confermi?
Si`, confermo.


Gia`, non e` giusto.
Psss... non puoi dire altro sull`unicita` ?
Visto che ormai l`hai fatto notare, l`unicita` va proprio intesa, diciamo cosi`...
`a meno di casi essenzialmente uguali`.

Sempre con spirito didattico.
E' un solitario  ben conosciuto da quando Eduard Lucas ha dedicato un
paio di pagine del suo "Recreations Mathematiques"  1882, vol.II
pag.141-143 col titolo "Un jeu de pions".
Cominciando con n gettoni bianchi ed n neri, si trova, (ad es. per
induzione), che:
Il num. di posizioni considerando inizio e fine, e' (n+1)^2
Percio' il num. di mosse e' (n+1)^2-1
di cui 2n sono passi e n^2 sono salti.
Recentemente l'editore della rivista americana Games, Will Shortz, ha
trovato un riferimento precedente  American Agriculturist (jun 1867),
che lo presenta come Spanish Puzzle.
:) dario

 di cui 2n sono passi e n^2 sono salti.
Solo per amore di completezza.
Se si considerano N pedine nere e B bianche, dal momento che le bianche
non si scavalcano mai, per arrivare alla fine devono avanzare di N+1
caselle ognuna, idem per le nere :
caselle_attraversate = B(N+1) + N(B+1) = 2BN+B+N
essendoci B*N incroci, che riducono dello stesso valore il numero di mosse,
Mosse = BN+B+N
di cui BN sono salti e di conseguenza B+N avanzamenti, che come numero di
stati, con inizio e fine, si puo` scrivere (B+1)(N+1).
Discutere l`unicita` e` una cosa terrificante e la ometto (l`ho fatto
durante le vacanze), dico solo che esiste un caso inatteso in cui questa
non vale.
Crios.