Problemi su probabilita e non solo (non facilissimi)

[kobeilprofeta]

Vi propongo alcuni problemi sul calcolo combinatorio - probabilità e non solo.
Alcuni a me sembrano abbastanza insidiosi. (dato che li ho scritti io non ho delle soluzioni "ufficiali" per tutti ma vi posso dire quello che è venuto a me).


1) Calcolare le possibili permutazioni nelgioco del 15.

2) Dimostrare che la somma continua delle cifre di un numero (es: 999=9+9+9=27=2+7=9 oppure 545=5+45=50=5+0=5) chiamata $S(x)$ è uguale a $x mod 9$.
NB: non importa se le cifre si sommano singolarmente o a coppie, ecc...)

3) Trovare e dimostrare quanto vale $lim_(n rightarrow infty) P(X)$ dove P(X) è la probabilità che accada almeno una volta dopo $n$ tentativi un evento con probabilità $1/n$.

[fu^2]

alcune domande per capire un attimo meglio

nel secondo cosa vuol dire che le cifre si possono "sommare a coppie"?...

nel terzo tu vuoi sapere la probabilità che al $n+1$-tentativo si verifichi un evento con probabilità $1/n$? Oppure che dall'istante $n+1$ in poi si verifichi un evento?...
E quell'evento ha probabilità $1/n$ di verificarsi e $1-1/n$ di non verificarsi?

[kobeilprofeta]

Nel secondo intendo che sommi le cifre come vuoi
Es: 3421
Può essere:
3+4+2+1=10. 1+0=1
oppure
342+1=343. 3+43=46. 4+6=10. 1+0=1

Nel terzo è semplice: intendo per esempio la probabilità che esca almeno un sei lanciando 6 volte un dado (in questo caso $n=6$) oppure che con due lanci di una moneta esca almeno una volta testa ($n=2$). L'importante è che ci siano $n$ tentativi, o lanci, e probabilità per ogni tentativo pari a $1/n$. Ecco ora per $n rightarrow infty$ qual è la probabilità che accada almeno una volta in $n$ tentativi?

[gygabyte017]

Per quanto riguarda il terzo, io farei:

Supponendo gli eventi indipendenti e ragionando con l'evento complementare di quello che chiedi che è più facile, la probabilità che in $n$ lanci non si verifichi mai quell'evento (che ha probabilità $1 / n$) è $(1 - 1/n)^n = ((n-1)/n)^n$.
Dobbiamo quindi calcolare $lim_{n -> oo}((n-1)/n)^n = lim_{n -> oo} e^(ln ((n-1)/n)^n) = lim_{n -> oo} e^(n ln ((n-1)/n))$.
Ora, ricordando lo sviluppo in serie di $ln(1+x)$ (sono pigro, sicuramente con i limiti notevoli o l'Hopital si fa uguale), abbiamo: $ln(1+x) = x - x^2 /2 + o(x^2)$.
E quindi:
$lim_{n -> oo} e^(n ln ((n-1)/n)) = lim_{n -> oo} e^(n ln (1 - 1/n)) = lim_{n -> oo} e^(n (-1/n - 1/n^2 + o(1/n^2)))=lim_{n -> oo} e^(-1 -1/n + o(1/n))=1/e$

Quindi la probabilità dell'evento che cercavamo è $1-1/e$.
(Sempre se non ho sbagliato i conti )

Per quanto riguarda il secondo, mi sembra carino ci voglio pensare un attimo

[Pianoth]

"kobeilprofeta":
2) Dimostrare che la somma continua delle cifre di un numero (es: 999=9+9+9=27=2+7=9 oppure 545=5+45=50=5+0=5) chiamata $S(x)$ è uguale a $x mod 9$.

Precisazione: se \(x \equiv 0 \pmod9\) allora $S(x) = 9$, non $0$ (eccetto quando $x = 0$)...
La dimostrazione del secondo è molto più semplice di quel che sembra.

[kobeilprofeta]

"gygabyte017":Per quanto riguarda il terzo, io farei:

Supponendo gli eventi indipendenti e ragionando con l'evento complementare di quello che chiedi che è più facile, la probabilità che in $n$ lanci non si verifichi mai quell'evento (che ha probabilità $1 / n$) è $(1 - 1/n)^n = ((n-1)/n)^n$.
Dobbiamo quindi calcolare $lim_{n -> oo}((n-1)/n)^n = lim_{n -> oo} e^(ln ((n-1)/n)^n) = lim_{n -> oo} e^(n ln ((n-1)/n))$.
Ora, ricordando lo sviluppo in serie di $ln(1+x)$ (sono pigro, sicuramente con i limiti notevoli o l'Hopital si fa uguale), abbiamo: $ln(1+x) = x - x^2 /2 + o(x^2)$.
E quindi:
$lim_{n -> oo} e^(n ln ((n-1)/n)) = lim_{n -> oo} e^(n ln (1 - 1/n)) = lim_{n -> oo} e^(n (-1/n - 1/n^2 + o(1/n^2)))=lim_{n -> oo} e^(-1 -1/n + o(1/n))=1/e$

Quindi la probabilità dell'evento che cercavamo è $1-1/e$.
(Sempre se non ho sbagliato i conti )

Per quanto riguarda il secondo, mi sembra carino ci voglio pensare un attimo

Il terzo è corretto, bravo!
Ora pensate agli altri due... Il secondo non ho capito se quella postata era una soluzione...in ogni caso il secondo è più di ragionamento, il primo è laborioso come calcoli

[Pianoth]

Non era una soluzione, era una precisazione (non è $x mod 9$ se $x$ è un multiplo di $9$, cioè se io prendo $81$ la somma continua è $9$, non $81 mod 9 = 0$)

[Pianoth]

Visto che nessuno risponde al secondo...

Si nota che \(10 \equiv 1\pmod{9}\) e conseguentemente \(10^k \equiv 1^k \equiv 1\pmod{9}\)... D'altra parte ogni numero in base $10$ può essere espresso con le potenze di dieci (esempio: $23048 = 2*10^4+3*10^3+0*10^2+4*10^1+8*10^0$), ovvero per ogni numero $x$ con $k$ cifre, $x = n_0*10^(k-1)+n_1*10^(k-2)+\ldots+n_(k-1)$. Unendo queste due frasi:
\(x \equiv n_0*10^{k-1}+n_1*10^{k-2}+\ldots+n_{k-1} \equiv n_0+n_1+n_2+\ldots+n_{k-1} \pmod{9}= S(x)\)
Ossia, $x mod 9 = S(x)$
Tuttavia, se $x > 0 ^^ x mod 9 = 0$, $S(x) = 9$.

[kobeilprofeta]

Dai !! Rimane solo il primo... Vediamo chi ci riesce... In questo caso io chiamerei anche Superpippone all'appello (che è molto bravo in questo genere di problemi)....

[Pianoth]

Non sono per niente bravo nei problemi di probabilità, ma ci provo:
Dando per scontata la discussione sulla parità (che tutti i matematici dovrebbero conoscere) per dimostrare che metà di tutte le permutazioni sono impossibili da risolvere, il numero delle possibili permutazioni del gioco del 15 dovrebbe essere...

$(16!)/2 = 10461394944000$

[kobeilprofeta]

Anchio l'ho pensata come pianoth. Ma il calcolo non mi convince al 100%...

[Pianoth]

Io invece sono piuttosto sicuro del mio calcolo, la "famosa discussione sulla parità" esclude effettivamente metà delle permutazioni, perché questa discussione asserisce che il numero di inversioni deve essere pari... Poi il numero totale di permutazioni (contando anche quelle impossibili da risolvere) è dato dal totale numero di modi di ordinare tutti gli oggetti di una matrice $4 \times 4$ (dato che anche il quadratino vuoto conta), ovvero $(4*4)! = 16!$... Per ottenere quelle risolvibili basta solo dividere per $2$.

Un altro esempio in cui questo accade è per il cubo di Rubik:
Il numero totale di permutazioni è dato dal prodotto delle permutazioni degli angoli e delle permutazioni degli spigoli (i centri non si possono scambiare). Gli angoli possono essere scambiati in $8!$ modi e orientati in $3^8$ modi differenti, gli spigoli possono essere scambiati in $12!$ modi e orientati in $2^12$ modi. Ciò ci dà quindi come risultato $8!*3^8*12!*2^12 = 519024039293878272000$.
Il numero totale di permutazioni possibili è però molto più piccolo: 7 angoli possono essere orientati indipendentemente, mentre l'ultimo dipende da tali; 11 spigoli possono essere orientati indipendentemente, mentre l'ultimo dipende da tali; inoltre la parità degli angoli implica parità degli spigoli, ovvero gli spigoli possono essere orientati in $(12!)/2$ modi. Il numero quindi di permutazioni possibili è pari a $8!*3^7*(12!)/2*2^11 = 43252003274489856000$.
Questo è effettivamente il numero di permutazioni del cubo di Rubik, che puoi anche trovare facilmente su internet cercando tipo "permutazioni Rubik" (alcuni lo scrivono come $(8!*3^8*12!*2^12)/12$, ma è la stessa cosa).