Newsgroup: it.hobby.enigmi
Titolo: Biglietti

10 persone sono in fila davanti ad uno sportello per acquistare ciascuno
un biglietto che costa lire 5000.
Sappiamo che 5 persone hanno le 5000 lire contate, le altre 5 persone
invece pagheranno con una banconota da 10000 lire.
Qual'e' la probabilita' che il cassiere possa vendere i 10 biglietti
senza ricorrere a moneta extra per dare eventuali resti ??
Generalizza con 2n persone delle quali n pagano con 5000 ed n con 10000.
:) dario

...

[SPOILER]
S
 P
  O
  I
 L
E
R
 S
  P
  O
 I
L
E
 R
  S
  P
 O
I
 L
  E
  R
 S
P
La probabilita' richiesta e' 1/6
Costruiamo la seguente tabella a doppia entrate, dove l'indice di riga
rappresenta il numero di spettatori che hanno pagato con 10.000 lire e
quello di colonna quelli che pagano con 5.000 lire. L'elemento i,j indica
la probabilita' che dopo i+j spettatori ancora non si sia fatto uso della
cassa extra
	0      1      2      3      4      5	
0     1      1/2    2/9    1/12   1/42   1/252	
1            5/18   5/18   5/28   5/63   5/252	
2                   10/63  25/126 1/7    1/18 	
3                          5/42   1/6    1/9  	
4                                 1/9    1/6  	
5                                        1/6	
Ovviamente se le 10.000 superano le 5.000 non si hanno speranze di fare a
meno di rifornirsi, quindi la tabella e' mezza vuota.
P(i,j) si calcola a partire da elementi gia' noti:
La probabilita' P(i,j) che non serva extra per le prime i+j persone e'
uguale alla probabilita' P(i-1,j) che non sia servito con uno spettatore da
10.000 in meno moltiplicato per la probabilita' che l'ultimo spettatore
abbia pagato con 10.000, piu' la probabilita' P(i,j-1) per la probabilita'
che l'ultimo abbia pagato con 5.000. Per esmpio,
P(3,4)=P(3,3)*2/4+p(2,4)*3/4
Ma ci deve essere un modo molto piu' semplice, perche' generalizzando ho
trovato che P(n,n)=1/(n+1)!!!
Per ora uso la forza, aspettando che l'astuzia mi assista...
Ciao, Silvio

 Ciao, Silvio
Come al solito e' esatto, speravo di darti piu' filo da torcere. Ora non
ho tempo ti daro' piu' dettagli nel prossimo post.
ciao :)dario

            N
            .
           / \
          .   .
         / \ / \
        .   .   .
       / \ / \ / \
      .   .   .   .
     / \ / \ / \ / \
    .   .   .   .   .
   / \ / \ / \ / \ / \
O .   .   .   .   .   .E
   \ / \ / \ / \ / \ /
    @   @   @   @   @
     \ / \ / \ / \ /
      @   @   @   @
       \ / \ / \ /
        @   @   @
         \ / \ /
          @   @
           \ /
            @
            S
Una formica si trova sul vertice Ovest di una rete romboidale e vuole
raggiungere il vertice Est.
Ad ogni nodo decide a caso la direzione da prendere senza mai tornare
indietro, cioe' procede sempre verso NE o verso SE.
Alcuni ragni (@) sono in attesa nei nodi a sud della diagonale orizzontale,
esclusi i nodi sulla diagonale stessa.
Domande:
1) Che probabilita' ha la formica di arrivare ad Est senza incappare nei
ragni?
2) Che ci fa questo problema in questo thread?
ciao
paolo

 2) Che ci fa questo problema in questo thread?
e' esattamente lo stesso problema di Dario!
Considera le persone che hanno 10.000 lire associate alle svolte a NO,
quelle che hanno le 5.000 come svolte a SO e vedrai che non appena le
persone con 10.000 lire superano quelle con 5.000... il ragno se le mangia!
Ciao, Silvio

 Considera le persone che hanno 10.000 lire associate alle svolte a NO,
ovviamente l'associazione e' quella opposta :(
Questo e' un altro brillante esempio di due enigmi apparentemente
diversissimi tra loro, ma in realta' identici: e' proprio la varieta' dei
possibili enigmi che rende affascinante l'arte del comporre forse ancor
piu' di quella del risolvere...
Ciao, Silvio

 persone con 10.000 lire superano quelle con 5.000... il ragno se le
mangia!
Ho esagerato nel trovare analogie: i due enigmi sono solo SIMILI.
E' vero che alla fine la formica fa 5 passi a NO e 5 a SO (come per i
biglietti), che i passi a NO non devono essere mai inferiori a quelli a SO
(altra analogia), ma i singoli passi qui sono equiprobabili, mentre nel
gioco dei biglietti le probabilita' dipendono dagli spettatori rimasti.
La tabella che ho proposto per la soluzione dei biglietti puo' essere
utilizzata anche qui, e risulta anche piu' semplice:
             1/32
             /  \
          1/16  3/32
          /  \  /  \
       1/8   1/8  21/128
       /  \  /  \  /  \  
    1/4   3/16  9/64  7/32 
    /  \  /  \  /  \  /  \
 1/2   1/4   5/32  7/64 63/256
 /  \  /  \  /  \  /  \  /  \
1   1/4   1/8   5/64 7/128 63/256
 \  /  \  /  \  /  \  /  \  /
  0     0     0     0     0
    \  /  \  /  \  /  \  /
     0     0     0     0
       \  /  \  /  \  /
        0     0     0
          \  /  \  /
           0     0
             \  / 
              0
Dove il numero riportato su ogni nodo rappresenta la probabilita' che la
formica passi per quel nodo e si calcola sommando le probabilita' dei nodi
di sinistra moltiplicate per 1/2 (tranne quelli a margine, a scelta
obbligata)
Ciao, Silvio

Ciao, Silvio
ciao
paolo

 Ciao, Silvio
Molto bene. Lasciamo stare per un momento le probabilita' e pensiamo a
contare i casi  favorevoli dei problemi che stiamo trattando.
1,2,5,14,42,132,429,1430....Questa serie dove l'ennesimo num. e' dato
dalle combinazioni di 2n prese n alla volta diviso n+1, e' nota come
Numeri Catalani scoperti per la prima volta da Eulero.
Questi numeri catalani si incontrano nei piu' diversi prob. combinatori.
Nel problema dei biglietti possiamo mettere +1 per un pagamento con 5000
e -1 per le 10000 e' evidente che un caso e' favorevole se la somma
parziale non scende mai sotto lo zero. Prendiamo il caso semplice di
2n=4 persone, ci sono sei possibili disposizioni:
+1+1-1-1
+1-1+1-1
+1-1-1+1
-1+1+1-1
-1+1-1+1
-1-1+1+1
come vediamo solo le prime 2 sono favorevoli. Possiamo ora rappresentare
ciascona riga con grafico corrispondente, es:
                /\
+1+1+1-1-1-1 = /  \
              /    \
               /\/\
+1+1-1+1-1-1 =/    \ ecc.
Quante differenti "montagne" possono essere disegnate con n tratti in
salita ed n in discesa ? E' evidente la corrispondenza, e qui veniamo
alla idea di Paolo, come contare i percorsi della formica ? Abbiamo gia'
trattato lo stesso problema per i percorsi della torre poco tempo fa!
solo che qui siamo in presenza di una scacchiera triangolare, possiamo
scrivere:
1
1  1
1  2   2
1  3   5   5
1  4   9  14  14
1  5  14  28  42  42
1  6  20  48  90 132 132
1  7  27  75 165 297 429  429 .......
Dove come al solito ciascun elemento e' la somma dei numeri sinistra +
sopra.
Nelle dimensioni date da Paolo la formica ha 42 percorsi sicuri.
Per l'intera scacchiera 6*6 si ottiene:
1   1   1   1   1   1    
1   2   3   4   5   6
1   3   6  10  15  21
1   4  10  20  35  56
1   5  15  35  70 126
1   6  21  56 126 252
Allora la formica ha 42 percorsi sicuri su 252 possibili.
In quanti modi si possono aprire e chiudere n paia di parentesi annidate
o no??      
A ciascuna parentesi aperta associo 5000 lire,  e 10000 alla chiusa.
Es.
+1+1-1+1-1-1 = (()())
+1-1+1+1-1-1 = ()(()) .... 
Tornando alla probabilita' nel caso dei biglietti, le 2n persone si
possono sistemare in (2n,n) modi (Coefficente binomiale orizzontale?!)
E come abbiamo visto i casi favorevoli sono (2n,n)/(n+1), si ottiene,
come ha trovato Silvio 1/n+1.
ciao :)dario

 la probabilita' e' 63/256 =~ 24.7%
Sei sicuro? 
Io trovo fra i due problemi una perfetta analogia, come dal mio msg.
precedente conto 42 casi favorevoli su un totale di 252. 
Fammi sapere :)dario

 1  7  27  75 165 297 429  429 .......
 
Questo schema serve egregiamente per contare i percorsi favorevoli, senza
considerare le probabilita' di ogni singolo percorso, che e' legata
ovviamente alle condizioni del particolare problema. Abbiamo visto due
problemi che pur essendo identici dal punto di vista del numero dei casi
favorevoli, non lo sono da quello delle probabilita', perche' le modalita'
sono diverse: nel caso dei biglietti ogni percorso era equiprobabile, nel
caso della formica erano le singole scelte ad esserlo.
Per poter affrontare in maniera omogenea questi problemi, si puo' ricorrere
a triangoli simili a quelli proposti da Dario, con l'avvertenza di dare un
"peso" ai singoli addendi che tenga conto delle probabilita' di ogni passo.
Nel caso dei biglietti (ovviamente qui e' piu' semplice fare casi fav./casi
pos.) le probabilita' dipendevano dagli spettatori rimasti, e quindi i pesi
da assegnare ai singoli passi erano
 .
 |
5/10
 |
 .-5/9-.
 |     |
4/9   4/8
 |     |
 .-5/8-.-4/7-.
 |     |     |
3/8   3/7   3/6
 |     |     |
 .-5/7-.-4/6-.-3/5-.
 |     |     |     |
2/7   2/6   2/5   2/4
 |     |     |     |
 .-5/6-.-4/5-.-3/4-.-2/3-.
 |     |     |     |     |
1/6   1/5   1/4   1/3   1/2
 |     |     |     |     |
 .-5/5-.-4/4-.-3/3-.-2/2-.-1/1-.
I valori che ho indicato tengono conto come ho gia' detto della "storia"
passata. Per es. dopo 3 passi verso il basso, corrispondenti a 3 persone
che hanno esibito le 5000 lire, avremo 5 persone su 7 con le 10000 e 2 su 7
con le 5000, quindi sara' piu' probabile che la 4° persona in fila abbia le
10000
Possiamo utilizziamo le prob. appena tabulate come coefficienti da
utilizzare nella costruzione della tabella: ogni valore si ottiene sommando
i termini a sinistra ed in alto moltiplicati per il "peso" riportato sul
ramo corrispondente.
1
1/2   5/18
2/9   5/18 10/63
1/12  5/28 25/126 5/42
1/42  5/63  1/7   1/6   1/9
1/252 5/252 1/18  1/9   1/6   1/6
che e' la tabella che ho utilizzato per il problema.
Nel caso della formica la tabella delle prob. e' estremamente semplice:
 .
 |
1/2
 |
 .-1/2-.
 |     |
1/2   1/2
 |     |
 .-1/2-.-1/2-.
 |     |     |
1/2   1/2   1/2
 |     |     |
 .-1/2-.-1/2-.-1/2-.
 |     |     |     |
1/2   1/2   1/2   1/2
 |     |     |     |
 .-1/2-.-1/2-.-1/2-.-1/2-.
 |     |     |     |     |
1/2   1/2   1/2   1/2   1/2
 |     |     |     |     |
 .--1--.--1--.--1--.--1--.--1--.
e quindi la tabella associata e'
1
1/2   1/4
1/4   1/4   1/8
1/8   3/16  5/32  5/64
1/16  1/8   9/64  7/64  7/128
1/32  3/32 21/128 7/32 63/256 63/256
Scusate la ripetizione delle soluzioni precedenti, ma credo che mostrarle a
confronto aiuti la comprensione del metodo generale.
Ciao, Silvio

Ciao, Silvio
ciao
paolo


Grazie delle precisazioni. Rileggendo vedo che la formica sceglie ad
ogni nodo, e questo convalida il calcolo di Silvio. Pensavo che la
formica fosse piu' meticolosa e avesse programmato il viaggio
rivolgendosi ad una agenzia che come noto procede cosi'. Mette 5 palline
nere e 5 bianche in una scatola, dopo aver ben mescolato le estrae una
dopo l'altra. Palla bianca= +1, palla nera =-1. Se la formica va in
rosso viene divorata !!
Esattamente quello che succede me con la mia banca !!
ciao dario.

+AD4-Da tutto questo si puo' trarre una morale:
+AD4-E' piu' conveniente (almeno per le formiche) vivere alla giornata,
piuttosto
+AD4-che programmare in anticipo le proprie azioni :-)
Si, per+API- ai pargoli continuiamo a raccontarla al solito modo la favola della
cicala e della formica, vero? +ADs-o))
Bye
Diego.

ciao dario.
ciao
paolo

 palline nere. 
.. ne bastano due, se le rimetti dentro e tieni il conto delle uscite  ;-)
Ciao, Silvio