Newsgroup: it.hobby.enigmi
Titolo: Parcheggiare in germania

Un problemino di probabilità dalla rivista Archimede:
Giovanni è un italiano emigrato in Germania, dove vive in un condominio
insieme a 15 tedeschi. Ciascuno dei 16 condomini ha il suo posto
macchina. Giovanni, da buon italiano, quando arriva parcheggia in un
posto libero a caso. I tedeschi, invece, quando rincasano parcheggiano
al proprio posto auto, a meno che questo non sia già occupato, nel qual
caso posteggiano anche loro a caso.
Una sera Giovanni arriva quando il parcheggio è ancora tutto libero.
Qual è la probabilità che l'ultimo condomino a rientrare trovi il
proprio posto auto libero?
[Forse è vecchio, però il testo è divertente...]
Maurizio
-- 
Per rispondermi via e-mail togli l'ovvio.

 ha scritto nel messaggio 
news:1ifpwuz.a1a2a51akk4kyN%frigeni_ovvio@tiscali_ovvio.it...

Molto ma molto ma molto interessante.
Ed anche leggermente controintuitivo, aggiungo. Cosa che aggiunge pepe 
all'enigma.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
50%
Vediamo perché.
Supponiamo che gli inquilini rientrino a casa ordinatamente, per numero 
(organizzazione tedesca!)
L'italiano occupa il posto "n". Rientrano tutti fino ad "n" e parcheggiano 
nei propri box, n può scegliere tra parcheggare al primo posto (quello 
dell'italiano), al 16 oppure in un altro posto maggiore del suo.
- Se parcheggia all'1, la catena si chiude e tutti quelli che arrivano dopo 
troveranno il posto libero, compreso il 16.
- Se parcheggia al 16 allora qualsiasi cosa succeda sappiamo che il 16 
troverà il posto occupato.
- Se parcheggia in qualsiasi altro posto "m" maggiore del suo allora la 
questione si ripropone tale e quale per l'inquilino "m"; parcheggiare all'1, 
al 16 o altrove?
Per simmetria parcheggiare all'1 o al 16 sono equiprobabili per uno che 
sceglie a caso, per cui il 16 ha il 50% di probabilità di trovare il posto 
libero.
Riassumendo: il 16 trova il suo posto occupato solo se un suo coinquilino ha 
scelto di parcheggiare al 16 pur potendo parcheggiare all'1; trova il posto 
libero se un suo coinquilino ha scelto di parcheggiare all'1 pur potendo 
parcheggiare al 16.
Il caso in cui l'italiano parcheggia direttamente al posto 16 è 
controbilanciato dal caso equiprobabile in cui parcheggia al suo posto senza 
farsi riconoscere! La simmetria vince ancora una volta.
-- 
Ciao, Silv:o) 

 parcheggiare al 16.
Mi sembra che la tua giustificazione "senza calcoli" sia convincente. Io
ci sono arrivato in modo più formale così: indico con p(n) la
probabilità che l'ultimo inquilino parcheggi al suo posto, quando ci
sono ancora n posti liberi (fra cui l'ultimo e quello dell'italiano) e
il primo che arriva parcheggia a caso (o perché è italiano, o perché
trova il suo posto occupato). A noi evidentemente interessa p(16).
Si vede che vale la relazione ricorsiva:
p(n) = 1/n + 1/n p(n-1) + 1/n p(n-2) + ... + 1/n p(2)
(il ragionamento è essenzialmente quello che hai fatto tu sui possibili
casi) e d'altra parte p(2) = 1/2, da cui si ricava a p(3) = 1/2, p(4) =
1/2, ecc.



Ancora più rapidamente, senza fare calcoli:
Osserviamo che il fatto che un tedesco che trovi il proprio posto occupato 
si sposti in un posto libero a caso, è equivalente a porre che il tedesco 
prenda possesso del proprio spazio,
sbattendo fuori Giovanni, il quale andrà nuovamente in un posto a caso. (I 
ruoli di Giovanni e del tedesco di turno si scambiano, ma la sostanza del 
problema resta la stessa)
A questo punto, dopo i primi 14 tedeschi, piazzati regolarmente, a Giovanni 
restano due posti liberi, il suo e quello del 16 inquilino. Pertanto c'è una 
possibilità su due che l'ultimo tedesco
trovi il suo posto libero.
Ciao
Andrea

 sbattendo fuori Giovanni, il quale andrà nuovamente in un posto a caso.
Bellissimo! 


 si scambiano, ma la sostanza del problema resta la stessa)
E' quello che intendevo quando dicevo che il primo tedesco che trova il 
posto occupato può sciogliere il nodo gordiano scegliendo il posto 1 o il 16 
oppure "passare la mano" ad un altro inquilino occupandogli il box.
Ma l'immagine del tedesco che sbatte fuori Giovanni e se ne va a dormire è 
molto più efficace.
Per me in questi problemi la parte più stimolante è - una volta trovata la 
soluzione e scoperto che è semplice - trovare un modo elegante per 
giustificarla. Il tuo è davvero bello, rosico molto di non averlo trovato 
ieri notte. Complimenti.
-- 
Ciao, Silv:o) 

Splendido problema! Mi sono permesso di includerlo qui:
http://www.marianotomatis.it/index.php?id=blog&section=enigmi&url=103
Se avete qualcosa in contrario, fatemelo sapere.
Grazie!
Mariano