Newsgroup: it.hobby.enigmi
Titolo: il fuggitivo

un fuggitivo scappa e improvvisamente si trova a dover scegliere tra tre 
ponti:
.il primo ponte e' il piu' sicuro di tutti,
.il secondo potrebbe crollare, ed e' del 20% piu' insicuro rispetto al primo
.il terzo ponte e' pieno di serpenti velenosi mortali che potrebbero 
attaccare chi lo attraversa. Questo rende il terzo ponte
quattro volte piu' pericoloso del secondo.
il fuggitivo vuole attraversare indenne il ponte, ma deve tener conto 
che dall'altra parte del fiume c'e' una guardia ad aspettarlo pronta a 
sparare, la quale a sua volta deve scegliere un ponte particolare su cui 
appostarsi, senza sapere cosa ha scelto il fuggitivo.
Se la guardia sceglie lo stesso ponte scelto dal fuggitivo, il fuggitivo
viene ucciso dalla guardia (sempre che non sia gia' perito per la 
pericolosita' del ponte).
Come si comporta la guardia?
Come si comporta il fuggitivo?

 Come si comporta il fuggitivo?
Fa un ragionamento simile alla guardia ed esclude il terzo. Poi potrebbe
scegliere il secondo visto che la guardia si mette sul primo. Ma come
detto prima la guardia potrebbe intuire questo ragionamento ed aspettare
proprio sul secondo, alchè il fuggitivo potrebbe scegliere il primo...
Conclusione "intuitiva":
La guardia sul primo e il fuggitivo sul secondo...
ciao
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

Direi che e' un classico caso di paradosso da teoria dei giochi, con le
classiche ripercussioni sulle teorie economiche ;-)))
Venendo alla pubblicita' durante le ferie ho letto un - IMHO -
interessantissimo libro di P. Odifreddi dal titolo "C'era una volta un
paradosso" (gugolando troverete casa editrice, indice e qualche brano) che
tratta in maniera piuttosto estesa, ma anche con una certa profondita', dei
vari tipi di paradossi (logici, visivi, ecc.).
Ciao a tutti.
Tom Cat
P.S. Tanto per precisare, non ho nessun grado di parentela con Odifreddi :-)

no, spiacente. vorrei darti qualche indizio, ma mi limito a
confermare che si tratta di un problema di teoria dei giochi.
Ciao.



Riepilogando:
 - se il fuggitivo passa dal ponte 1, ha probabilità pari a 0 di morire sul
ponte;
 - se passa dal ponte 2, ha probabilità pari a 0,2 di morire sul ponte;
 - se passa dal ponte 3, ha probabilità pari a 0,8 di morire sul ponte;
 - se sceglie il ponte che ha scelto la guardia, ha probabilità pari a 1 di
morire (solo dopo essere uscito indenne dal ponte, ovviamente).
In una tabella a doppia entrata (N.B.: da visualizzare con un carattere non
proporzionale!) metto le probabilità di morire del fuggitivo, in
corrispondenza del ponte scelto da ognuno dei due (G=guardia, F=fuggitivo,
T=totale):
\G|  1  |  2  |  3  |  T  |
F\|     |     |     |     |
--+-----+-----+-----+-----+
1 | 1   | 0   | 0   | 1   |
--+-----+-----+-----+-----+
2 | 0,2 | 1   | 0,2 | 1,4 |
--+-----+-----+-----+-----+
3 | 0,8 | 0,8 | 1   | 2,6 |
--+-----+-----+-----+-----+
T | 2   | 1,8 | 1,2 |     |
--+-----+-----+-----+-----+
Il fuggitivo sceglierà il ponte che minimizza il totale delle probabilità in
cui viene ucciso, la guardia sceglierà il ponte in cui massimizza il totale
delle probabilità in cui invece il fuggitivo muore (sia per mano sua, che
incidentalmente).
Così il fuggitivo sceglierà il ponte 1, poiché morirà solo nel caso in cui
anche la guardia abbia scelto lo stesso ponte.
Anche la guardia però sceglierà il ponte 1, perché in questo modo massimizza
i casi in cui il fuggitivo viene ucciso.
Entrambi scelgono il ponte 1, il fuggitivo lo attraversa senza problemi e,
una volta uscito, si trova di fronte alla guardia che gli spara.
Ciao,
  Daniele
P.S.: io mi sono fermato ad un "livello di profondità", ma ognuno dei due
potrebbe ragionare su cosa sceglierebbe l'altro ed agire di conseguenza...
in un circolo teoricamente infinito!

 ha scritto nel messaggio
news:3F60563C...@domain.com...

Il fuggitivo deve massimizzare la sua prob. di salvezza, mentre la guardia
tenta di minimizzarla.
Se il fuggitivo sceglie il ponte 1 con prob. a, il 2 con prob. b, il terzo
con prob. 1-a-b, e la guardia sceglie i ponti con prob. x per il primo, y
per il secondo e 1-x-y per il terzo, la prob. di salvezza sarà:
P=a*(1-x)+b*0.8*(1-y)+(1-a-b)*0.2*(x+y)
con a,b e x,y che variano nel triangolo di vertici: (0,0) (0,1) e (1,0).
Con un po' di calcoli, e considerando che i valori che cerchiamo per a,b,x,y
stanno necessariamente sul bordo del
dominio, otteniamo come valore finale della prob. di salvezza: P=4/9.
Ottenibile se a=4/9 b=5/9 e x+y=1 (purché non 0,1 o 1,0)
Ciao
Andrea

 confermare che si tratta di un problema di teoria dei giochi.
Si' ma se permetti non ha una soluzione univoca neanche posta sotto
forma di percentuali. A meno che non si stabilisca a priori che
entrambi debbano seguire una certa strategia. Vediamo se mi spiego;
Davide ha seguito un criterio che mi pare impeccabile dal punto di
vista delle probabilita' esistenti, pero' il passaggio
"Il fuggitivo sceglierà il ponte che minimizza il totale delle
probabilità in
cui viene ucciso, la guardia sceglierà il ponte in cui massimizza il
totale
delle probabilità in cui invece il fuggitivo muore (sia per mano sua,
che
incidentalmente)"
non lo si puo' accettare come sicuro, perche' il fuggitivo sa come
dovrebbe teoricamente comportarsi il poliziotto e viceversa, il che ci
porta ad un gioco infinito di deduzioni e controdeduzioni. E' come il
paradosso dell' esame (o dell' esercitazione militare) imprevedibile
http://digilander.libero.it/bluehop/pdx_esame.html
Qualcosa accadra', ma non si sa bene cosa. I due faranno una scelta,
ma non la si puo' conoscere a priori
ciao
fulvio

 in un circolo teoricamente infinito!
Non è infinito, anzi in due o tre livelli si arriva in fondo. Io ho postato
una soluzione, se è giusta, posterò anche i calcoli.
Ciao
Andrea

 ma e' variabile.
No, a me risulta una funzione di lineare di x+y, qualcosa come: P=A*(x+y)+B
con A e B costanti che adesso non mi ricordo più, dovrei rifare i conti,
prima però spiegami bene se le probabilità di superare i tre ponti sono come
le ho intese io.
Ciao
Andrea

spoiler:

La guardia rende equiprobabile il pericolo totale di ogni ponte per il 
fuggitivo.


 Questo non implica che le probabilita' siano 0.8, 0.2 e 0.
Ora posto il ragionamento in dettaglio:
Ovviamente la scelta non può essere deterministica: se la strategia
suggerisse al fuggitivo di scegliere sempre un certo ponte, la guardia
potrebbe mettercisi e lo ucciderebbe ogni volta. Bisogna scegliere i
ponti in maniera aleatoria.
Le prob. di scegliere i tre ponti siano: a, b, 1-a-b
Le prob. di non crollo sono, dal testo: k, 0.8*k, 0.2*k con k sconosciuto.
La guardia si posiziona sui tre ponti con prob.: x,y,1-x-y
P= sum P(scelgo il i-esimo)*P(non crolla)*P(non c'è la guardia) , i=1..3
Otteniamo: P=a*k*(1-x)+b*0.8*k(1-y)+(1-a-b)*0.2*k*(x+y)
Il k si può raccogliere ovunque, quindi lo trascuriamo.
Dato che a, b, 1-a-b devono stare in [0,1]
abbiamo che a e b variano nel triangolo di vertici (0,0),(0,1),(1,0).
Idem per x e y.
Siano inoltre A e B i punti (a,b)=(4/9,5/9)
e (a,b)=(4/29,5/29) rispettivamente (serviranno poi).
Vogliamo trovare a e b che massimizzano P indip. da x e y,
e viceversa x e y che minimizzano P indip. da a e b.
Raccogliamo x e y nell'espressione di P:
P= x*(-1.2a -0.2b +0.2) +y*(-0.2a -b +0.2) + a + 4b/5
Consideriamo i coeff. di x e y uguagliati a 0:
(-1.2a -0.2b +0.2)=0
(-0.2a -b +0.2)=0
Queste sono due rette che dividono il dominio triangolare di a e b
in quattro zone.
(conviene farsi un grafico, si ponga a in ascissa e b in ordinata)
Chiaramente, al di sopra di ciascuna retta il primo
membro risulterà negativo, al di sotto sarà positivo.
Dopodiché, supposti fissati a e b, e x e y variabili, dovremo cercare
di minimizzare P regolando x e y. E' ovvio che se una delle due var. ha
un coeff. positivo converrà porre tale variabile a 0, per non contribuire
ad accrescere il totale, mentre se il coeff. è negativo bisognerà assegnare
alla variabile un valore positivo "il più grande che si può", in modo da
ridurre il più possibile il valore di P. Se invece il coeff. è esattamente
nullo, tale variabile può fare quel che vuole, compatibilmente col valore
assunto dall'altra.
Detto ciò vediamo di regolare x e y per minimizzare P.
Osserviamo che i coeff. di x e y possono essere (vedere grafico):
1) entrambi pos. => zona in basso a sx, P è min se x=y=0 => P=a+4b/5
2) entrambi neg. => zona in alto a dx, P è min se x e y sono i più grandi
possibili: possiamo per ora solo dire che x+y=1 (se infatti fosse x+y<1
potremmo accrescere una delle due variabili, diminuendo P, che quindi non
era minimo).
3) coeff x>0, coeff y<0 => zona in alto a sx, P è min se x=0,y=1
4) coeff x<0, coeff y>0 => zona in basso a dx, P è min se x=1,y=0
Vediamo in dettaglio i 4 casi.
(non consideriamo per ora il caso di coeff. nulli)
1) P=a+4b/5 => max per (a,b)=B => P=8/29
(Ricordiamo che a e b variano nella zona in basso a sx
e a+4b/5=P è una retta sul piano a,b con pendenza fissata e intercetta
crescente con P. Il max valore dell'intercetta per cui la retta resta
nella zona giusta ci dà il valore di P. Si vede subito che tale valore
è quello per cui la retta interseca lo spigolo in (4/29,5/29).
In realtà dobbiamo fermarci prima di raggiungere tale punto, visto che
ivi si annullano i coeff di x e y mentre noi li vogliamo positivi.
Per cui (a,b) sta in un intorno di B e P tende a 8/29 dal basso)
2) Sostituendo x+y=1 e sviluppando abbiamo:
P=(0.8*b-a)*x + 0.2*(1-a-b)+a.
Come scegliamo x? Osserviamo che 0.8b-a può essere sia pos. che neg.
nella zona in alto a dx. Distinguiamo allora i tre casi:
2.1)0.8*b-a>0 => x=0,y=1 => P=0.2*(1-a-b)+a => retta che trasla verso
il basso al crescere di P => P è max. per (a,b) in un intorno di A => P
tende a 4/9 ma è minore.
2.2)0.8*b-a<0 => x=1,y=0 => P=-0.2*a+0.6*b+0.2 => retta che trasla verso
l'alto al crescere di P => P è max. per (a,b) in un intorno di A => P tende
a 4/9 ma è minore
2.3)0.8b-a=0 => sparisce la dipendenza da x => x e y liberi purché x+y=1
=> P=0.2*(1-a-b)+a, come il caso 2.1, risulta Pmax=4/9 con a=4/9 e b=5/9.
3) P= 0.8a -0.2b +0.2 => max per (a,b) in un intorno di B
   => P tende a 8/29 dal basso
4) P= -0.2a +0.6b +0.2 => max per (a,b) in un intorno di B
   => P tende a 8/29 dal basso
Se invece almeno uno dei coeff. è nullo ci spostiamo
lungo le due rette trovate inizialmente, e allora è chiaro
che l'unico punto di massimo per P è il punto A, in corrisp. del quale si
annullano entrambi i coeff.
Se esistessero altri punti li avremmo individuati mentre analizzavamo le
quattro zone.
In sostanza abbiamo un max locale in (a,b)=(4/29,5/29)
e quello assoluto in (4/9,5/9).  (visto che 8/29 < 4/9 !)
La scelta fra queste alternative spetta al fuggitivo, che scegliendo a e b
determina in quale caso ricadano i due coeff. di x e y. Il fuggitivo
sceglierà la massima di queste prob. che è P=4/9, ottenuta con a=4/9
b=5/9 e x+y=1. (recuperando il k inizialmente trascurato otteniamo più
precisamente: P=4k/9,
ma quel che conta sono a,b e x,y)
Ciao
Andrea







spoiler
La guardia sceglie necessariamente il ponte 1, perche' infatti
in tal modo le restano 20/100 che crolli il secondo e 80 per il
terzo.
Il fuggitivo sceglie invece il secondo sapendo che la guardia
sara` sicuramente a protezione del primo altrimenti sguarnito.
-- 
Ciao,		| Attenzione! campo "Reply-To:" alterato ;^)
Remigio Zedda	| E-mail: 
remi...@tiscali.it
	-- Linux 2.4.18 su Debian GNU/Linux 3.0 "Woody"

 sara` sicuramente a protezione del primo altrimenti sguarnito.
Pero' non tieni conto che i due possono mettersi nel panni dell'altro.
Se io fossi la guardia, a avessi fatto il tuo ragionamento, sceglierei il ponte
2.
Se fossi il fuggitivo, viceversa, scegliere il primo.
Non e' la tattica giusta, come e' stato detto.
Ciao