Coelestis - Il Forum Italiano di Astronomia

Coelestis - Il Forum Italiano di Astronomia (http://www.trekportal.it/coelestis/index.php)
-   Rudi Mathematici (http://www.trekportal.it/coelestis/forumdisplay.php?f=11)
-   -   Estrazioni casuali (http://www.trekportal.it/coelestis/showthread.php?t=42400)

aspesi 14-04-12 10:24

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

:hello:

aspesi 14-04-12 17:02

Re: Estrazioni casuali
 
Quote:

Due giocatori si alternano nello scegliere un numero

Facciamo lo stesso giochino imponendo che il numero scelto
:hello:
#393

Quote:

.

Di un insieme di cartoncini si sa che:
1) Sono in tutto 81;
Domanda: Quanti sono i cartoncini sui quali c'è scritto il numero 10?

---------------
:hello:
#672

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

:hello:

aspesi 15-04-12 17:56

Re: Estrazioni casuali
 
Quote:

aspesi (Scrivi 584539)
Due giocatori si alternano nello scegliere un numero e sommarlo al totale raggiunto.
Il numero scelto deve essere minore o uguale della metà del totale, che inizialmente parte da 2.
Vince chi arriva a 1000 (generalizzando: a un valore N).
Chi vince fra i due, e qual è la strategia?

:hello:

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:

aspesi 16-04-12 09:29

Re: Estrazioni casuali
 
Quote:

aspesi (Scrivi 584539)

Facciamo lo stesso giochino imponendo che il numero scelto debba essere "minore"
della meta' del totale (e non "minore o uguale"),e supponiamo pero' di partire da 4.
Anche in questo caso per vincere bisogna arrivare a 1000.
In questo caso, vince chi comincia o l'altro giocatore?

:hello:

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:

aspesi 18-04-12 14:31

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:

Erasmus 19-04-12 12:20

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:

aspesi 19-04-12 13:38

Re: Estrazioni casuali
 
Quote:

Erasmus (Scrivi 588028)
N·(N–1)/[(N–M–1)·(N – M)] = 2 <=> N·(N–1) = 2·(N–M–1)·(N – M)


N = 21; M = 6.
Per controllo, deve essere

N = 4060; M = 1189.. O.K.

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

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

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

Erasmus 19-04-12 19:31

Re: Estrazioni casuali
 
Quote:

aspesi (Scrivi 588055)
[...]
(Con meno di 1000 palline, c'è anche N=697 e M=204)

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

aspesi 19-04-12 20:10

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)

Quote:

Erasmus (Scrivi 588150)
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

------------------

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

:hello:

Erasmus 20-04-12 04:51

Sequenze linearmente dipendenti
 
Quote:

aspesi (Scrivi 588161)
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)

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).
Codice:

n ––>|  ...      –4      –3      –2      –1        0      1      2        3        4        5    ...
–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
N––>|  ...  –119    –20    –3        0        1      4      21      120    693    4060  ...
M––>|  ... –1189  –204    –35    –6      0        1        6      35    204    1189 ...

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:

aspesi 20-04-12 09:32

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)

Quote:

Erasmus (Scrivi 588203)
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).
:hello:

: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)

Erasmus 20-04-12 12:51

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:

Erasmus 20-04-12 17:01

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:
Codice:

                    n    ––>| 0      1        2        3        4        5    ...
–––––––––––––––––––––––––––––––––––––––––––––––––––––
      Cateto min. x  ––> | 0      3      20      119    696  4059  ...
N = Cateto mag. y ––> | 1      4      21      120    697  4060  ...
      Ipotenusa    z ––> | 1      5      29      169    985    5741  ...
–––––––––––––––––––––––––––––––––––––––––––––––––––––––
          x + y        –––> |1      7      41      239  1393    8119 ...   
      x + y  – z    –––> |0      2      12        70    408    2378 ... 
M = (x + y – z)/2 –––> |0      1        6        35      204  1198 ...

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:

aspesi 20-04-12 18:42

Re: Piccola riflessione filosofica
 
Quote:

Erasmus (Scrivi 588346)
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:
Codice:

                    n    ––>| 0      1        2        3        4        5    ...
–––––––––––––––––––––––––––––––––––––––––––––––––––––
      Cateto min. x  ––> | 0      3      20      119    696  4059  ...
N = Cateto mag. y ––> | 1      4      21      120    697  4060  ...
      Ipotenusa    z ––> | 1      5      29      169    985    5741  ...
–––––––––––––––––––––––––––––––––––––––––––––––––––––––
          x + y        –––> |1      7      41      239  1393    8119 ...   
      x + y  – z    –––> |0      2      12        70    408    2378 ... 
M = (x + y – z)/2 –––> |0      1        6        35      204  1198 ...


Sì che mi ero accorto...

#410
Siamo già incappati in questi numeri triangolari.

Quote:

Davvero sorprendente ed affascinante ad un tempo.
Mi domando se per caso dipende dal fatto che, in fonto, è sempre l'Uomo che inventa la matematica astraendo la partenza delle sue elucubrazioni da fatti naturali e proseguendo poi nella creatività dell'astratto puro.

Ciao ciao
---------
:hello:
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:

Erasmus 21-04-12 11:29

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:

Erasmus 21-04-12 12:55

Re: Piccola riflessione filosofica
 
Quote:

aspesi (Scrivi 588369)
Sì che mi ero accorto...
#410
Siamo già incappati in questi numeri triangolari.

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:

aspesi 21-04-12 13:25

Re: Piccola riflessione filosofica
 
Quote:

Erasmus (Scrivi 588490)
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
:hello:

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:

Erasmus 22-04-12 19:04

Re: Piccola riflessione filosofica
 
Quote:

aspesi (Scrivi 588509)
... with n>=0.

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

aspesi (Scrivi 588509)
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.

Ma allora insisti? :(
Quote:

aspesi (Scrivi 588509)
M = x^3 - 5x^2 + 5x - 1
x^3 +5·x^2 + 5x - 1)

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

aspesi 23-04-12 17:13

Re: Piccola riflessione filosofica
 
Quote:

Erasmus (Scrivi 588832)
Da quando in qua ti sei messo a scrivere in inglese?
Hai fatto un copia/incolla?
Allora non vale!
----------------
----------------

-Ossia: chiediamoci se l'equazione [diofantina]:
8·x + √(16·x^2 + 9) = 3·y
ammette soluzioni intere
-----------------
Ciao ciao

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:

Rob77 23-04-12 17:45

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

Rob77 23-04-12 17:46

Re: Estrazioni casuali
 
Quote:

aspesi (Scrivi 587815)
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:

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

:hello:

Erasmus 23-04-12 18:32

Re: Estrazioni casuali
 
Quote:

Rob77 (Scrivi 589005)
Questo era l'ultimo ed è stato risolto, giusto?

:hello:

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:

Rob77 24-04-12 12:29

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

aspesi 24-04-12 12:50

Re: Estrazioni casuali
 
Quote:

Rob77 (Scrivi 589215)
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).

Ciao

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:

Rob77 24-04-12 13:55

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

aspesi 24-04-12 16:50

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:

Rob77 24-04-12 17:08

Re: Estrazioni casuali
 
Allora, ho scritto questo semplicissimo programmino in Turbo Pascal:

Codice:

program estrazioni;

var
  i, j, k, m, jj: Integer;
  estratto_indice: Integer;
  casisfavorevoli, t: LongInt;
  filehandler, filehandler1: Text;
  fname, fname1: String[10];
  prob, forbice: Real;

begin
  Randomize;
  fname:='rtot';
  fname1:='rvalid';
  assign(filehandler, 'C:\'+fname+'.txt');
  assign(filehandler1, 'C:\'+fname1+'.txt');
  rewrite(filehandler);
  rewrite(filehandler1);

  forbice:=0.5/100;
  for i:=3 to 100 do
  begin
    write(filehandler, i);
    write(filehandler, ';');
    for j:=1 to i-2 do
    begin
      for t:=1 to 100000 do
      begin
        for jj:=1 to j do
        begin
          estratto_indice:=random(i-jj+1);
          if (estratto_indice=0) Or
            (estratto_indice=1) then
          begin
          casisfavorevoli:=casisfavorevoli + 1;
          break;
          end;
        end;
      end;
      prob:=1-(casisfavorevoli/100000);
      write(filehandler, prob:1:4);
      write(filehandler, ';');
      if (prob<0.5+forbice) And
        (prob>0.5-forbice) then
      begin
        write(filehandler1, i);
        write(filehandler1, ';');
        write(filehandler1, j);
        write(filehandler1, ';');
        writeln(filehandler1, prob:1:4);
      end;
      casisfavorevoli:=0;
    end;
    writeln(filehandler);
  end;

  close(filehandler);
  close(filehandler1);
end.

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

aspesi 24-04-12 18:09

Re: Estrazioni casuali
 
Quote:

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

Ciao

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:

Rob77 24-04-12 18:58

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

Rob77 24-04-12 21:18

Re: Estrazioni casuali
 
Quote:

aspesi (Scrivi 589283)
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:

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

aspesi 24-04-12 21:54

Re: Estrazioni casuali
 
Quote:

Rob77 (Scrivi 589358)
Il problema è che conto più di una volta stesse sequenze.

Vabbè, stacco e ci ripenso più tardi.

Ciao

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

:hello:

Rob77 26-04-12 17:11

Re: Estrazioni casuali
 
2,32733e+29 ?

aspesi 26-04-12 17:30

Re: Estrazioni casuali
 
Quote:

Rob77 (Scrivi 589897)
2,32733e+29 ?

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

:hello:

Rob77 26-04-12 17:38

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:

aspesi 26-04-12 17:54

Re: Estrazioni casuali
 
Quote:

Rob77 (Scrivi 589905)
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:

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:

Rob77 26-04-12 18:01

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

aspesi 26-04-12 18:08

Re: Estrazioni casuali
 
Quote:

Rob77 (Scrivi 589910)
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

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

Rob77 26-04-12 18:13

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

TTTTTCCTTTTT

Rob77 26-04-12 19:33

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

aspesi 26-04-12 20:21

Re: Estrazioni casuali
 
Quote:

Rob77 (Scrivi 589935)
Curiosità: hai usato la stessa strada mia? Mi sembra un pò faticosa ma è l'unica che mi è venuta in mente

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:


Tutti gli orari sono GMT. Attualmente sono le 17:58.

Powered by vBulletin versione 3.6.7
Copyright ©: 2000 - 2023, Jelsoft Enterprises Ltd.
Traduzione italiana a cura di: vBulletinItalia.it