Scacchiere a caso
Scacchiere a caso
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 ...
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
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
Spero di non aver scritto boiate assurde
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
Spero di non aver scritto boiate assurde
"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]
[quote="julio14"]
jordan è in realtà l'origine e il fine di tutti i mali in [tex]\mathbb{N}[/tex][/quote]
Re: Scacchiere a caso
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
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}$
$\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
1Cor 13:2
"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102
Re: Scacchiere a caso
Uh già, per distrazione ho contato solo i modi di andare dal vertice in basso a sinistra, a quello in alto a destraEvaristeG ha scritto:Per n=2 il tuo conto fa 1/8, ma ci sono 3 scacchiere valide 2x2, quindi dovrebbe fare 3/16.
"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]
[quote="julio14"]
jordan è in realtà l'origine e il fine di tutti i mali in [tex]\mathbb{N}[/tex][/quote]
Re: Scacchiere a caso
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 spiegatoiademarco ha scritto:Uh già, per distrazione ho contato solo i modi di andare dal vertice in basso a sinistra, a quello in alto a destraEvaristeG ha scritto:Per n=2 il tuo conto fa 1/8, ma ci sono 3 scacchiere valide 2x2, quindi dovrebbe fare 3/16.
"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
1Cor 13:2
"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102
Re: Scacchiere a caso
Secondo me anche tu ti perdi dei casi (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 Già per $n=3$ falla.
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 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
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
Re: Scacchiere a caso
Bon,dario2994 ha scritto:Secondo me anche tu ti perdi dei casi (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 Già per $n=3$ falla.
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
1Cor 13:2
"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102
Re: Scacchiere a caso
Qui ci sta un LOL giganteMist ha scritto:Bon,dario2994 ha scritto:Secondo me anche tu ti perdi dei casi (e mi hai pure fregato il bon iniziale )
correggerò...
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
Re: Scacchiere a caso
No, non ti sei spiegatoMist ha scritto: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 spiegatoiademarco ha scritto:Uh già, per distrazione ho contato solo i modi di andare dal vertice in basso a sinistra, a quello in alto a destraEvaristeG ha scritto:Per n=2 il tuo conto fa 1/8, ma ci sono 3 scacchiere valide 2x2, quindi dovrebbe fare 3/16.
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
"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]
[quote="julio14"]
jordan è in realtà l'origine e il fine di tutti i mali in [tex]\mathbb{N}[/tex][/quote]
Re: Scacchiere a caso
@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
$${ 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
LOL Le parole non so per quale ASSURDO 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 XDEvaristeG 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
"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]
[quote="julio14"]
jordan è in realtà l'origine e il fine di tutti i mali in [tex]\mathbb{N}[/tex][/quote]