La soluzione del problema 8 sarà forse sembrata un po’ debole ad alcuni lettori: in fin dei conti è teoricamente possibile che non si riesca mai a capire chi vinca, e si debba continuare a lanciare la moneta all’infinito. Non è proprio possibile fare di meglio, e trovare un modo per essere certi di terminare la procedura? Purtroppo no.

La dimostrazione non è molto difficile: basta accorgersi che tutto quello che possiamo fare è assegnare a uno dei giocatori un insieme preciso di successioni di testa e croce, e all’altro giocatore le successioni restanti. Se questi due insiemi fossero finiti, la probabilità totale sarebbe la somma delle probabilità delle singole successioni. Ma ciascuna successione di lunghezza N ha una probabilità di uscita che è rappresentata da una frazione con denominatore 7^N, dato che moltiplichiamo fattori 3/7 e 4/7. Ma la somma di frazioni con denominatore 7^k non può mai fare 1/2, visto che il denominatore della somma sarà comunque una potenza di 7. Fine dei giochi. (Una somma infinita ci permette di riuscirci, come spiegato nella risposta al problema).

Quello che si può fare è però minimizzare il numero di lanci necessario per trovare il vincitore. Io così ad occhio userei un algoritmo “greedy” come quello indicato qui sotto, ma non ho nessuna idea se è davvero ottimo. L’algoritmo sceglie a ogni passo la probabilità maggiore che non faccia sballare le percentuali, cioè superare 1/2, e la assegna al giocatore in svantaggio. Supponiamo per non avere subito numeri troppo grandi che la moneta lanciata mostri testa una volta su tre e croce due volte su tre: la sequenza funzionerà allora così…

• Primo lancio T: vince A (1/3). Probabilità totale di vincita: A=1/3, B=0, resto 2/3
• Primo lancio C, secondo lancio C: vince B (4/9). Probabilità totali: A=3/9, B=4/9, resto 2/9
• Primi lanci CT, terzo lancio C: vince A (4/27). Probabilità totali: A=13/27, B= 12/27, resto 2/27
• Primi lanci CTC, quarto lancio C: vince B (4/81). Probabilità totali: A=39/81, B=40/81, resto 2/81

Semplice, no? No che non è semplice se dobbiamo fare i conti noi e non un computer. ed è per questo che la procedura indicata nel libro, anche se non ottimale, è più comoda!