Pagina 1 di 1

Scacchiere a caso

Inviato: 21 ago 2011, 03:39
da EvaristeG
Prendiamo una griglia $n\times n$. Qual è la probabilità che, colorando a caso ogni casella di nero o di bianco, ci sia un percorso di sole caselle nere crescente dal vertice in basso a sinistra a quello in alto a destra?

un percorso è crescente se è fatto solo di mosse in alto o a destra

Bonus: Qual è la probabilità di un percorso di sole caselle nere monotono (crescente o decrescente) tra due vertici opposti?

EDIT: tnx ma_go ... all'inizio volevo scriverlo cancellando le caselle ...

Re: Scacchiere a caso

Inviato: 21 ago 2011, 19:32
da iademarco
I casi totali sono $ 2^{n^2} $
I casi favorevoli possiamo assimilarli al numero di parole di $ 2n-2 $ lettere, formate solo dalle lettere N (nord) ed E (est), in cui ciascuna lettera non si ripeta più di $ n-1 $ volte.
I casi sono quindi: $ 2^{2n-2} - 2[{2n-2 \choose n}-{2n-2 \choose n+1}-... -{2n-2 \choose 2n-2}] $, che è uguale a $ 2^{2n-2} - 2[2^{2n-3} - {2n-3 \choose n-1}] $.
Quindi la probabilità è $ 2{2n-3 \choose n-1} / 2^{n^2} $
Ciò dovrebbe valere per n>1, ma il caso n=1 credo possa essere sorvolato :P
Spero di non aver scritto boiate assurde :roll:

Re: Scacchiere a caso

Inviato: 21 ago 2011, 20:50
da EvaristeG
Per n=2 il tuo conto fa 1/8, ma ci sono 3 scacchiere valide 2x2, quindi dovrebbe fare 3/16.

Re: Scacchiere a caso

Inviato: 21 ago 2011, 20:53
da Mist
Bon, chiamo $b_{n}$ il numero di modi in cui si può costruire un percorso monocromatico nero dalla casella in basso a inistra a quella in alto a destra su una scacchiera $n\times n$. Aggiungo una riga in alto e una colonna a destra e provo quindi a calcolare $b_{n+1}$. Ci sono tre modi di colorare le quattro caselle più in alto a destra:

$\begin{matrix} \mbox{nero} & \mbox{nero} \\ \mbox{nero} & \mbox{nero} \end{matrix}$

$\begin{matrix} \mbox{bianco} & \mbox{nero} \\ \mbox{nero} & \mbox{nero} \end{matrix}$

$\begin{matrix} \mbox{nero} & \mbox{nero} \\ \mbox{nero} & \mbox{bianco} \end{matrix}$

Per ognuno di questi tre casi posso colorare le altre caselle della nuova riga e della nuova colonna in $2^{2n-2}$ modi e quindi $b_{n+1} = b_{n}\cdot 2^{2n-2}\cdot 3$. Facendo un po' di calcoli quindi si ha che $\displaystyle b_{n+1} = b_1\cdot 2^{2\frac{n(n-1)}{2}}\cdot 3^n = 2^{n(n-1)}\cdot 3^n $

I casi possibili sono ovviamente $2^{(n+1)^2}$ e quindi la probabilità su una scacchiera di $n+1$ caselle è pari a $\displaystyle \frac{1}{2}\left( \frac{3}{8} \right) ^n$

Quindi, tanto per scongiurare eventuali errorini di calcolo durante il controllo dei casi piccoli (che miracolosamente escono), la probabilità (lo scrivo bene ora) che su una scacchiera di $n\times n$ caselle colorate casualmente di nero o bianco si venga a formare un percorso monotono da quella in basso a sinistra a quella in alto a destra è pari a $\displaystyle \frac{1}{2}\left( \frac{3}{8} \right) ^{n-1}$

Re: Scacchiere a caso

Inviato: 21 ago 2011, 21:06
da iademarco
EvaristeG ha scritto:Per n=2 il tuo conto fa 1/8, ma ci sono 3 scacchiere valide 2x2, quindi dovrebbe fare 3/16.
Uh già, per distrazione ho contato solo i modi di andare dal vertice in basso a sinistra, a quello in alto a destra

Re: Scacchiere a caso

Inviato: 21 ago 2011, 21:14
da Mist
iademarco ha scritto:
EvaristeG ha scritto:Per n=2 il tuo conto fa 1/8, ma ci sono 3 scacchiere valide 2x2, quindi dovrebbe fare 3/16.
Uh già, per distrazione ho contato solo i modi di andare dal vertice in basso a sinistra, a quello in alto a destra
nono, il tuo errore mi sa che non è quello (che è esattamente quello che dice il problema XD) ma piuttosto credo nel modo in cui fai il conteggio. Tu usi infatti un approccio che io definisco "a freccie", simile ad un conteggio alla catalan, ma così non conti bene anche i casi in cui i percorsi che portano dalla casella in basso a sinistra a quella in alto a destra sono due possibili, o comunque in numero maggiore di uno... Insomma, ti perdi dei casi, non so se mi sono spiegato :wink:

Re: Scacchiere a caso

Inviato: 21 ago 2011, 21:25
da dario2994
Secondo me anche tu ti perdi dei casi :roll: (e mi hai pure fregato il bon iniziale :? )
Dai per scontato che la colorazione per $n+1$ caselle sia anche una colorazione per $n$ caselle... che è falso... funziona per $n=1,2$ proprio perchè in questi 2 rari casi è vero :wink: Già per $n=3$ falla.

Re: Scacchiere a caso

Inviato: 21 ago 2011, 21:28
da Mist
dario2994 ha scritto:Secondo me anche tu ti perdi dei casi :roll: (e mi hai pure fregato il bon iniziale :? )
Dai per scontato che la colorazione per $n+1$ caselle sia anche una colorazione per $n$ caselle... che è falso... funziona per $n=1,2$ proprio perchè in questi 2 rari casi è vero :wink: Già per $n=3$ falla.
Bon,

correggerò...

Re: Scacchiere a caso

Inviato: 21 ago 2011, 21:34
da <enigma>
Mist ha scritto:
dario2994 ha scritto:Secondo me anche tu ti perdi dei casi :roll: (e mi hai pure fregato il bon iniziale :? )
Bon,

correggerò...
Qui ci sta un LOL gigante :mrgreen:

Re: Scacchiere a caso

Inviato: 21 ago 2011, 21:45
da iademarco
Mist ha scritto:
iademarco ha scritto:
EvaristeG ha scritto:Per n=2 il tuo conto fa 1/8, ma ci sono 3 scacchiere valide 2x2, quindi dovrebbe fare 3/16.
Uh già, per distrazione ho contato solo i modi di andare dal vertice in basso a sinistra, a quello in alto a destra
nono, il tuo errore mi sa che non è quello (che è esattamente quello che dice il problema XD) ma piuttosto credo nel modo in cui fai il conteggio...Insomma, ti perdi dei casi, non so se mi sono spiegato :wink:
No, non ti sei spiegato :mrgreen:
Potrei sbagliare, ma forse non hai ben inteso cosa ho contato io...solo i modi di andare dal vertice in basso a sinistra a quello in alto a destra, senza tener conto delle colorazioni, infatti per n=2, i modi sono solo 2 e non 3, e mi pare funzioni anche per n maggiori...insomma ho fatto un altro problema :P

Re: Scacchiere a caso

Inviato: 21 ago 2011, 22:40
da EvaristeG
@iademarco: cmq non ho capito come conti le parole... hai n-1 N e n-1 E e devi anagrammarle (che se vuoi equivale a scegliere quale sottoinsieme delle 2n-2 lettere è fatto da sole E), il che ha una formula semplice:
$${ 2n-2 \choose n-1}$$
sia come anagramma che come scelta di lettere. Il tuo complicato calcolo ha lo stesso risultato:
$${2n-3\choose n-1}={2n-3\choose n-2}$$
quindi
$$2{2n-3\choose n-1}={2n-3\choose n-1}+{2n-3\choose n-2}={2n-2\choose n-1}\;.$$
Ma la strada intrapresa mi sembra alquanto complicata XD

Re: Scacchiere a caso

Inviato: 22 ago 2011, 00:07
da iademarco
EvaristeG ha scritto:@iademarco: cmq non ho capito come conti le parole... hai n-1 N e n-1 E e devi anagrammarle...il che ha una formula semplice
LOL Le parole non so per quale ASSURDO :shock: motivo le ho contate così: totale delle parole formate da N ed E, anche 2n-2 N o 2n-2 E, meno tutte quelle che non andavano bene XD