giovedì, luglio 15, 2010

Il truello

Tre rivali si radunano all'alba per risolvere una querelle mediante una sparatoria. Una sorta di duello, ma con tre persone. Le regole sono le seguenti:

  • Si tira a sorte chi sarà il primo a sparare, chi il secondo e chi il terzo
  • Si continua a sparare, uno per volta, in quest'ordine finché solo uno resterà in vita
  • Ogni persona decide a chi sparare
  • Tutti sanno che A ha una probabilità di uccidere il suo bersaglio del 100%, B dell'80% e C del 50%
  • Ciascuno sceglie la strategia ideale
  • Nessuno viene colpito di striscio e i partecipanti rispettano tutte le regole
Chi ha più possibilità di vincere il "truello" e quante sono esattamente le sue probabilità di vittoria?

10 commenti:

Davi ha detto...

Partiamo con alcune considerazioni.
Quando una persona deve scegliere a chi sparare, cercherà sempre di colpire l'avversario che ha la percentuale maggiore di successo, in quanto è più probabile che il colpo del suddetto avversario vada a segno, uccidendolo.
Dato che l'ordine di estrazione è casuale, bisogna considerare tutti e 6 i casi (equiprobabili): ABC, ACB, BAC, BCA, CAB e CBA.
Calcolate le percentuali di successo di ognuno dei tre contendenti, è sufficiente sommarle e dividerle per 6, otteendo così il risultato richiesto.
A: 13/40 = 32,5%
B: 32/135 = 23,7%
C: 473/1080 = 43,8%

Walter ha detto...

La soluzione non è corretta, hai tralasciato un po' di considerazioni che alterano il risultato, rispetto a quello da te ipotizzato.

grAz ha detto...

Non ho trovato nulla di meglio che farmi un mega-diagramma ad albero per provare a risolvere questo.

Allora, dividiamo i 6 casi, ciascuno con probabilità 1/6 (16,6% circa), ABC, ACB, BAC, BCA, CAB, CBA.

*PREMESSA*
Calcolare le probabilità dei pistoleri è facile finché è in vita A. A, infatti, è infallibile, e gli altri sparano sempre a lui.
Il difficile è calcolare le probabilità quando rimangono B e C, perché nessuno dei due è infallibile.

SE rimangono solo B e C, e spara per primo B:
vince nei 4/5 dei casi (80%);
in 1/5*1/2=1/10 dei casi vince C (che dopo spara e al 50% lo uccide);
rimane 1/10 dei casi in cui si ripresenta la situazione di partenza, e spara di nuovo per primo B. Così in 1/10*4/5 dei casi vince B, e in 1/10*1/10 dei casi vince C, e in 1/10*1/10 dei casi si ritorna alla situazione di partenza.
Passando al limite, quindi, le probabilità diventano la somma di una serie:
P(B)=SOMMA [n=0 a inf.to] di (4/5*(1/10)^n)=4/5* SOMMA(1/10)^n= 4/5*1,1111... = 0,8888... =(approx) 88,8%
P(C)=SOMMA [n=1 a inf.to] di (1/10)^n = 0,1111... =(approx) 11,1%
(la somma delle due probabilità è, correttamente, 1, perché in infiniti tentativi uno dei due prevarrà di sicuro).

Allo stesso modo, se rimangono solo B e C e spara per primo C:
vince in 1/2 dei casi;
se non uccide B, quello lo uccide in 1/2*4/5=4/10 dei casi;
ancora una volta in 1/10 dei casi si ritorna alla situazione di partenza. Quindi:
P(B)=SOMMA [n=0 a inf.to] di (4/10*(1/10)^n)=4/10* SOMMA(1/10)^n= 4/10*1,1111... = 0,4444... =(approx) 44,4%
P(C)=SOMMA [n=0 a inf.to] di (1/2*(1/10)^n) = 0,5555... =(approx) 55,5%

Visto questo passaggio, il più difficile, il resto è solo diagramma ad albero e composizione di probabilità. Vediamo i casi uno per uno.

*ABC*
A spara a B e lo uccide.
Rimangono C e A, C spara per primo. Se vince (P=1/2), ha vinto, sennò lo ucciderà A dopo.

P(ABC_A)=50%
P(ABC_B)=0
P(ABC_C)=50%

*ACB*
Caso del tutto identico al precedente.

P(ACB_A)=50%
P(ACB_B)=0
P(ACB_C)=50%

*BAC*
B spara ad A.
In 1/5 dei casi NON lo uccide. Spara allora A e uccide B. A questo punto spara C, nel 50% dei casi vince uccidendo A, e nel restante 50% verrà ucciso da A subito dopo.
In 4/5 dei casi lo uccide. Rimangono B e C, spara per primo C. Come visto prima quindi vincerà C nel 55,5% dei casi e B nel 44,4% dei casi.

P(BAC_A)=20%*50%=10%
P(BAC_B)=80%*44,4%=35,5%
P(BAC_C)=20%*50%+80%*55,5%=54,4%

*BCA*
B spara ad A.
In 1/5 dei casi NON lo uccide.
Spara allora C ad A. Se lo uccide (50%), rimangono B e C con B primo a tirare: B 88,8%, C 11,1%.
Se NON lo uccide (50%), A spara a B e lo uccide. Rimangono C e A, spara primo C. C 50%, A 50%.

In 4/5 dei casi lo uccide. Rimangono B e C, spara per primo C. C 55,5% e B 44,4%.

P(BCA_A)=20%*50%*50%=5%
P(BCA_B)=20%*50%*88,8%+80%*44,4%=44,4%
P(BCA_C)=20%*50%*(11,1%+50%)+80%*55,5%=50,5%

*CAB*
C spara ad A.
50% lo uccide. Rimangono B e C, spara primo B. B 88,8%, C 11,1%.
50% non lo uccide. A uccide B, C 50%, A 50%.

P(CAB_A)=50%*50%=25%
P(CAB_B)=50%*88,8%=44,4%
P(CAB_C)=50%*11,1%+50%*50%=30,5%

*CBA*
C spara ad A.
50% lo uccide. Rimangono B e C, spara primo B. B 88,8%, C 11,1%.
50% non lo uccide. B spara ad A.
80% lo uccide. Rimangono B e C, spara primo C. C 55,5% e B 44,4%.
20% non lo uccide. A uccide B e rimane con C che spara per primo. C 50%, A 50%.

P(CBA_A)=50%*20%*50%=5%
P(CBA_B)=50%*88,8%+50%*80%*44,4%=62,2%
P(CBA_C)=50%*11,1%+50%*80%*55,5%+50%*20%*50%=32,7%

Quindi, in totale:

P[A] = 1/6*(50%+50%+10%+5%+25%+5%)= 24,17%
P[B] = 1/6*(35,5%+44,4%+44,4%+62,2%)= 31,08%
P[C] = 1/6*(50%+50%+54,4%+50,5%+30,5%+32,7%)= 44,68%


È interessante notare come il pistolero più scarsamente dotato è quello che ha di gran lunga più possibilità di uscire vincitore... in barba a Darwin e alla selezione naturale! :D

Davi ha detto...

La scelta di una strategia vale fino a quando ci sono tutti e 3 i contendenti in vita. Non appena uno muore, la sfida diventa uno scontro a due dove ognuno cerca di uccidere l'altro.
Quindi, dati i 6 casi equiprobabili ABC, ACB, BAC, BCA, CAB e CBA, vediamo come potrebbe ragionare il primo che deve sparare.

Supponiamo di essere nei primi due casi, e che quindi il primo colpo sia sparato da A. A è consapevole che ucciderà il suo bersaglio e, se sopravvive al colpo di quello rimasto in vita, con un secondo colpo la ucciderà, vincendo in questo modo la sfida. Quindi deve lasciare in vita quello che ha
la probabilità di successo minore, cioè C, perciò sparerà a B uccidendolo.
Ora C sa che ha un solo colpo, con probabilità 1/2 di uccidere A; se fallisce sarà lui stesso a morire il turno seguente.
Quindi in questi primi 2 casi, le probabilità di uscire vittoriosi dalla

sfida sono:
A 1/2
B 0
C 1/2

Analizziamo il caso BAC.
B vede che il secondo a dover sparare sarà A. Se B decidesse di sparare a C, sia che lo ammazzi (in questo caso rimmarrebbero solo B e A), sia che lo lasci in vita, si rende conto che poi A sparerebbe a lui, uccidendolo.
Quindi l'unico modo per poter sperare di aver la meglio è puntare proprio ad ammazzare A. Si hanno ora 2 casi:
-con probabilità 1/5 A sopravvive. Dato che è il secondo a dover sparare e che sono vivi sia B che C, seguirà la strategia che avrebbe seguito nel caso in cui fosse stato il primo a sparare (quella esposta nei due casi precedenti)
-con probabilità 4/5 A muore. In questo caso il duello si riduce ad una sfida tra B e C a "chi colpisce per primo".

In totale, le probabilità di successo dei tre contendenti sono:
A 1/10
B 16/45
C 49/90

Caso BCA.
B deve decidere a chi sparare.
Supponiamo che decida di sparare a C. Se lo ammazza, poi verrà ucciso a sua volta da A, dato che sono rimasti in due. Se non lo ammazza, non gli resta che sperare che C spari ad A uccidendolo, altrimenti sarà lo stesso B a morire. va notato che B è convinto della scelta di C, perchè se quest'ultimo decidesse di sparare a lui, poi dovrebbe vedersela col colpo infallibile di A. Tutto sommato, è da notare che la persona che ha più probabilità di
morire, nel caso appena analizzato, è proprio B.
Quindi B deciderà di sparare ad A. Se lo uccide, poi la sfida continua tra B e C.
Se B non uccide A, é C a dover prendere la decisione su chi sarà il suo bersaglio. Se uccidesse B, poi morirebbe per mano di A.
Se sparasse ad A, poi verrebbe molto probabilmente ucciso da B.
Quindi la sua migliore prospettiva è quella di sparare e mancare il
bersaglio, in modo tale da lasciare che A uccida B ed avere cosi 1 possibilità su 2 di uccidere a sua volta A, prima che sia il turno del pistolero infallibile. Quindi in questo caso a C conviene sparare in alto, in
mezzo ad un campo o comunque lontano da A e da B.
Quindi, capita la scelta di C, il caso si riduce come a BAC, con le stesse probabilità di vittoria.

Caso CAB.
Capito il fatto che C non mira ne ad A ne a B, finchè entrambi sono vivi, questo caso si riduce come i primi due.

Caso CBA.
Anche in questo caso C farà in modo che i due pistoleri più bravi si affrontino tra di loro, subentrando solo alla morte di uno dei due.
COsì facendo questo caso si riduce come quelli in cui è B a sparare per primo.

Alla fine avremo le seguenti possibilità di uscire vittoriosi dal conflitto:

A 1/6 * (3 * 1/2 + 3 * 1/10) = 3/10
B 1/6 * (3 * 0 + 3 * 16/45) = 8/45
C 1/6 * (3 * 1/2 + 3 * 49/90) = 47/90

che in percentuale sono:

A 30% ; B 17,78% ; C 52,22%

Quindi, chi ha più probabilità di uscire vincente dal "truello" è C col 52,22% di possibilità.

PS: dal testo dell'enigma ho visto solo che c'è l'obbligo di sparare, ma non mi pare che qualcosa vieti a C di sparare altrove per mancare appositamente i suoi avversari. Spero che come soluzione sia accettabile, altrimenti mi
ritirerò a fare molti altri pensieri su come risolverlo.

Ciao ciao!

grAz ha detto...

Davi, la tua considerazione sul fatto che a C convenga sparare in aria è interessante, e in effetti aumenta ulteriormente le chances di successo di C rispetto alla mia soluzione, ma non so se sia consentita dal testo, in quanto nel momento in cui lo fai sparare in aria di fatto decidi arbitrariamente che per quel colpo le sue probabilità di successo non siano, come affermato dal testo, del 50% ma dello 0%...

Piuttosto, scusami, posso chiederti come calcoli le probabilità di vittoria di B vs C? Ho visto che facendo la divisione delle frazioni che mostri, ti esce la stessa probabilità che viene a me, ma non ho capito che metodo hai usato...

Walter ha detto...

Le percentuali date sono riferite al caso in cui chi spara decida effettivamente di colpire il suo bersaglio. Se uno spara deliberatamente in aria allora le sue probabilità di colpire il bersaglio crollano necessariamente a zero. Mi rendo conto che l'espressione "ogni volta che spara" sia stata un po' infelice, e me ne scuso. Correggo il testo e nei prossimi giorni verifico per bene le soluzioni suggerite da voi due (ora purtroppo non posso dato che ho un esame e sono impegnatissimo).

grAz ha detto...

In tal caso, a meno di errori di calcolo direi che la soluzione corretta è quella di Davi.
Io ho proceduto considerando che ogni pistolero fosse obbligato a "sparare per uccidere", e avesse sempre e comunque probabilità di successo pari alla sua abilità.

Davi ha detto...

Ciao grAz.

Vedo di spiegarti come calcolo la probabilità B vs C con un esempio.

Prendiamo BAC.

B spara ad A e lo uccide; quindi siamo già nel caso 0,8 in cui ha successo.
Tocca ora a C che spara a B. Ha una possbilità di 0,5 di ucciderlo ( e in questo caso il gioco finisce) e una possibilità di 0,5 di lasciarlo in vita.
Se B sopravvive, spara a C e ha una possibilità dello 0,8 di ucciderlo e una possibilità dello 0,2 di lasciarlo in vita.
Se C rimane vivo, il gioco ricomincia dal punto precendente.
Calcolo ora la probabilità di vittoria di B:
0,8*0,5*0,8 + 0,8*0,5*0,8*0,5*0,2 + 0,8*0,5*0,8*0,5*0,2*0,5*0,2 + ...
Ai puntini va sostituita una serie infinita di addendi in cui ognuno è uguale al precedente moltiplicato per 0,5*0,2.
Raccolgo ora 0,8*0,5*0,8 a fattor comune, ottenendo:
0,8*0,5*0,8 * (1 + 0,5*0,2 + 0,5*0,2*0,5*0,2 + ...)

Lavoro ora sull'espressione tra parentesi

1 + 0,1 + 0,01 + ...

Questa somma può essere scritta come una sommatoria di infiniti termini; più precisamente è la sommatoria per i che va da 0 ad infinito di x elevato alla i.
Per x compresi tra 0 e 1, la somma di questa serie è pari a 1/(1-x)
Nel nostro caso x=0,1 quindi posso applicare questo metodo.

PS: ora ho usato i decimali per facilitare la lettura del testo, ma quando faccio i miei conti su carta, uso le frazioni che permettono una semplicità e corretteza maggiori.

Spero di esseri stato utile, ciao ciao!

grAz ha detto...

Ah, ok! Quindi, in sostanza, è lo stesso metodo che ho usato io!

Chiedevo perché vedendo le frazioni ho immaginato che potessi avere trovato un metodo diverso o più semplice... invece, credo che comunque la si giri non si può evitare di passare al limite...

Grazie, ciao!

Walter ha detto...

Altri cinque punti a Davi