Re: Estrazioni casuali
 

E' sufficiente un piccolo ragionamento.
Incominciando dalla fine (e andando a ritroso...) ;)

:hello:

Re: Estrazioni casuali
 

#393

#672

Probabilmente, i quesiti sono ...troppo semplici.
E allora ... soprassediamo :D

:hello:

Re: Estrazioni casuali
 

Chi comincia vince, dato che alla prima mossa lascia l'avversario con 3 che perde.

Un totale parziale è perdente se, trovandocelo davanti ed avendo noi la mano, non possiamo fare niente per evitare la sconfitta.

Il valore cui si deve giungere (N o 1000) è logicamente perdente per chi consente all'avversario di arrivarci.
Sono invece vincenti quei parziali che ci permettono di fare una giocata che lascia l'avversario con un parziale perdente.

Quindi tutti i numeri x da 999 a 667 sono vincenti, perché distano da 1000 per meno della loro metà,
ovvero (1000-x)<(x/2)
anche x>2/3*1000,
che è vero a partire dal valore x=[2/3*1000]=667 ([] è la parte intera superiore).

666 è invece perdente, perché da lì non si riesce ad arrivare a 1000 e d'altra parte almeno 1 lo si deve aggiungere, lasciando l'avversario in posizione vincente.

Continuando a scendere, il prossimo perdente è x=[2/3*666]-1=443,
che è il più piccolo parziale dal quale non si può raggiungere 666.
Poi vengono 295, 196, 130, 86, 57, 37, 24, 15, 9, 5, 3, 1.

2 non è nell'elenco, quindi è vincente!

In generale, si parte da N e si comincia a moltiplicare per 2/3, arrotondando per eccesso e poi togliendo 1.
Se la catena passa per il 2 allora chi inizia perde, altrimenti vince.
Lo scopo di un giocatore è raggiungere ad ogni passo i numeri indicati, che risultano perdenti per l'avversario.

Ad esempio, se si dovesse raggiungere 100, il 2 sarebbe perdente.
Gli altri perdenti sarebbero 66, 43, 28, 18, 11, 7, 4, 2, per cui al secondo di mano (che si troverà subito di fronte ad un 3) basterà raggiungere sempre quei parziali per vincere.

:hello:

Re: Estrazioni casuali
 

Ancora più facile.
Se si parte da 4, e si deve arrivare a 1000, chi parte perde.
Infatti, vince chi raggiunge 4, 6, 10, 16, 25, 38, 58, 87, 131, 197, 296, 444, 666 e 1000 (dal target basta moltiplicare di volta in volta per 2/3, eliminando gli eventuali decimali).

Infine, supponiamo di poter aggiungere al parziale raggiunto, un numero minore di tale totale (non della metà).
Con una mossa non siamo in grado di passare da x a 2x, con due però possiamo raggiungere sia 2x che 2x+1, quale che sia il passaggio intermedio.
Questo in binario equivale ad aggiungere un bit a piacimento a destra di un
qualsiasi numero.

Per esempio, se il totale parziale fosse 30 (11110), il nostro avversario con una mossa non potrà mai arrivare a 11110x (60 o 61), mentre noi lo possiamo fare qualsiasi cosa faccia lui. Quindi possiamo aggiungere bit a piacimento, e raggiungere qualsiasi target, una volta che riusciamo ad agganciare la sequenza iniziale di bit.
Chi muove per primo può solo cominciare la sequenza con 11, il secondo giocatore vince nel caso in cui l'espansione binaria del numero da raggiungere cominci con 10. Quindi la discrimante la fa il secondo bit da sinistra.


Per esempio, nel caso di mille, che in binario vale 1111101000 vince il primo giocatore, passando per i parziali 11, 111, 1111, 11111, 111110, 1111101, 11111010, 111110100 e 1111101000.

La strategia per quello dei due che deve vincere è di portare il punteggio al valore che in binario corrisponde alle prime cifre da sinistra di N, aggiungendo una cifra ad ogni mossa:
Se N=1000, cioè 1111101000
il primo giocatore dovrà ottenere nell'ordine:
3 = 11
7 = 111
15 = 1111
31 = 11111
62 = 111110
125= 1111101
250= 11111010
500= 111110100
1000= 1111101000

Saluti binari
:hello:

Re: Estrazioni casuali
 

In un sacchetto, ci sono N palline di cui 2 sono nere e tutte le altre sono bianche.
Ho notato che estraendone a caso un certo numero M, (M>1), la probabilita' che siano tutte bianche e' = 1/2.

Sapendo che nel sacchetto ci sono meno di 100 palline, quali sono i valori di N ed M ?

E se N fosse maggiore di 1000 e minore di 10 mila?

:hello:

Re: Estrazioni casuali
 

Ultimo quiz proposto da Nino II.
In un sacchetto, ci sono N palline di cui 2 sono nere e tutte le altre sono bianche.
Ho notato che estraendone a caso un certo numero M, (M>1), la probabilità che siano tutte bianche è = 1/2.
a) Sapendo che nel sacchetto ci sono meno di 100 palline, quali sono i valori di N ed M ?
b) E se N fosse maggiore di 1000 e minore di 10 mila?

Sia C(N, k) il numero di combinazioni di N oggetti a k a k.
Estraendone M, fra le C(N, M) M-ple diverse (per identità delle palline che le compongono), ce ne sono C(N–2, M) di tutte palline bianche.
Dire che la probabilità che una N–pla scelta a caso sia di sole palline bianche vale 1/2 equivale a dire che
C(N–2, M) = C(N, M)/2 (*)
Ricordando che
C(N, k) = N! / [k! (N – k)!]
la (*) è una equazione diofantina nelle 2 incognite M ed N.

Precisamente:
2·(N–2)!/{M! · [N – (M + 2)]!]} = N! / [M! · (N – M)!] (**)

Semplificando per M! (divisore comune ai due membri) e per tutti i possibili fattori o divisori comuni
– cioè anche per (N – 2)! nei numeratori e per [N – (M + 2)]! nei denominatori –
resta l'uguaglianza

N·(N–1)/[(N–M–1)·(N – M)] = 2 <=> N·(N–1) = 2·(N–M–1)·(N – M) <=>
<=> N^2 + 2M^2 – 4MN – N + 2M = 0 (***)

Concettualmente ... il quiz finisce qua!

Non c'è che da cercare la coppie (N, M) per N crescente da 1 in su, M < N pure crescente da 0 in su, [arrestando M quando N^2 + 2M^2 – 4MN – N + 2M ≥ 0]
e registrare (N, M) quando
N^2 + 2M^2 – 4MN – N + 2M = 0
===========================
Ma ... mi sottopongo alle forche caudine: trovare le effettive soluzioni.
-------------
Si può interpretare l'uguaglianza (***) come equazione parametrica in N di parametro M.

Esplicitando N si trova allora:
N = [4·M + 1 + √(8M^2 + 1)]/2. (4)
Esplicitando invece M si trova:
M = {[2N – 1 – √[2N·(N–1)+1]}/2 (5)

Con la (4) occorre cercare M tale che 8M^2 + 1 sia il quadrato di un dispari.
Per M = 6 viene
8M^2 + 1 = 8·36+1= 288+1 ^ 289 = 17^2
Allora N = [(4·6 + 1) + 17)/2 = 21

Risposta a):
N = 21; M = 6.
Per controllo, deve essere
19!/(19–6)! = [21!/(21–6)!]/2= (1/2)·19!·20·21/[(19 – 6)!·(20–6)·(21 –6)] –––>
–––> 1 = [20·21/(14·15)]/2 = [420/(210)]/2 = 2/2 ––> O.K. :rolleyes:
============================================

D. «E se N fosse maggiore di 100?»
R. Continuando la ricerca di M intero tale che √(8M^2 + 1) sia intero, trovo, per esempio,
M = 35; N = 120.
Le possibilità sono infinite ma i numeri M ed N crescono.
Limitando le possibili soluzioni per N compreso in un certo intervallo, possiamo trovare
• nessuna soluzione, oppure
• una soluzione sola oppure
• più soluzioni
(a seconda dell'intervallo).

Adesso astromauh o qualcun altro si fa la conta (al computer) degli M che rendono intero il radicale
R = √(4M^2 + 1)
in modo che
N = (4M+1 + R)/2
renda vere le disequazioni
1 000 < N < 10 000
cioè
• M intero tale che R = √(8M^2 + 1) sia intero e
• 1000 < (4M + 1 + R)/2 < 10 000 <=> 1999 < 4M + R < 19 999
============================================

Beh: visto che ho detto di sottopormi alle forche caudine, la conta provo a farla anch'io senza computer :o

Per N sempre più grande N/M tende al limite 2 + √(2) ≈ 3,41
(N/M)limite = 2 + √(2) ≈ 3,41
(M/N)limite = 1 – √(2)/2 ≈ 0,293.
Questo mi agevola nel limita<re i calcoli

Dato l'intervallo di N, posso trovare l'intervallo di M esplicitando M come in (5)).

M = [2N – 1 – √(2N^2 – 2N + 1)]/2 (5)

Quando fosse
1000 < N < 10 000
dovrebbe essere
292 < M < 2929

Se si fa la conta a mano ... allora bisogna risparmiare sui conti!

8M^2 +1 deve essere quadrato di un dispari. Sia questo 2X+1.
Allora deve essere 8M^2 = 4X^2 + 4X e quindi
M = √[X·(X+1)/2]
Ma X e X+1 non possono avere fattori comuni quindi
• O succede che X è un quadrato dispari e (X+1)/2 è pure quadrato (di un altro dispari)
• oppure X+1 è un quadrato dispari e X/2 è pure un quadrato (di un pari).

Tabulando i quadrati dei numeri pari del tipo 4y^1 e dei dispari del tipo (2y+1)^2 si beccano per confronto gli X giusti.

Per esempio:
2 · 70^2 = 9800; 99^2 = 9801
Allora X = 9800
M = √[X(X+1)/2] = 70·99 = 6930
N = [4M+1 + √(8M^2 + 1)]/2 = 23661 Oops! Troppo grosso!

[Ma ... ce almeno una soluzione per 1 000 < N < 10 000? :mmh:]

Con X = (2y +1)^2 e z = √[(2y·(y+1)+1] trovo (crescendo y di un'unità alla volta fino a a che z diventa intero):
––> y = 3; z = 5; M = (2y+1)·z = 7·5 = 35; M = 35; N = 120 (Troppo piccoli)
––> y = 20; z = 29: M = (2y+1)·z = 41·29 = 1189: M = 1189; N = 4060 O.K.
Con X+1 = 2y^2 + 1 e z = √(2y^2+1) trovo (crescendo y di un'unità alla volta fino a che z diventa intero):
––> y = 12 ; z = 17 : M = y·z = 12.17 = 204; M= 204; N = 697 (Troppo piccoli)

Mi pare che, per 1000 < N < 10000, di M ed N che van bene non ce ne siano più.

Risposta b)
N = 4060; M = 1189..
---------
:hello:

Re: Estrazioni casuali
 

:ok:

Da:
N^2 - N + 2M^2 - 4NM + 2M = 0
ponendo:
K = N - 2M
si ha:
K^2 - K - 2M^2 = 0
K = (1 +- RADQ(1+8M^2))/2

e, a questo punto, ... ho messo in excel ... :)

(Con meno di 1000 palline, c'è anche N=697 e M=204)

:hello:

Re: Estrazioni casuali
 

Già conteggiati e segnati come "troppo piccoli"
Vedi che ho anche calcolato [N, M] = [23661, 6930] segnandoli come "troppo grossi".

------------
¿ Si possono costruire delle successioni di coppie di interi [Xn, Yn] con la proprietà caratteristica
x^2 + 2y^2 – 4xy – x + 2y = 0
tali che, spostando il riferimento, cartesiano si ottenga una progressione geometriaca? :mmh:

[L'equazione cartesiana è quella di un'iperbole con un ramo che passa per l'origine degli assi].

Cioè:
Si possono trovare 6 costanti, A, B, C, D ed E tali che risulti, per qualsiasi n intero, valga quel che segue qui sotto?
X(n+1) – E = A·[X(n) – E] + B·[Y(n) – F]
Y(n+1) – F = C·[X(n) – E] + D·[Y(n) – F]

Il quiz te lo dò io adesso: ;)
Rispondi alla domanda e, in caso affermativo, dicci quali sono le 6 costanti
:D
------------------

Re: Estrazioni casuali
 

Siamo già incappati in questi numeri triangolari.
N
a(n) = 6a(n-1) - a(n-2) -2 con n>2, a(0)=1, a(1)=4
a(n) = 7a(n-1) - 7a(n-2) + a(n-3) con a(0)=1, a(1)=4, a(2)=21

M
a(n) = 7(a(n-1) - a(n-2)) + a(n-3), a(1) = 0, a(2) = 1, a(3) = 6, n > 3.
a(n) = 5*(a(n-1) + a(n-2)) - a(n-3)

:o Non capisco neppure la domanda... e mi nascondo un po' :D

:hello:

Sequenze linearmente dipendenti
 

La seconda legge di ricorrenza per M non va bene: è incompatibile con la prima (che ovviamente ha gli stessi coefficienti della legge di ricorrenza per N).
-----------------------------
N ed M sono è realtà una sequenze linearmente dipendenti (che continua indefinitamente anche a suinistra) col medesimo polinomio caratteristico).E' la terza volta che ripeto!
Quando k + 1 termini in fila – prescindendo dal numero d'ordine del capofila – sono linearmente dipendenti, (esiste cioè una loro combinazione lineare nulla con opportuni coefficienti indipendenti dal numero dìordine), si può associare il polinomio caratteristico. Gli zeri di questo siano distinti, diciamoli Zr con r da 1 a k.
Allora la sequenza è del tipo
Xn = A1·Z1^n + A2·Z2^n + ... Ak·Zk.

Se conosco k termini in fila, posso determinare le costanti A1, A2, ..., Ak

Consideriamo N (come hai fatto tu).
Vedo che, per ogni n
a(n+3) – 7·a(n+2) + 7·a(n+1) + a(n+1) = 0

Il polinomio caratteristico è dunque
x^3 – 7·x^2 + 7·x – 1 = (x – 1)·(x^2 – 6·x + 1)

Gli zeri (cioè le soluzioni dell'equazione che si ha uguagliando il polinomio a zero) sono
Z1 = 1; Z2 = 3 + 2√(2); Z3 = 3 – 2·√(2).

Allora sarà sempre (per n qualsiasi)
a(n) = A·[3+2√(2)]^n + B·[3 – 2√(2)]^n + C (perché il terzo zero è Z3 = 1 e 1^n = 1).

Sapendo che
a(0) = 1; a(1) = 4; a(2) = 21
faccio il sistema lineare (nelle iincognite A, B e C)

A + B + C = 1 [cioè A·Z1^0 + B·Z2^0 + C·Z3^0 = a(0) ]
A·[3 + 2√(2)] + B·[3–2√(2)] + C = 3(A+B) + 2·√(2)· (A – B) + C = 4
A·[3 + 2√(2)]^2 + B·[3 – 2√(2)]^2 + C = 17(A + B) + 12·√(2) (A – B ) + C = 21.

Si trova
A = [√(2) + 1]/4; B = [√(2) – 1]/4; C = 1/2.

Quindi:
a(n) = {[√(2) + 1]/4}·[3 + 2√(2)^n – {[√(2) – 1]/8}·[3 –2√(2)]^n}

--------------------------
Analogamente per M.
Il polinomio caratteristico è lo stesso. I coefficienti del sistema lineare sono gli stessi. Cambiano invece i termini noti
Siano b(n) i termini della sequenza M.
b(0) = 0; b(1) = 1; b(2) = 6.
Deve essere (per ogni n):
b(n) = D·[3+2√(2)]^n + E ·[3 – 2√(2)]^n + F

Si trova:
D = √(2)/8 ; E = – √(2)/8; F = 0.
Quindi:
b(n) = [√(2)/8] · {[3 + 2√(2)^n – [3 –2√(2)]^n}

------------------
:hello:

Re: Sequenze linearmente dipendenti
 

a(n) = 7(a(n-1) - a(n-2)) + a(n-3), a(1) = 0, a(2) = 1, a(3) = 6, n > 3.
a(n) = 5·[a(n-1) + a(n-2)] - a(n-3)

:mmh: Perché?
a(3) = 5*(a(2)+a(1)) -a(0) = 5*7 - 0 = 35
a(4) = 5*(35+6) - 1 = 204
a(5) = 5*(204 + 35) - 6 = 1189
..........

:hello:

Ho trovato anche (per M):
Lim n -> inf. a(n)/a(n-1) = 3 + 2*sqrt(2).
a(n) ~ 1/8*sqrt(2)*(sqrt(2) + 1)^(2*n)

Re: Sequenze linearmente dipendenti
 

In questo caso particolare ... hai ragione tu, va bene anche
X(n+3) = 5·X(n+2) + 5·X(n+1) – X(n).

Ma allora vuol dire che la sequenza di M non è del terzo ordine, ma del secondo.

In effetti, per ogni k arbitrario andrebbe anche bene una ricorrenza del tipo

X(n+3) = (6+k)·X(n+2) – (6·k +1)·X(n+1) + k·X(n) (*)

Per esempio, per k = – 2 abbiamo:
X(n+3) = 4·X(n+2) + 11·X(n+1) – 2·X(n).

Allora, per X(–1) = 1; X(0) = 0 e X(1) = 1 otteniamo
X(2) = 4·(1) + 11·(0) –2·(–1) = 6
X(3) = 4·6 +11·1 –2·0 = 24 + 11 = 35
X(4) = 4·35 + 11·6 – 2·1 = 140 + 66 – 2 = 204
X(5) = 4·204 + 11·35 – 2·6 = 816 + 385 – 12 = 1201 – 12 = 1189
....

Per k = +1 viene la ricorrenza X(n+3) = 7·X(n+2) – 7·X(n+1) + X(n) [la stessa di N].
Per k = –1 viene la ricorrenza X(n+3) = 5·X(n+2) + 5·X(n+1) – X(n).

Spiegazione
Il polinomio caratteristico della (*) è infatti
P(z) = z^3 – (6+k)·z^2 + (6·k + 1)·z – k = (z – k)·(x – a)·(x – 1/a)
dove a = 3 + 2√(2), [per cui 1/a = 3 – 2√(2)].

La soluzione generale della (*) è allora del tipo

X(n) = A·a^n + B/a^n + C·k^n (**)

Evidentemente, occorre e basta che, nel caso specifico, sia C = 0 perché la (*) vada bene per qualsiasi k.

Ma allora le costanti da determinare sono due sole, cioè: la ricorrenza non è di ordine 3 ma di ordine 2.
Se vogliamo che la legge di ricorrenza sia unica, basta (nel polinomio caratteristico) trascurare il fattore (z – k) e considerare solo il polinomio di 2° grado
P(z) = z^2 – 6z + 1
ottenendo
X(n+2) = 6·X(n+1) – X(n)
Per X(–1) = –1 e X(0) = 0 si ha infatti
X(1) = 6·0 –1·(–1) = 1
X(2) = 6·1 –1·0 = 6
X(3) = 6·6 – 1 = 36 – 1 = 35
X(4) = 6·35 – 6 = 210 – 6 = 204
X(5) = 6·204 – 35 = 1224 – 35 = 1189
X(6) = 6·1189 – 204 = 7134– 204 = 6930
X(7) = 6·6930 – 1189 = 41580 - 11894 = 40391
...

[Questi numeri X sono tutti e soli quelli per i quali la radice quadrata di 8·X^2 + 1 è un numero intero perché sono del tipo A·(b^n – 1/b^2) con A = √(2)/8.
In effetti, se X = A·[b^n–(1/b)^n] è intero, abbiamo:
8·X^2 + 1 = 8·A^2·[b^(2n) + (1/b)^(2n) – 2] + 1 = 8·A^2·[b^(2n) + (1/b)^(2n) +2] + 1 – 32·A^2 = 8·(A^2)· [(b^n + 1/b^n)]^2 + (1 – 32·A^2).
Se ora è A = √(2)/8, risulta 8·A^2 = 1/4 e 1 – 32·A^2 = 0, per cui:
8·X^2 + 1 = (b^n + 1/b^n)/2
che è intero se b e 1/b sono rispettivamente nella forma b = k + h ; 1/b = k – h con k intero e h^2 intero pari perché allora b^n + 1/b^n risulta intero pari.

E' proprio il nostro caso essendo k = 2√(2) per cui √(k^+1) = 3.

Si noti anche che b = 3 + 2√(2) è il quadrato di √(2) + 1. Se fosse b = √(2) + 1, [e allora sarebbe 1/b = √(2) – 1 ], pur non essendo intero b + 1/b né le potenze dispari di (b + 1/b), sarebbe comunque intero il quadrato di (b^n + 1/b^n):
[(√2 + 1)^n + (√2 – 1)^n]^2 = (3 + 2√2)^n + (3 – 2√2)^n – 2·[√(4 –1)^n =
= (3 + 2√2)^n + (3 – 2√2)^n – 2·3^n.
------------
:hello:

Piccola riflessione filosofica
 

Spesso capita di ritrovare gli stessi "topic" trattando argomenti che sembrano assolutamente slegati.

Siamo partiti da un particolare problema di probabilità e siamo cascati ancora una volta nelle sequenze linearmente dipendenti (tipo la sequenza di Fibonacci).
Non solo: ma gli autovalori sono gli stessi del caso delle sequenze dei lati dei triangoli rettangoli con lati interi e differenza costante tra i cateti.
Non so se l'hai notato: la sequenza di N è esattamente quella del cateto maggiore della sequenza dei triangoli con differenza 1 tra i cateti; e la sequenza di M è la metà della differenza tra la somma dei cateti e l'ipotenusa. Guarda qua:Trovo molto strano questo ritornare di elementi astratti di matematica pura nei singoli disparati casi della matematica applicata.
Davvero sorprendente ed affascinante ad un tempo.
Mi domando se per caso dipende dal fatto che, in fondo, è sempre l'Uomo che inventa la matematica astraendo la partenza delle sue elucubrazioni da fatti naturali e proseguendo poi nella creatività dell'astratto puro.
Ecco perché avvicino la matematica a qualsiasi altra forma di umanesimo, sia esso puramente artistico o squisitamente pratico (come l'ingegnerizzazione e il progresso tecnologico).

Ciao ciao
---------
:hello:

Re: Piccola riflessione filosofica
 

Sì che mi ero accorto...

#410
Siamo già incappati in questi numeri triangolari.

Se avessi trovato qualche professore che mi faceva "giocare" con i quiz, e magari anche a scopone, scacchi, totocalcio, ..., forse la matematica a scuola mi sarebbe piaciuta, anziché annoiarmi ... e l'avrei imparata...

:)

:hello:

Re: Piccola riflessione filosofica
 

Come prima.
Abbiamo un sacchetto N palline di cui 2 sono nere e le altre tutte bianche.
Estraiamo M palline a caso.
Tu avevi chiesto [in sostanza] per quali coppie (M, N) la probabilità che le M palline estratte a caso siano tutte bianche vale 1/2.

Rilancio e chiedo.
1) «Per quali coppie (M, N) la probabilità che le M palline estratte siano tutte bianche vale 1/3?»
2) «Per quali coppie (M, N) la probabilità che le M palline estratte siano tutte bianche vale 1/4?»
....
2) «Per quali coppie (M, N) la probabilità che le M palline estratte siano tutte bianche vale 1/k [k intero, k>1]?»

En passant, visto che nel quiz c'era da trovare M intero tale che anche
N = [4·M+1 + √(8·M^2 + 1)]/2
fosse intero, proviamo a trovare per quali M è intero anche
N = [8·M + 3 + √(16·M^2 + 9)]/6.
Prima bastava che fosse intera la radice quadrata di 8·M^2 + 1.
Ora non basta che sia intera √(16·M^2 + 9) ma bisogna pure che sia intero il numero
X = [8·M + √(16·M^2 + 9)]/3. ;)
-------------
:hello:

Re: Piccola riflessione filosofica
 

Siccome invece io non me ne sono accorto subito, non capivo cosa intendevi dire, dal momento che esiste già la categoria dei numeri triangolari
T(n) = n(n+1)/2 per ogni n naturale [ ––> Numero triangolare (Wikipedia)]
... e ho lasciato perdere.
------------
Un'ultima osservazione ... sui numeri triangolari nel senso che intendevi tu. ;)

Siano [X(n), Y(n), Z(n)] l– con Y(n) > X(n) – le terne pitagoriche con Y(n) – X(n) = 1 [per ogni n naturale].
[Sono tutte primitive]

Il perimetro è sempre pari e quindi il semi-perimetro P(n) = [X(n) + Y(n) + Z(n)]/2 è sempre intero.
I nostri numeri N(n) ed M(n) sono definibili come:
N(n) = Y(n);
M(n) = [X(n) + Y(n) – Z(n)]/2 = [X(n) + Y(n) + Z(n) – 2·Z(n)]/2 = P(n) – Z(n).

Siccome, per ogni n naturale
X(n+1) = 2·X(n) + 1·Y(n) + 2·Z(n)
Y(n+1) = 1·X(n) + 2·Y(n) + 2·Z(n)
Y(n+1) = 2·X(n) + 2·Y(n) + 3·Z(n)
e (invertendo)
X(n) = 2·X(n+1) + 1·Y(n+1) – 2·Z(n+1)
Y(n) = 1·X(n+1) + 2·Y(n+1) – 2·Z(n+1)
X(n)= –2·X(n+1) –2·Y(n+1) + 3·Z(n+1)
s dimostra facilmente che
M(n) = P(n–1).

In altre parole, M(n) è il semi-perimetro della terna antecedente quella di cui N(n) è il cateto maggiore
--------------
:hello:

Re: Piccola riflessione filosofica
 

Sono in partenza. Forse ci guardo stasera.

Comunque, per p=1/3
N = 3,10,36,133,495,1846,6888...
M = 1,2,6,21,77,286,1066,...

per N ; a(n) = a(n-3) - 5*a(n-2) + 5*a(n-1), a(0) = 1, a(1) = 3, a(2) = 10.
a(n) = 1/2-(1/4)*sqrt(3)*(2-sqrt(3))^n+(1/4)*sqrt(3)*(2+sqrt(3))^n+(1/4)*(2-sqrt(3))^n+(1/4)*(2+sqrt(3))^n, with n>=0.
per M; a(1) = 1, a(2) = 2, a(3) = 6; a(n) = 5*a(n-1) - 5*a(n-2) + a(n-3) for n>3.
M = x^3 - 5x^2 + 5x - 1

:hello:

Re: Piccola riflessione filosofica
 

Da quando in qua ti sei messo a scrivere in inglese?
Hai fatto un copia/incolla? :mad:
Allora non vale!
----------------
Comunque, questo era facile facile. Più che per p = 1/2.
Ma allora insisti? :(
Eh, eh ... hai imparato il concetto di "polinomio caratteristico" (anche se l'ortografia lasca a desiderare ... dato che M non è il [suo]polinomio caratteristico[/u]).
Come per l'altra volta, però ... polinomio di 3° grado e [quindi] [/u]ricorrenza di terzo ordine sono ridondanti la sequenza di M.
Il polinomio si riduce a x^2 – 4·x + 1.
Ripeto: Nel polinomio caratteristico c'è il fattore (x – 1) quando la sequenza contine una costante additiva.
Infatti, da P(z) = (z – 1)·(z –k)·(z – 1/k) segue che la soluzione generale della data legge di ricorrenza è del tipo
X(n+2) = A·k^n + B·(1/k)^n + C·1^n
[Combinazione di progressioni geometriche di ragione pari ai singoli zeri del polinomio caratteristico].
La legge di ricorrenza per M si riduce al 2° ordine perché non può esserci una costante additiva, essendo M una sequenza con simmetria dispari, cioè
M(–n) = M(n)
Quindi, la costante C è per forza nulla,
[cioè: non c'è la progressione geometrica di ragione 1 :eek:]
Per M basta fare
M(–1) = –1; M(0) = 0;
M(n+2) = 4·M(n+1) – M(n).
Infatti
M(1) = 4·M(0) – M(–1) = 4·0 –(–1) = 1;
M(2) = 4·M(1) – M(0) = 4·1 – 0 = 4;
M(3) = 4·4 – 1 = 15
M(4) = 4·15 – 4 = 56
M(5) = 4·56 – 15 = 209
Ecc. ecc.
------------

Ma resta da risolvere il quiz per p = 1/4 ...

Nel caso p=1/2, che cosa vuol dire che una coppia (M, N) è (4, 1)?
Vuol dire che con 4 palline, due nere e due bianche, una sola pallina estratta ha probabilità 1/2 di essere bianca.

E nel caso p = 1/3, che cosa vuol dire che una coppia è N = 3 e M = 1?
Vuol dire che con 3 palline, due nere e una bianca, una sola pallina estratta ha probabilità 1/3 di essere bianca.

E nel caso p = 1/4 ?
Oh, orco mondo, non posso fare una analoga cosa con p = 1/4.

Mentre con p =1/2 e p = 1/3 trovavo di colpo tre coppie (M, N) in fila, qui ne ho due sole:
(–1, 0), (0, 1).

Ci sarà mai una terza coppia?

Per non cercare forse inutilmente l'ago nel pagliaio, cerchiamo di capire se nel pagliaio qualche ago c'è davvero-
Ossia: chiediamoci se l'equazione [diofantina]:
8·x + √(16·x^2 + 9) = 3·y
ammette soluzioni intere :fis:
-----------------
Ciao ciao

Re: Piccola riflessione filosofica
 

Sono stato beccato!:D
Comunque, le cose è importante saperle... ma ancora più importante ed utile è sapere dove andarle a cercare....:)

Torno ora, dov'ero non prendevo Internet, vedo che sono spariti anche Astromauh e Rob77; è un po' mortificante assistere ad uno che domanda e l'altro (quasi sempre gli stessi!) risponde ... e viceversa... :(

----------
Per p=1/4 mi pare non esistano soluzioni.

:hello:

Re: Estrazioni casuali
 

Presente! È che nelle ultime due settimane avevo un pò di lavoro da smaltire...

Re: Estrazioni casuali
 

Questo era l'ultimo ed è stato risolto, giusto?

:hello:

Re: Estrazioni casuali
 

Non proprio!
1) Resta la variante che ho fatto io.
Risolvere se possibile lo stesso quiz con p = 1/4.
[Se si ritiene impossibile, spiegare perché].
[Comunque, quel che ne è uscito merita una lettura attenta].

Aspetto ansiosamente :eek: che aspesi (o altri) risponda al quiz con la variante p = 1/4 che ho proposto ... cambiando nella sostanza l'argomento ;).

2) Ho messo un nuovo quiz (nell'altro thread: Un po' di calcoli ... un po' di logica)
-------------
:hello:

Re: Estrazioni casuali
 

Ho fatto un programmino sotto Excel, tra l'altro neanche tanto complesso, con input la probabilità data la quale si ricavano M ed N solo che inspiegabilmente non gira (e non dà neanche errori in runtime).

Adesso lo porto in C.

Ciao

Re: Estrazioni casuali
 

Non gira o non trova risultati?

Perché per p=1/4 non dovrebbero esserci soluzioni (di N e M) se le palline di uno dei due colori sono solo 2.

:hello:

Re: Estrazioni casuali
 

Se lo lancio in debug va, se lo lancio in release no :mmh:
Ho quasi finito in Turbo Pascal...

Re: Estrazioni casuali
 

Nel lancio di una moneta N volte, lo spazio campionario è costituito da 2^N esiti (sequenze di teste e croci)

Qual è il numero di esiti che contengono almeno 8 T consecutive per N=100 lanci (e K teste "consecutive" per N>K)?

E qual è il numero minimo di lanci che consentono di avere una probabilità superiore al 50% di osservare almeno 8 T consecutive?

:hello:

Re: Estrazioni casuali
 

Allora, ho scritto questo semplicissimo programmino in Turbo Pascal:

Purtroppo credo che i risultati siano inficiati dalla qualità del random del Turbo Pascal.
Ad ogni modo, ve li presento qui:

1. Tutte le probabilità: http://www.mediafire.com/download.php?pcev84hz4gg8zi9
2. Solo ed esclusivamente i casi per cui la probabilità trovata dal programma stia nell'intervallo 0,5±1%·0,5: http://www.mediafire.com/download.php?2bgzdwlc417d3bd

Come potete vedere, il mio programma trova più casi M, N.
Scusate se ho scritto castronerie ma ho fatto tutto di frettissima.

Ciao

Re: Estrazioni casuali
 

La simulazione è relativa solo al quiz proposto da me, cioè:
N<100 palline, di cui 2 nere e N-2 bianche
Estraendone un numero M>1 a caso, la probabilità che siano tutte bianche è = 1/2

L'unica soluzione è: N=21 e M=6
Infatti, 21*20 = 2*(21-6)*(20-6)

Il tuo programma, come hai visto, trova anche altre soluzioni, perché l'approssimazione e la randomizzazione in questo caso non sono accettabili.
Ad es.:

N=24 e M=7
p_simulazione = 0,4979
p_effettiva = (24-7)*(23-7)/(24*23) = 0,492754...

N=35 e M=10
p_simulazione = 0,5026
P_effettiva = (35-10)*(34-10)/(35*34) = 0,504202...

ecc...

:hello:

Re: Estrazioni casuali
 

Sì, era proprio questa verifica che volevo da voi.
Ho visto che ci sono alcune routine per generare sequenze di numeri casuali.
Provo a vedere di utilizzarle.

Ciao

Re: Estrazioni casuali
 

Per il primo punto ho pensato ad una possibile strada che risulta però errata (e ve lo scrivo alla fine il perchè):
[*] 8T: ho 92 shift possibili.
TTTTTTTTxxxxx...xxx
xTTTTTTTTxxxxx...xx
[...]
xxx....xxxxTTTTTTTT

Ogni shift lo moltiplico per le possibili combinazioni (T/C) delle rimanenti posizioni.

+

[*] 9T: idem come sopra

+

[*] 10T: idem come sopra

...


Il problema è che conto più di una volta stesse sequenze.

Vabbè, stacco e ci ripenso più tardi.

Ciao

Re: Estrazioni casuali
 

;) Proprio così. Occorre fare attenzione a non ripetere conteggi di cui si è già tenuto conto.

:hello:

Re: Estrazioni casuali
 

2,32733e+29 ?

Re: Estrazioni casuali
 

Ne hai contati il 7,8% in più...:)

:hello:

Re: Estrazioni casuali
 

Strano perché ho applicato lo stesso metodo per 5 estrazioni ed almeno 3T consecutive e mi ha dato il risultato corretto (ho poi proprio provato a contarle).

Ho ragionato così: per ogni shift calcolo le possibili combinazioni degli N elementi a destra e le possibili combinazioni degli M-1 elementi a sinistra (M+N+1=100).
Sottraggo 1 ad M per il calcolo degli elementi a sinistra per non contare più volte la stessa combinazione.

Per il caso 5/3T:

Shift;Libere a Dx;Libere a Sx;Combin. a Dx;Combin. a Sx;Totale
0 2 0 4 1 4
1 1 0 2 1 2
2 0 1 1 2 2

Totale: 8

:mmh:

Re: Estrazioni casuali
 

In questo caso va bene:
TTTXX =4
CTTTX =2
CCTTT =1
TCTTT =1
Totale = 8

Ma se aumenti i lanci, ho paura che il tuo calcolo conteggi qualche ripetizione.
Prova 12 lanci e 5 consecutività minimo (p=0,1394... combinazioni=571)

:hello:

Re: Estrazioni casuali
 

Sì, probabilmente erra il mio algoritmo.

Caso: 12/5
Shift;LibereaDx;LibereaSx;Combin.aDx;Combin.aSx;To tale
0 7 0 128 1 128
1 6 0 64 1 64
2 5 1 32 2 64
3 4 2 16 4 64
4 3 3 8 8 64
5 2 4 4 16 64
6 1 5 2 32 64
7 0 6 1 64 64

576

Ora lo riguardo

Re: Estrazioni casuali
 

A occhio, mi pare sbagli quando i lanci superano il doppio delle consecutività...

(il 6 sono 62 e il 7 sono 61, mentre tu consideri per tutti 64...)

Re: Estrazioni casuali
 

Esatto. L'ho trovato ora il problema. Vengo ad ammettere sequenze del tipo:

TTTTTCCTTTTT

Re: Estrazioni casuali
 

Ho corretto l'algoritmo e ora il valore è giusto.
Curiosità: hai usato la stessa strada mia? Mi sembra un pò faticosa ma è l'unica che mi è venuta in mente

Re: Estrazioni casuali
 

No, io non so programmare.
Ci sono almeno due modi per affrontare il problema e risolverlo abbastanza agevolmente (con un foglio excel, ma anche con una semplice calcolatrice).

Aspetto Erasmus e Astromauh, se hanno voglia di pensarci.
Altrimenti, sabato indicherò le mie soluzioni.

:hello: