Newsgroup: it.hobby.enigmi
Titolo: Rook&chessboard

(Saranno i turisti,sarà la globalizzazione,ma si sente parlare solo 
l'inglese per strada...do you? ):-/ mi adatto)
Una rook(torre) si trova in una casella della 
chessboard(scacchiera)8x8:qual è la probabilità che vi ritorni?E il 
numero medio di mosse?
On(acceso)-Off(spento)

 ha scritto nel messaggio
news:MPG.15bd0fbee...@news.inwind.it...

So che su questi problemi farei meglio a tacere,
ma visto che c' entrano gli scacchi, mi accingo
all' ennesima figuraccia...
Spoiler
Spoiler
Spoiler
Dopo la prima mossa puo' tornarci in una mossa
sola, avendo pero' altre 13 mosse diverse
possibili
Dopo la seconda mossa deve tornarci in 2 mosse ma
prima deve andare in una delle due colonne  X,Y
che determinano la posizione originale...per
cui... beh... direi...
"AIUTOOOOOOOOOOOOOOOOOOOOOOOOOO!!!!!"
lo sapevo che dovevo lasciar perdere subito  ;-)
comunque uno dei fattori per determinare la
probabilita' e' 1/14 ...
(che genio!)
ciao
fulvio

Buongiorno, Onoff ha scritto:

Supponiamo che ad ogni mossa la torre si muova casualmente in una delle due
direzioni di un numero casuale non nullo di caselle, se n e' l'indice che
numera le mosse, chiamiamo P(n) la probabilita' che la torre sia ritornata
nella casella di partenza alla mossa n-esima e quindi termini il moto, Q1(n)
quella che una delle sue due coordinate sia diversa da quella iniziale,
Q2(n) quella che entrambe le coordinate siano distinte da quelle iniziali.
Se la torre ritorna nella casa iniziale alla mossa n, alla mossa (n-1) una
sola delle sue coordinate era distinta da quella di partenza, e questo
avviene con probabilita' Q1(n-1), inoltre la probabilita' di ottenere le
coordinate iniziali in queste condizioni e' 1/14, poiche' ci sono due scelte
per la direzione, e 7 per lo spostamento in una direzione fissata, quindi si
ha P(n) = Q1(n-1) / 14.
Analogamente, considerando i possibili casi, si ottiene:
Q1(1) =1,   Q2(1) = 0
Q2(n) = Q1(n-1) / 2 + Q2(n-1) * 6 / 7
Q1(n) = Q1(n-1) * 3 / 7 + Q2(n-1) / 7
Abbiamo quindi un sistema lineare che ci da' Q1(n) e Q2(n) in funzione di
Q1(n-1) e Q2(n-1), risolvendolo otteniamo Q1(n) e quindi, posto a =
SQRT(23), se n>1:
P(n) = [(9+a)^(n-2)*(a-3)/2 + (9-a)^(n-2)*(3+a)/2] / a / 14^(n-1),
e calcolando la media, <n> = 64.
Ciao
--
Giorgio Bibbiani
Per rispondere togliere la h nell'indirizzo e-mail.

#include "Onoff.h"

La scacchiera e' vuota, piena o mezza vuota? 
---
Blackstorm
*Vicario d'Armi di idf*
    .--.     Tittums e' il nostro gatto, ed ha le dimensioni 
   |o_o |    di un rotolo di soldini. Inarcava la schiena
   |:_/ |    e bestemmiava come uno studente in medicina. 
  //   \ \   (Jerome Klapka Jerome)  
 (|     | )  E da oggi anche su ICQ!
/'_   _/`\   UIN 116647346 (nick: blacks)
___)=(___/

...

E io sono un po' Sat (saturazione) hai presente un transistor mal
polarizzato? (Ho Elettronica fra due giorni)
comunque...
:
:
:
:
:
:
:
:
:
:
:
:
:
:
La prob. che torni è del 100% e ci metterà 27.25 mosse
tonde tonde.
E già che c'ero, volendo raggiungere una certa casella
a partire da un'altra riga e colonna ce ne vorrebbero 28,
mentre a partire dalla stessa riga o colonna solo 26.25.
Calcolati tutti insieme con un diagramma degli stati.
Ciao
Andrea

 mentre a partire dalla stessa riga o colonna solo 26.25.
63.
Ciao
Andrea

 polarizzato? (Ho Elettronica fra due giorni)
In culo alla balena!!(Si sta molto più larghi,comodi e al caldo che tra 
le fauci di un lupo;).Ma allora sei un Ing.?Credevo fossi un fisico o un 
matemat.!Ti do un consiglio(non ne capisco un'H di elettronica):prima di 
polarizzarti in diretta o in inversa,controlla di essere On,altrimenti 
sei Off e devi inserire la spina per la "corente".
Onov (alla russa)

 
Non fare gesti inconsulti!L'altra sera ho provato anch'io a suicidarmi 
con il taglia-unghie,ma si soffre troppo.Allora mi sono tagliato i 
capelli e devo dire che non ho sentito alcun dolore e dopo ho provato una 
piacevole sensazione di fresco e siccome mi sentivo bene c'ho bevuto su 
un po' di moscato e mi č venuta fame e me so'sbafato un cannolo stracolmo 
de ricotta e mo' perņ devo scappa' al bagno!Tutto per spirito di 
imitazione!
Onov (alla russa)

#include "Andrea Artesiani.h"

Stiamo parlando di media, vero?
Non so perche' ma mi sembrano piu' plausibili le prime risposte...


Tutto per spirito di  imitazione!
Di Fiorello quando fa Califano?
:-)
PS- Se gioco io comunque la torre ci torna alla
seconda mossa! Ho vinto!
ciao thanks
fulvio

 
Stiamo parlando di media, vero?
Non so perche' ma mi sembrano piu' plausibili le prime risposte...
Fidati, sono giuste le seconde: se hai una torre libera di
muoversi a caso su una scacchiera 8x8 vuota, considera
che una volta che è finita su una riga e colonna diversa
da quella iniziale ci sono 12 prob su 14 che ci resti ancora...
Ciao
Andrea

 siano distinte da quelle iniziali.
Qualche tempo fa Paolo propose un quesito analogo, chiedeva proprio le
probabilità che dopo n mosse la torre fosse al punto di partenza. Il thread
si chiamava "Torre" e tentammo anche di risolverlo con la Donna al posto
della Torre.
Proposi di chiamare A la casella di partenza, B quelle a portata di torre, e
C le
altre
 _ _ _ _ _ _ _ _
|     | |       |
| C   |B|   C   |
|_ _ _|_|_ _ _ _|
|_B_ _|A|_ _B_ _|
|     | |       |
| C   |B|   C   |
|     | |       |
|_ _ _|_|_ _ _ _|
La matrice delle transizioni è
 \   A  |   B  |   C  |
-+------+------+------+
A|   0  |14/14 |   0  |
-+------+------+------+
B| 1/14 | 6/14 | 7/14 |
-+------+------+------+
C|   0  | 2/14 |12/14 |
-+------+------+------+
Con questa tabella abbiamo le probabilità di andare da uno stato ad un altro
in una mossa, moltiplicandola per se stessa ricaviamo le probabilità in due
passi e così via. Ovviamente il prodotto converge (bastano una dozzina di
iterazioni) a
 \   A  |   B  |   C  |
-+------+------+------+
A| 1/64 |14/64 |49/64 |
-+------+------+------+
B| 1/64 |14/64 |49/64 |
-+------+------+------+
C| 1/64 |14/64 |49/64 |
-+------+------+------+
Perché dopo infiniti passi mi sono dimenticato da dove provenivo, e tutte le
caselle sono egualmente probabili. Quindi la probabilità di trovarsi,
partendo da B, dopo infiniti passi in C (che è uguale alla probabilità di
arrivarci partendo da A o da C), vale 49/64 perché 49/64 sono le caselle
marcate C.
Se cerchiamo le medie dei tempi di primo approdo in una casella specifica,
le cose sono abbastanza semplici:
Chiamiamo x=E[A] la media dei passi necessari a tornare nella casa di
partenza, y=E[B] la media dei passi necessari, partendo da A, ad arrivare in
una specifica casa del gruppo B (e viceversa), e z=E[C] l'analoga media per
le case del gruppo C.
Si avrà:
x = 1 + y
perché ci vuole un passo per raggiungere la zona B, dopodiché la casella
"target" è in zona B rispetto alla casella corrente, e quindi ci vorranno y
passi per raggiungerla.
y = 1 + 6/14*y + 7/14*z
perché se parto da una casa del gruppo B e devo raggiungere A, dopo un passo
6 volte su 14 staro' ancora in B (e quindi mediamente serviranno altri y
passi), 7 su 14 starò in C (altri z passi) e 1 su 14 starò proprio in A
(altri... 0 passi).
Analogamente:
z = 1 + 2/14*y + 12/14*z
Il sistema si risolve in due minuti e fornisce:
x = 64
y = 63
z = 70
Ciao, Silv:o)

Buongiorno, Silvio Sergio ha scritto:
[cut]

Non conoscevo questa dimostrazione, e' elegante e decisamente piu' semplice
della mia nel calcolo del numero medio di mosse.
Riguardo alle probabilita' di arrivo mi sembra che le due dimostrazioni
siano analoghe
anche se non immediatamente equivalenti, infatti moltiplicando la matrice di
transizione (n - 1) volte per se stessa si ottiene la probabilita' che alla
n-esima mossa la torre si venga a trovare in una posizione A o B o C
indipendentemente dal percorso seguito, mentre io calcolando P(n), Q1(n) e
Q2(n) cercavo la probabilita' che occupasse una posizione di tipo A o B o C,
senza essere passata precedentemente per A, cioe' P(n) e' la probabilita' di
primo arrivo in A, e infatti P(n) -> 0 per n-> infinito.


 
E' il mio secondo plagio allora!Non chiedo più nulla....per un po'!
Onononononoff

 
Uh, ora e' chiaro...
Pensavo si riferisse ad una partita. Cioe', che il calcolo andasse fatto
su una disposizione di pezzi...


 primo arrivo in A, e infatti P(n) -> 0 per n-> infinito.
Probabilmente si possono rendere le due cose equivalenti.
Aggiungiamo uno stato che indica la fine del gioco, dopo il ritorno
definitivo in A, chiamiamolo D.
Al primo passo la matrice (M1) diventa:
 \   A  |   B  |   C  |   D  |
-+------+------+------+------+
A|   0  |14/14 |   0  |   0  |
-+------+------+------+------+
B| 1/14 | 6/14 | 7/14 |   0  |
-+------+------+------+------+
C|   0  | 2/14 |12/14 |   0  |
-+------+------+------+------+
D|   0  |   0  |   0  |   1  |
-+------+------+------+------+
Mentre per i passi successivi (matrice M2) da A non si va più in B ma solo
in D dove si resta in eterno (stato assorbente)
 \   A  |   B  |   C  |   D  |
-+------+------+------+------+
A|   0  |   0  |   0  |   1  |
-+------+------+------+------+
B| 1/14 | 6/14 | 7/14 |   0  |
-+------+------+------+------+
C|   0  | 2/14 |12/14 |   0  |
-+------+------+------+------+
D|   0  |   0  |   0  |   1  |
-+------+------+------+------+
Ora facendo il prodotto M1*M2^(n-1) si hanno le probabilità di transizione
in n passi.
La prima riga rappresenta le probabilità che partendo da A e si arrivi in A
(per la prima volta!), B, C o D dopo n passi. Anche qui si nota che alla
lunga le prime tre righe tendono a diventare uguali (perdita di memoria
sullo stato iniziale) e che la tutte le probabilità tendano a 0 (molto più
velocemente le probabilità di primo arrivo in A) tranne ovviamente l'ultima
colonna, che tende ad 1 (stato assorbente: prima o poi si finisce nel buco
nero).
Ecco la situazione dopo 100 iterazioni:
 \     A     |     B     |     C     |     D     |
-+-----------+-----------+-----------+-----------+
A|0.003123262|0.043087998|0.167953386|0.785835354|
-+-----------+-----------+-----------+-----------+
B|0.003077714|0.042459626|0.165504044|0.788958616|
-+-----------+-----------+-----------+-----------+
C|0.003427620|0.047286870|0.184320235|0.764965275|
-+-----------+-----------+-----------+-----------+
D|     0     |     0     |     0     |     1     |
-+-----------+-----------+-----------+-----------+
che mostra come dopo 100 passi ci siano ancora buone probabilità di stare
vagando in B o C, poche di tornare proprio al centesimo passo in A, ed il
78% di probabilità di aver già concluso il gioco (il massimo lo si ha
partendo da B per via della possibilità di chiudere al primo colpo, il
minimo da C).
Ciao, Silv:o)

Buongiorno, Silvio Sergio ha scritto:
[cut]

Eccellente, proprio una dimostrazione chiara, completa e istruttiva.
Ho provato a verificare se con la formula P(n) che corrisponde
all'elemento di matrice AA di cui sopra ottengo gli stessi risultati, e in
effetti si ha P(101) = 0.00312326
(nel calcolo sopra le 100 iterazioni si riferiscono evidentemente a M1
moltiplicata 100
volte per M2).
