I cerini di Banach

[panurgo]

Stefan Banach soleva acquistare due scatole di cerini per volta; se le metteva in tasca e prendeva i cerini scegliendo a caso una delle due scatole e rimettendola in tasca subito dopo; quando cercando un cerino trovava che la scatola scelta era vuota, gettava via le due scatole e ne comprava altre due: quanti cerini sprecava con questo giochetto?

[delfo52]

sei sicuro che seguisse questo algoritmo ?
A me avevano detto che buttava via le scatole quando prendeva l'ultimo cerino?
e la cosa ha più (?) senso, perchè se la cosa gli succede di notte....
A parte gli scherzi, il problema è intrigante, e per un numero di cerini abbastanza alto, le due strategie non dovrebbero comportare una differenza troppo grande.
Ma per l'appunto, è necessario sapere quanti cerini contiene una scatola?
a occhio direi di sì.
nel caso limite di due scatole monoceriniche, alla seconda sigfaretta, ha il 50% di chances di buttare via un cerino (con la trategia proposta da me, ha il 100% !!)
con scatole da tre cerini, mi viene uno spreco di 19seddicesimi di cerino
SE&O

[panurgo]

I torni contano... la sfida è trovare una forma chiusa per il valore atteso (io non ci sono ancora riuscito)

[franco]

Con la scatola a 3 cerini torna anche a me il conto di Enrico.
Adesso il problema è generalizzare a N cerini, .... mi sembra dura (almeno col metodo che ho usato io).

P.S. Questo quesito ricorda molto da vicino un problema pubblicato su RM di questo mese, o sbaglio?

[franco]

Forse era meno dura di quanto pensavo. (forse...)



ciao

[panurgo]

P.S. Questo quesito ricorda molto da vicino un problema pubblicato su RM di questo mese, o sbaglio?

In questo caso, $p = \frac 1 2$, ma $N$ non è fissato (e c'è un'altra piccola differenza)

Forse era meno dura di quanto pensavo. (forse...)

...forse... (...anche se corretta, questa non è una forma chiusa)

P.S.: il post l'ho preparato prima di leggere RM 103

[franco]

Cosa intendi per "forma chiusa"?

(comunque, aperta o chiusa che sia la forma, il fatto di aver trovato una soluzione NON SBAGLIATA mi inorgoglisce non poco .
Un anno fa non ci avrei neppure provato!)


P.S. Mica pensavo che l'avevi copiato ho solo notato la somiglianza (ed anche le differenze!)

ciao

[Admin]

Ciao Franco,
non so se la tua risposta vada bene;
però la probabilità che, quando viene presa una scatola vuota, nell'altra ci siano esattamente $k$ cerini (evento $e$), ci è data da:

$p(e)={2n-k \choose n}\cdot\(\frac 1 2\)^{2n-k}$

Questa probabilità non è farina del mio sacco;
per chi vuole: http://en.wikipedia.org/wiki/Banach's_matchbox_problem

a questo punto moltiplicando questa probabilità per $k$ e sommando i valori per ogni $k$ si ha:

$\sum_{i=0}^{n}{{2n-i \choose n}\cdot\(\frac 1 2\)^{2n-i}\cdot i}$

che ci dovrebbe dare in media il numero di cerini che vengono buttati da Banach, supposto che le scatole ne contengano inizialmente $n$.

SE&O

Sono di fretta, per cui scappo.

Ciao
Admin

[delfo52]

e se SB adottasse la strategia di buttare le due scatole ogni volta che trova un singolo cerino (dopo averlo ustao, of course!) ?

[panurgo]

P.S. Mica pensavo che l'avevi copiato ho solo notato la somiglianza (ed anche le differenze!)

Non avevo pensato questo: solo che l'aver ponderato questo problema (attribuito a Banach stesso, cfr. il link nel post di Admin) mi ha permesso di risolvere rapidamente (??) il problema di RM.

A presto la strategia che ho usato io per la soluzione

P.S.: una forma chiusa è per esempio

$\sum_{\script k = 0}^{\script n} {2^{\script k} \/ {2n - k \choose n}} \/ = \/ 2^{\script 2n}$

Quello che vorrei è

$\left \langle k \right \rangle \/ = \/ 2^{\script -2n} \/ \sum_{\script k = 0}^{\script n} k \/ {2^{\script k} \/ {2n - k \choose n}} \/ = \/ \text ?$

P.P.S: la tua soluzione è equivalente, ma manca $?$

P.P.P.S: la soluzione nella pagina di Wikipedia è sbagliata (per un refuso, come si evince dal testo) per un fattore $\frac 12$

[franco]

P.P.P.S: la soluzione nella pagina di Wikipedia è sbagliata (per un refuso, come si evince dal testo) per un fattore $\frac 12$

ohibò,

Stavo giusto rispondendo che dai miei calcoli risultava che la formula di Wikipedia dava gli stessi risultati della mia e adesso scopro che è sbagliata?
Forse ho sbagliato i calcoli!

A parte ciò, volevo rispondere "a naso" al quesito di Enrico:
Secondo me si può usare esattamente la stessa formula considerando però come se le scatole avessero un fiammifero in meno.
Non ho fatto grandi calcoli o approfondimenti quindi potrei sbagliare di grosso.
(mettiamo le mani avanti che è meglio!)

[Gianfranco]

Ciao a tutti,

Ho preparato il seguente messaggio prima di leggere la formula di Franco e il dibattito che ne segue, comunque vi invio alcune simulazioni che ho fatto e che potrete confrontare con le vostre formule.

Credo che la versione originale del problema sia quella proposta da Panurgo.
Tuttavia è valida anche la variante proposta da Enrico (che mi sembra leggermente più abbordabile).

Non ho cercato la formula risolutiva (purtroppo non mi sembra facile e non ho molto tempo a disposizione), ma mi sono divertito a fare due simulazioni in Decimal Basic.
Riporto qui i risultati e i relativi programmi.
C'è anche un accenno ad una misteriosa formula che risolverebbe il problema (variante di Panurgo)

--------------------------------
Risultati simulazione A (variante Enrico)
Il programma ha eseguito 100 000 prove per ogni caso, da 1 a 10 cerini per scatola.
I numeri delle due colonne sono:
1) Num. cerini per scatola;
2) Cerini sprecati (in media per ogni coppia di scatole)
---
1 ; 1
---
2 ; 1.49631
---
3 ; 1.87189
---
4 ; 2.1856
---
5 ; 2.4599
---
6 ; 2.7134
---
7 ; 2.93181
---
8 ; 3.14658
---
9 ; 3.34818
---
10 ; 3.52225
---

--------------------------------
Risultati simulazione B (variante Panurgo)
Il programma ha eseguito 10 000 prove per ogni caso, da 1 a 20 cerini per scatola.
I numeri delle tre colonne sono:
1) Num. cerini per scatola;
2) Cerini sprecati (in media per ogni coppia di scatole);
3) Risultato di una formula approssimata che risolverebbe il problema.
(per ora non scrivo la formula)

1 ; .4971 ; .692568750643269
---
2 ; .8666 ; .994711402007163
---
3 ; 1.1844 ; 1.28014505554696
---
4 ; 1.4497 ; 1.5388531259649
---
5 ; 1.7089 ; 1.77544577422218
---
6 ; 1.9102 ; 1.99428262875157
---
7 ; 2.1197 ; 2.19865427934385
---
8 ; 2.3275 ; 2.39100938341218
---
9 ; 2.5197 ; 2.57320069580246
---
10 ; 2.7033 ; 2.74666064392082
---
11 ; 2.8738 ; 2.91251987844181
---
12 ; 2.9972 ; 3.071687599191
---
13 ; 3.1633 ; 3.2249069814793
---
14 ; 3.3299 ; 3.37279425441778
---
15 ; 3.4935 ; 3.51586684644726
---
16 ; 3.6434 ; 3.65456406426899
---
17 ; 3.7772 ; 3.78926256496602
---
18 ; 3.8925 ; 3.920288124951
---
19 ; 4.0203 ; 4.04792472671767
---
20 ; 4.1351 ; 4.17242167014133
---

---------------------------------------
Programmi in Decimal Basic che ho utilizzato.

Simulazione A

FOR k = 1 TO 10
LET a = k
LET b = k
LET NumProve = 100000
LET SommaAv = 0
LET na=a
LET nb=b
RANDOMIZE
FOR i = 1 TO NumProve
DO
LET e = INT(2*RND+1)
IF e=1 THEN LET na=na-1
IF e=2 THEN LET nb=nb-1
IF na=0 OR nb=0 THEN
LET SommaAv=SommaAv+na+nb
LET na=a
LET nb=b
EXIT DO
END IF
LOOP
!'PRINT SommaAv
NEXT i
PRINT k;SommaAv/NumProve
PRINT "---"
NEXT k

END

---------------------------------------
Simulazione B
FOR k = 1 TO 20
LET a = k
LET b = k
LET NumProve = 10000
LET SommaAv = 0
LET na=a
LET nb=b
RANDOMIZE
FOR i = 1 TO NumProve
LET na=a
LET nb=b

DO
LET e = INT(2*RND+1)

IF e=1 THEN
IF na = 0 THEN
LET SommaAv=SommaAv+nb
EXIT DO
ELSE
LET na=na-1
END IF
END IF

IF e=2 THEN
IF nb = 0 THEN
LET SommaAv=SommaAv+na
EXIT DO
ELSE
LET nb=nb-1
END IF
END IF
LOOP

NEXT i
PRINT k;SommaAv/NumProve; ((2*k+1)/SQR(PI*k))-1

PRINT "---"
NEXT k

END

Buona notte!
Gianfranco

[franco]

Ho fatto anchio delle prove numeriche per vedere se, son la forza bruta, riuscivo a trovare una forma chiusa.

Con excel (so che a Gianfranco non piace ma io mi ci trovo bene), ho calcolato i valori sino a N=49 (poi è andato in tilt).

Non sono riuscito a ricavarne nulla salvo:

Un grafico del numero di cerini buttati (Y) in funzione di N:


Un secondo grafico Y/N in funzione di N:


Y è naturalmente un razionale nella forma a/b.
b si trova facilmente: $b=2^{2N-1}$
per trovare a ho cercato di analizzare la sequenza ma senza successo.

Solo a livello di curiosità, facendo un grafico di $a=2^{2N-1}Y$ in funzione di N in scala logaritmica si ottiene una curva che assomiglia moltissimo ad una retta:


ciao

[Admin]

P.P.P.S: la soluzione nella pagina di Wikipedia è sbagliata (per un refuso, come si evince dal testo) per un fattore $\frac 12$

Si, lo avevo notato anch'io;

comunque ho provveduto a correggere l'errore su wikipedia.

Ciao
Admin

[franco]

Volevo solo aggiungere che ho verificato l'equivalenza delle formule risolutive mia e di Wikipedia:

per $k=N-i$


Questa è la tabella dei valori per N sino a 17, qualora qualcuno fosse interessato a trovare un forma chiusa con questa strada:



ciao