Scacchiere a caso

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
EvaristeG
Site Admin
Messaggi: 4777
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Scacchiere a caso

Messaggio da EvaristeG » 21 ago 2011, 03:39

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 ...

Avatar utente
iademarco
Messaggi: 264
Iscritto il: 10 dic 2008, 22:12
Località: Campobasso

Re: Scacchiere a caso

Messaggio da iademarco » 21 ago 2011, 19:32

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:
"Il lemma fondamentale: se vi danno un esercizio è perchè potete farlo; se potete farlo è perchè è proprio facile; se è proprio facile è perchè servono delle cose che sapete; le cose che sapete sono pochissime, quindi avete da cercare in un insieme piccolissimo di cose" Michele Barsanti


[quote="julio14"]
jordan è in realtà l'origine e il fine di tutti i mali in [tex]\mathbb{N}[/tex][/quote]

EvaristeG
Site Admin
Messaggi: 4777
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: Scacchiere a caso

Messaggio da EvaristeG » 21 ago 2011, 20:50

Per n=2 il tuo conto fa 1/8, ma ci sono 3 scacchiere valide 2x2, quindi dovrebbe fare 3/16.

Mist
Messaggi: 542
Iscritto il: 01 gen 2011, 23:52
Località: Provincia di Milano

Re: Scacchiere a caso

Messaggio da Mist » 21 ago 2011, 20:53

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}$
Ultima modifica di Mist il 21 ago 2011, 21:19, modificato 1 volta in totale.
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2

"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102

Avatar utente
iademarco
Messaggi: 264
Iscritto il: 10 dic 2008, 22:12
Località: Campobasso

Re: Scacchiere a caso

Messaggio da iademarco » 21 ago 2011, 21:06

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
"Il lemma fondamentale: se vi danno un esercizio è perchè potete farlo; se potete farlo è perchè è proprio facile; se è proprio facile è perchè servono delle cose che sapete; le cose che sapete sono pochissime, quindi avete da cercare in un insieme piccolissimo di cose" Michele Barsanti


[quote="julio14"]
jordan è in realtà l'origine e il fine di tutti i mali in [tex]\mathbb{N}[/tex][/quote]

Mist
Messaggi: 542
Iscritto il: 01 gen 2011, 23:52
Località: Provincia di Milano

Re: Scacchiere a caso

Messaggio da Mist » 21 ago 2011, 21:14

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:
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2

"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: Scacchiere a caso

Messaggio da dario2994 » 21 ago 2011, 21:25

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.
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Mist
Messaggi: 542
Iscritto il: 01 gen 2011, 23:52
Località: Provincia di Milano

Re: Scacchiere a caso

Messaggio da Mist » 21 ago 2011, 21:28

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ò...
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2

"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102

Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

Re: Scacchiere a caso

Messaggio da <enigma> » 21 ago 2011, 21:34

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:
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)

Avatar utente
iademarco
Messaggi: 264
Iscritto il: 10 dic 2008, 22:12
Località: Campobasso

Re: Scacchiere a caso

Messaggio da iademarco » 21 ago 2011, 21:45

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
"Il lemma fondamentale: se vi danno un esercizio è perchè potete farlo; se potete farlo è perchè è proprio facile; se è proprio facile è perchè servono delle cose che sapete; le cose che sapete sono pochissime, quindi avete da cercare in un insieme piccolissimo di cose" Michele Barsanti


[quote="julio14"]
jordan è in realtà l'origine e il fine di tutti i mali in [tex]\mathbb{N}[/tex][/quote]

EvaristeG
Site Admin
Messaggi: 4777
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: Scacchiere a caso

Messaggio da EvaristeG » 21 ago 2011, 22:40

@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

Avatar utente
iademarco
Messaggi: 264
Iscritto il: 10 dic 2008, 22:12
Località: Campobasso

Re: Scacchiere a caso

Messaggio da iademarco » 22 ago 2011, 00:07

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
"Il lemma fondamentale: se vi danno un esercizio è perchè potete farlo; se potete farlo è perchè è proprio facile; se è proprio facile è perchè servono delle cose che sapete; le cose che sapete sono pochissime, quindi avete da cercare in un insieme piccolissimo di cose" Michele Barsanti


[quote="julio14"]
jordan è in realtà l'origine e il fine di tutti i mali in [tex]\mathbb{N}[/tex][/quote]

Rispondi