[C] posti a caso...

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

matthewtrager
Messaggi: 132
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da matthewtrager » 01 gen 1970, 01:33

Prima di tutto tanti auguri a tutti!
<BR>
<BR>Alooora... Ci sono 100 passeggeri che aspettano di salire su un aereo che ha esattamente 100 posti. Il primo passeggero che sale sull\'aereo ha perso la sua carta di imbarco e cosi\' si siede in un posto qualsiasi. Tutti gli altri passeggeri si siedono al loro posto se lo trovano libero e in uno a caso se e\' occupato. Qual\'e\' la probabilita\' che l\'ultimo passeggero si sieda al proprio posto?
<BR>
<BR>ciao!
<BR>

metafisic
Messaggi: 41
Iscritto il: 01 gen 1970, 01:00
Località: Franconia

Messaggio da metafisic » 01 gen 1970, 01:33

Calcoliamo la probabilità che rimanga senza posto.Questo può avvenire per il primo passaggero(il primo prende il suo) e vale 1/100.Può avvenire per il secondo passaggero e allora dovremmo avere che il primo si siede sul posto del secondo e che questo si sieda sul posto dell\'ultimo.Questa probabilità vael 1/100*1/99. Il posto gli viene sottratto dal k-esimo passeggero con probabilità1/(100*99*...100-k+1) e questi eventi sono disgiunti.La probbilità cercata è dunque:
<BR>
<BR>1-1/100-1/(100*99)-1/(100*99*9<IMG SRC="images/forum/icons/icon_cool.gif">-...-1/(100*99*...*2)
<BR>
<BR>La somma potendosi scrivere in modo più decente.[addsig]
La compactesse est metaphisique.

metafisic
Messaggi: 41
Iscritto il: 01 gen 1970, 01:00
Località: Franconia

Messaggio da metafisic » 01 gen 1970, 01:33

Non so cosa c\'entri la faccina, comunque è un 8.
La compactesse est metaphisique.

matthewtrager
Messaggi: 132
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da matthewtrager » 01 gen 1970, 01:33

qualcosa non mi convince.. (anche perche\' la risposta non torna <IMG SRC="images/forum/icons/icon_razz.gif"> )
<BR>Secondo te ad esempio c\'e\' la probabilita\' del 1/(100*99*98 ) che il posto gli venga sottratto dal terzo passeggero; quindi per te il primo passeggero si siede al posto del secondo, che siede al posto del terzo che a sua volta si siede al posto dell\'ultimo passeggero. Potrebbe pero\' anche succedere che il primo passeggero si sieda subito al posto del terzo, che poi si siede al posto dell\'ultimo, lasciando il secondo libero di sedersi al suo posto. Quindi penso ci siano altri casi che non hai considerato...<BR><BR>[ Questo Messaggio è stato Modificato da: matthewtrager il 02-01-2005 14:56 ]

metafisic
Messaggi: 41
Iscritto il: 01 gen 1970, 01:00
Località: Franconia

Messaggio da metafisic » 01 gen 1970, 01:33

Vero <IMG SRC="images/forum/icons/icon_cool.gif"> ...vediamo di inserirci qualche binomiale
La compactesse est metaphisique.

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 01 gen 1970, 01:33

[OT]
<BR>Non capisco come quelli dell\'AMM ancora accettino di averti fra i loro \"<!-- BBCode Start --><I>contributors</I><!-- BBCode End -->\"... <IMG SRC="images/forum/icons/icon_eek.gif"> <IMG SRC="images/forum/icons/icon_confused.gif"> <IMG SRC="images/forum/icons/icon_razz.gif"> <IMG SRC="images/forum/icons/icon_mad.gif">
<BR>[/OT]

metafisic
Messaggi: 41
Iscritto il: 01 gen 1970, 01:00
Località: Franconia

Messaggio da metafisic » 01 gen 1970, 01:33

cattivone, ho il raffreddore <IMG SRC="images/forum/icons/icon_razz.gif"> [addsig]
La compactesse est metaphisique.

Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz » 01 gen 1970, 01:33

vedi qua:
<BR>
<BR>http://olimpiadi.ing.unipi.it/modules.p ... 40&forum=5
<BR>
<BR>
<BR>(se volete risolverlo per conto vostro, ignorate il link!)
<BR>
<BR> <IMG SRC="images/forum/icons/icon_biggrin.gif"> <IMG SRC="images/forum/icons/icon_biggrin.gif">
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]

Avatar utente
info
Messaggi: 903
Iscritto il: 01 gen 1970, 01:00

Messaggio da info » 01 gen 1970, 01:33

Nn volevo farmi battere da 2 quesiti di tipo elementare in così poco tempo (vedasi DG). Questo spero di averlo risolto: il risultato è ½.
<BR>
<BR>Rinominiamo i posti in modo che la prima persona che entri debba andare al primo posto, la seconda al secondo, e così via….Questo si può sempre fare, magari cambiando le etichette dei sedili. Si fa un po’ di confusione, ma noi abbiamo tempo…
<BR>
<BR>Osservazione (inutile nel procedimento ma simpatica) : l’ultima persona ad entrare entrerà nel primo o nell’ultimo posto. Se per assurdo entrasse in un posto k, la k<sub>esima persona</sub> lo avrebbe trovato libero e lo avrebbe occupato. Contraddizione. Questo spinge fortemente ad ipotizzare il risultato. Magari si possono mettere in corrispondenza biunivoca le combinazioni ma io nn ci sono riuscito.
<BR>
<BR>Immaginiamo che i posti siano n. Chiamiamo
<BR>
<BR>C<sub>t</sub>(n): il numero totale di combinazioni finali (ad ogni posto associamo la persona che lo prende: questo si intende per combinazione) possibili con n posti;
<BR>
<BR>C<sub>f</sub>(n): il numero di combinazioni finali possibili con n posti e con in fondo l’ultimo passeggero;
<BR>
<BR>Osserviamo che: C<sub>f</sub>(n+1) = C<sub>t</sub>(n) per corrispondenza biunivoca…
<BR>Dobbiamo quindi trovare una formula per C<sub>t</sub>(n). Si osserva che:
<BR>
<BR>C<sub>t</sub>(1)=1; C<sub>t</sub>(2)=2 ; C<sub>t</sub>(3)=4 per verifica diretta.
<BR>
<BR>Dimostriamo per induzione che :
<BR>
<BR>C<sub>t</sub>(n) = 2<sup>n-1</sup>.
<BR>
<BR>Supponiamo il tutto vero per 1,2,3,….,n e vediamo il caso (n+1).
<BR>
<BR>Se il primo si mette nel posto (n+1) abbiamo 1 combinazione possibile;
<BR>
<BR>Se il primo si mette nel posto n abbiamo 2 combinazioni possibili;
<BR>
<BR>Se il primo si mette nel posto (n-k) dopo riempiamo i posti 2,3,…,(n-k-1) e qui ogni cliente và al sul posto. Rimangono i posti 1 ed (n-k+1),…,(n+1), cioè k+2 posti. I clienti rimasti sono invece sono sempre k+2 ma quelli con i posti (i biglietti!) (n-k),….,(n+1). Ora è possibile mettere in corrispondenza C<sub>t</sub>(k+2) e le combinazione possibili in questo caso. Basta associare 1<>n-k; 2<>n-k+1; 3<>n-k+2;…; k+2<>n+1. Infatti per quelli in fondo nn cambia assolutamente nulla (i loro posti sono liberi in entrambe le situazioni) mentre quello nel posto (n-k) al quale è associato l’1 sceglie come l’1 un posto a caso. Agli altri nn interessa se (n-k) ha cambiato nome o no! (un disegnino chiarisce tutto, fate un esempio numerico!).
<BR>
<BR>Quindi, potendo variare k da 1 ad (n-2), ed aggiungendo a mano gli altri casi (se il primo si mette nei posti 1,n,n+1):
<BR>
<BR>C<sub>t</sub>(n+1) = C<sub>t</sub>(3)+ C<sub>t</sub>(4)+…+ C<sub>t</sub>(n) + 1+1+2
<BR>C<sub>t</sub>(n+1)= sum<sub>i=2->n-1</sub> 2 <sup>i</sup>+1+2+1= sum<sub>i=0->n-1</sub>2<sup>i</sup> +1= 2<sup>n</sup>
<BR>
<BR>E quindi la tesi è verificata (spero)..
<BR>La probabilità finale è, dato che ogni caso è equiprobabile (vero?):
<BR>
<BR>C<sub>f</sub>(n)/ C<sub>t</sub>(n) = 2<sup>n-1</sup>/2<sup>n</sup>=1/2
<BR>
<BR>Ho scritto il tutto da off-line, prima di leggere cosa ha scritto Talpuz (che ora vado a vedere!)
<BR>
<BR>
<BR>[ Questo Messaggio è stato Modificato da: info il 04-01-2005 22:41 ]<BR><BR>[ Questo Messaggio è stato Modificato da: info il 04-01-2005 22:49 ]

Avatar utente
info
Messaggi: 903
Iscritto il: 01 gen 1970, 01:00

Messaggio da info » 01 gen 1970, 01:33

Beh...ho speso qualche riga in più di Talpuz, ma volevo essere più esplicito <IMG SRC="images/forum/icons/icon_wink.gif">
<BR>
<BR>....no:non và! I casi alla fine nn sono equiprobabili e di questo nn me ne posso sbattere... Bisogna modificare il ragionamento in modo da ragionare sulle probabilità (anche se la linea e le idee risolutive rimangono le stesse) fin dall\'inizio e nn sul numero totale di combinazioni... <BR><BR>[ Questo Messaggio è stato Modificato da: info il 05-01-2005 10:09 ]

DB85
Messaggi: 145
Iscritto il: 01 gen 1970, 01:00
Contatta:

Messaggio da DB85 » 01 gen 1970, 01:33

Il procedimento \"meno faticoso\" è quello di Talpuz (come lui stesso dice). <!-- BBCode Start --><I>A mira di naso</I><!-- BBCode End --> la formula ricorsiva si potrebbe dimostrare per induzione utilizzando questa tua osservazione
<BR>
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2005-01-04 22:34, info wrote:
<BR>C<sub>f</sub>(n+1) = C<sub>t</sub>(n) per corrispondenza biunivoca…
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Ciò non toglie che le tue idee siano molto interessanti.
<BR>
<BR>EDIT: Un\'ultima cosa: matthewtrager conosci la fonte del problema?
<BR><BR><BR>[ Questo Messaggio è stato Modificato da: DB85 il 05-01-2005 11:31 ]
"Le vite degli uomini famosi ci ricordano
Che possiamo rendere sublimi le nostre esistenze
E, morendo, lasciare dietro di noi
Le nostre impronte sulle sabbie del tempo"
Henry Wadsworth Longfellow

matthewtrager
Messaggi: 132
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da matthewtrager » 01 gen 1970, 01:33

non lo so... io lo sentito da un amico...

Avatar utente
frengo
Messaggi: 223
Iscritto il: 01 gen 1970, 01:00

Messaggio da frengo » 01 gen 1970, 01:33

Innanzi tutto, premetto che questa soluzione è venuta in mente allo stage senior di questo(2004)settembre ad un mio amico romano (S.A.), ve la scrivo perchè secondo me è SPETTACOLARE!!!! senza induzione, conteggi, binomiali....
<BR>
<BR>Allora: gli unici 2 posti che l\'ultimo passeggero può trovare liberi sono o il suo, o quello del passeggero infame senza biglietto(ogni altro posto, se fosse mai stato libero sarebbe stato occupato dal suo possessore). uno di questi due posti è sicuramente occupato, ma la persona che lo occupa si è trovata davanti ad una scelta per cui ogni posto era equiprobabile(sia questa persona l\'infame, o quello a cui l\'infame ha preso il posto, o quello a cui l\'infame ha preso il posto ha preso il posto, ecc.) quindi la probabilità che l\'ultimo passeggero trovi il suo posto libero(o il suo posto occupato)è 1/2.
<BR>Scusate per l\'italiano.
<BR>COMPLIMENTI A ST. AT.
<BR>Ciao a tutti

Avatar utente
what
Messaggi: 158
Iscritto il: 01 gen 1970, 01:00
Località: roma

Messaggio da what » 01 gen 1970, 01:33

Grandissimo St.!!!!!! <IMG SRC="images/forum/icons/icon_biggrin.gif"> <IMG SRC="images/forum/icons/icon_biggrin.gif"> <IMG SRC="images/forum/icons/icon_biggrin.gif">

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2005-01-09 18:04, frengo wrote:
<BR>Allora: gli unici 2 posti che l\'ultimo passeggero può trovare liberi sono o il suo, o quello del passeggero infame senza biglietto(ogni altro posto, se fosse mai stato libero sarebbe stato occupato dal suo possessore). uno di questi due posti è sicuramente occupato, ma la persona che lo occupa si è trovata davanti ad una scelta per cui ogni posto era equiprobabile(sia questa persona l\'infame, o quello a cui l\'infame ha preso il posto, o quello a cui l\'infame ha preso il posto ha preso il posto, ecc.) <font color=red>quindi la probabilità che l\'ultimo passeggero trovi il suo posto libero(o il suo posto occupato)è 1/2</font>.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Beh, insomma, scusate se faccio il Pierino della situazione, ma letta così ci vuole un po\' per capire che funziona (almeno, io non l\'ho trovata così convincente...). Qualcuno mi spiega meglio la parte in rosso?
<BR>
<BR>Ciao.
<BR>
<BR>M.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Bloccato