Newsgroup: it.hobby.enigmi
Titolo: Enigma scacchiera

Abbiamo una scacchiera con X colonne e Y righe. Posizioniamo un pezzo sulla 
prima riga in alto e ad ogni mossa lo muoviamo nella riga sottostante su 
caselle adiacenti (che si toccano). Sapreste trovare una formula in X e Y 
che ci permetta di calcolare quanti possibili percorsi ci sono?
Esempio, in una scacchiera 2x2 avremo (X caselle e I percorso del pezzo) 4 
possibili percorsi:
IX IX XI XI
IX XI IX XI
Esempio, in una scacchiera 2x3 avremo (X caselle e I percorso del pezzo) 8 
possibili percorsi:
IX IX IX IX XI XI XI XI
IX IX XI XI IX IX XI XI
IX XI IX XI IX XI IX XI
Esempio, in una scacchiera 3x2 avremo (X caselle e I percorso del pezzo) 7 
possibili percorsi:
IXX IXX XIX XIX XIX XXI XXI
IXX XIX IXX XIX XXI XIX XXI
Esempio, in una scacchiera 3x3 avremo (X caselle e I percorso del pezzo) 17 
possibili percorsi:
IXX IXX IXX IXX IXX XIX XIX XIX XIX XIX XIX XIX XXI XXI XXI XXI XXI
IXX IXX XIX XIX XIX IXX IXX XIX XIX XIX XXI XXI XIX XIX XIX XXI XXI
IXX XIX IXX XIX XXI IXX XIX IXX XIX XXI XIX XXI IXX XIX XXI XIX XXI
Provate, infine, a trovare la formula quando la scacchiera è cilindrica (la 
prima colonna è comunicante con l'ultima)
Ciao

 prima colonna è comunicante con l'ultima).
Questo caso è sicuramente il caso più semplice, la casella iniziale ha X
posizioni possibili, ad ogni mossa scegliamo tra 3 diverse caselle e quindi,
i percorsi diversi, dovrebbero essere:
X*3^(Y-1)
perchè abbiamo Y-1 mosse.
Per il caso di scacchiera piana non saprei ancora una formula generale, data
una scacchiera è facile numerare le caselle in maniera opportuna da ottenere
il numero di soluzioni senza disegnarle in maniera esaustiva ma non so come
generalizzare il procedimento in una formula. Per una generica scacchiera
marchio con 1 tutte le caselle della prima riga per le altre caselle procedo
a numerarle riga per riga nel seguente modo: in ogni casella scrivo la somma
delle caselle della riga superiore da cui posso giungere in quella sotto
esame. Il numero cercato è la somma dei numeri dell'ultima riga. Per esempio
per la 3x5 si ha:
 __ __ __ __ __
| 1| 1| 1| 1| 1|
|__|__|__|__|__|
| 2| 3| 3| 3| 2|
|__|__|__|__|__|
| 5| 8| 9| 8| 5|
|__|__|__|__|__|
Tot=5+8+9+8+5
GaS
P.S.: Altri messaggi che ho inviato oggi tramite fastweb non mi vengono
visualizzati su google e neanche su libero. Sono delle risposte a
"Origametrie" di Dario Uri e un nuovo problema dal nome "Multipli di 2004".
Voi li vedete? Anche il fatto che questo problema sia stato inviato due
volte da Ottavio Vargiu mi fa sospettare che ci sia qualche cosa che non va
con i newsreader. Ho provato a cambiare server, vediamo che cosa succede
--------------------------------
Inviato via 
http://arianna.libero.it/usenet/

 Voi li vedete?
Io sě, perň ho anch'io Fastweb :)
-- 
Alessio90 "the Sproloquiator"
Proud poster in: it.test - it.hobby.enigmi - it.hobby.fantasport
Di tutte le cose sicure la piů certa č il dubbio. (Bertolt Brecht)

 Voi li vedete?
Con OE non trovo né il thread "Origametrie" nè "Multipli di 2004".
Ho provato su google, niente.
ciao
paolo



Allora è un problema di Fastweb... però voi vedete i miei post, non è vero?
-- 
Alessio90 "the Sproloquiator"
Proud poster in: it.test - it.hobby.enigmi - it.hobby.fantasport
Chi sogna di giorno conosce molte cose che sfuggono a chi sogna solo di
notte. (Edgar Allan Poe)

 Allora č un problema di Fastweb... perň voi vedete i miei post, non č
vero?
Su libero e su google i tuoi post compaiono mentre i miei inviati con
fastweb non ci sono. Misteri di internet......
Chi ci capisce č bravo, per ora adopero libero, piů scomodo ma, sembra, piů
sicuro; magari domani riprovo.
Grazie a tutti dei feedback,
GaS



Io non vedo alcun thread Origametrie. Vedo i tuoi multipli di 2004, con ora
23.53, quindi immagino non siano quelli cui ti riferisci in questo
messaggio. Il mio server è 
news.individual.net
.
Ciao :-)
Giorgio

 percorsi ci sono?
I casi fino a X=5 sono stati abbondantemente studiati.
Basta trovare le soluzioni a mano col metodo di GaS per i primi 4-5 Y e dare
in pasto la sequenza all'enciclopedia delle sequenze intere. Ci sono formule
chiuse fino a X=5, roba con le radici tipo l'espressione chiusa per i numeri
di Fibonacci. In effetti non sorprende, visto che le relazioni sono
calcolabili ricorsivamente con uno schema fibonacci-like.
-- 
Ciao, Silv:o)

 sicuro; magari domani riprovo.
Se ti puň interessare il nocciolo della questione sta nella seconda parte
del Message-ID: i messaggi con "tornado." non sono ricevuti da tutti,
mentre gli altri sě.
-- 
Alessio90 "the Sproloquiator"
Proud poster in: it.test - it.hobby.enigmi - it.hobby.fantasport
Il paradiso lo preferisco per il clima, l'inferno per la compagnia. (Mark
Twain)

...

E quindi, non c'è nessuna formuna?

 E quindi, non c'è nessuna formuna?
Mi pareva di aver già detto.
Io ho usato lo schema proposto da GaS per trovare le soluzioni per i primi
Y. Per esempio, per Y=3 si ottiene facilmente (per i più pigri c'è excell ;)
 1   1   1  somma  3
 2   3   2  somma  7
 5   7   5  somma 17
12  17  12  somma 41
29  41  29  somma 99
.   .   .
Poi sono andato su 
http://www.research.att.com/~njas/sequences/
 (The On-Line
Encyclopedia of Integer Sequences) ho inserito 3,7,17,41,99 e ho premuto
Search.
Tra le tante cose che escono fuori, tutte moltissimo interessanti, c'è anche
formula: a(n) = ((1-Sqrt[2])^n + (1+Sqrt[2])^n) /2.
Fai la stessa cosa per Y=4 e poi continui fino a che ... ti dice che la
sequenza non è presente.
A quel punto hai due strade: ti accontenti, come me, e dici "i primi termini
sono studiati" oppure invii la sequenza mancante, ottenuta dal foglio excel,
magari commentata, magari dicendo a cosa serve. Magari te la pubblicano.
Magari no.
-- 
Ciao, Silv:o)