Categoria: Giochi matematici

Se il candidato attuale è peggiore di uno già rifiutato, può ancora essere il migliore di tutti?

Una scelta con possibilità di successo deve essere un nuovo record: il migliore visto finora. L’ultima scelta obbligata può essere perdente, ma non cambia questo criterio per vincere.

Prova a scartare i primi r candidati e poi scegliere il primo record successivo. Quando funziona?

Supponi che il migliore assoluto sia in posizione k, dopo la fase di osservazione. La strategia lo raggiunge soltanto se il migliore dei primi k − 1 si trovava fra i primi r.

Una soglia fra osservare e scegliere

La strategia ottimale per 100 candidati è: rifiutare i primi 37, ricordare il migliore di quel gruppo, poi accettare il primo che supera tutti quelli già incontrati. Se non arriva, si sceglie l’ultimo. La probabilità di successo è circa 37,1043%. Non è una garanzia di trovare il migliore in ogni sequenza.

Calcolare la probabilità

Con n candidati, chiamiamo r il numero iniziale di rifiuti, con 1 ≤ r ≤ n − 1. Il migliore assoluto occupa ciascuna posizione k con probabilità 1/n. Se k > r, lo scegliamo se e solo se il massimo dei primi k − 1 è nella fase iniziale: questo accade con probabilità r/(k − 1).

P_n(r) = (r/n) [1/r + 1/(r + 1) + … + 1/(n − 1)].

I casi k ≤ r sono già perduti. Se r = 0 scegliamo subito il primo e vinciamo con probabilità 1/n. La scelta obbligata dell’ultimo non aggiunge successi non contati: quando l’ultimo è il migliore è anche un record.

Perché una soglia è davvero ottimale

Un candidato che non è un record ha probabilità zero di essere il migliore. Un record in posizione k ha probabilità k/n di esserlo. L’ordine casuale rende i ranghi relativi successivi indipendenti da quelli osservati: il valore ottimale dell’attesa dipende dal momento, non dalla particolare storia dei confronti.

Il premio per fermarsi su un record cresce con k; il valore della continuazione non cresce quando diminuiscono le occasioni rimaste, perché prima possiamo sempre rifiutare un’occasione in più. Perciò, una volta conveniente accettare un record, rimane conveniente farlo in seguito. Questo giustifica la forma a soglia, non soltanto il confronto fra alcune strategie intuitive.

Per trovare il valore intero ottimale confrontiamo soglie consecutive. Per r ≥ 1, la differenza P_n(r + 1) − P_n(r) è [Σ_j=r+1ⁿ⁻¹ 1/j − 1]/n. Si aumenta r finché la somma supera 1; eventuali uguaglianze producono due soglie equivalenti. Per n = 100 il massimo è r = 37.

Da dove arriva il 37%

Se r/n tende a x, la somma armonica è approssimata da log(n/r), quindi P_n(r) tende a −x log x. La derivata è −log x − 1: si annulla in x = 1/e. In quel punto anche la probabilità limite vale 1/e, circa 36,7879%.

Il rapporto 1/e è un risultato asintotico. Per un n finito si usa la somma esatta e una soglia intera. Per esempio, con 10 candidati conviene scartarne 3 e la probabilità è circa 39,869%; con 100 si scartano 37 e la probabilità è circa 37,1043%.

È un problema di arresto ottimale: a ogni passo si confronta il valore di una decisione immediata con quello atteso continuando. Si ragiona all’indietro dall’ultima occasione, quando non c’è più nulla da attendere.

Le informazioni disponibili sono parte del problema. Con punteggi assoluti e una distribuzione nota potremmo usare soglie di qualità; con ordine non casuale la probabilità calcolata qui non sarebbe valida. Se vogliamo massimizzare la qualità media invece della probabilità di ottenere il massimo, cambia anche l’obiettivo.

La regola bilancia due rischi: scartare il migliore nella fase di osservazione oppure fermarsi troppo presto su un record modesto. Aumentare r riduce il secondo rischio e aumenta il primo. Il massimo della formula individua il compromesso per queste precise ipotesi.

Un riferimento rigoroso è il capitolo sui problemi a orizzonte finito di Thomas S. Ferguson, che presenta anche varianti del modello.

E se i candidati fossero soltanto tre? Scarta il primo e scegli il secondo se lo supera; altrimenti scegli il terzo. Associa i valori 1, 2, 3 alle qualità, con 3 migliore.

Fra i sei ordini equiprobabili, vinci con (1,3,2), (2,1,3) e (2,3,1). Perdi con gli altri tre. La probabilità è 1/2, uguale a P₃(1) = (1/3)(1 + 1/2). Scegliere subito il primo darebbe soltanto 1/3.

Se invece potessi richiamare chiunque dopo aver incontrato tutti, sceglieresti sempre il migliore e vinceresti con probabilità 1. È il vincolo di irrevocabilità, insieme all’informazione parziale, a rendere interessante il gioco.

Il problema compare anche come gioco di scelta del numero più grande, ed è stato studiato in numerose varianti. Il nome storico non deve far dimenticare la struttura astratta: una sequenza casuale, confronti relativi e una sola decisione irrevocabile.

Il celebre 37% viene spesso presentato come consiglio per qualunque scelta quotidiana. Il teorema è più preciso: richiede un numero noto di opportunità, ordine casuale e l’obiettivo di ottenere proprio il massimo. Se una di queste condizioni manca, applicare la percentuale automaticamente non è una conclusione matematica.

La partita non può durare per sempre e non può finire in pareggio. Che cosa ne segue per l’esistenza di una strategia vincente per uno dei due giocatori?

Ogni mossa elimina almeno un pezzo. Puoi ragionare a ritroso partendo dalla posizione con il solo pezzo avvelenato.

Immagina che il primo giocatore tolga soltanto il pezzo nell’angolo in alto a sinistra. Se questa mossa fosse perdente, quale risposta vincente avrebbe il secondo?

Qualunque altra mossa non avvelenata, eseguita direttamente sulla tavoletta intera, avrebbe eliminato anche quell’angolo. Confronta le posizioni risultanti.

Una strategia esiste

Il gioco è finito, senza mosse casuali e senza pareggi. Per induzione sul numero di pezzi, ogni posizione è vincente o perdente per chi deve muovere: è vincente se esiste una mossa sicura verso una posizione perdente; è perdente se tutte le mosse sicure conducono a posizioni vincenti. Il solo pezzo avvelenato è una posizione perdente.

Il furto di strategia

Supponiamo per assurdo che il rettangolo iniziale sia perdente per il primo giocatore. Questi toglie soltanto il pezzo in alto a sinistra, che non è avvelenato perché la tavoletta ha almeno due pezzi.

La posizione ottenuta deve essere vincente per il secondo giocatore. Esiste dunque una sua risposta sicura, in un pezzo Q, che lascia una posizione perdente a chi deve muovere.

Ma il primo avrebbe potuto scegliere Q subito, sulla tavoletta intera. Il morso in Q avrebbe eliminato anche il pezzo in alto a sinistra: la posizione rimasta sarebbe stata esattamente la stessa. Avrebbe quindi lasciato al secondo una posizione perdente, contraddicendo l’ipotesi iniziale.

Su ogni rettangolo con almeno due pezzi il primo giocatore ha una strategia vincente.

La dimostrazione non afferma che togliere l’angolo in alto a sinistra sia sempre una mossa vincente. Dice che o quella mossa vince, oppure una risposta che la confuta può essere usata direttamente come prima mossa. Senza identificare la risposta non abbiamo ancora una ricetta operativa generale.

Una strategia concreta per il quadrato

Su un quadrato n × n, con n almeno 2, il primo sceglie il pezzo immediatamente in alto a sinistra del veleno. Elimina così il quadrato (n − 1) × (n − 1) e lascia soltanto la riga inferiore e la colonna destra: una L con due bracci uguali e il veleno nel vertice comune.

Ogni mossa sicura dell’avversario accorcia uno dei due bracci. Il primo accorcia l’altro fino alla stessa lunghezza, scegliendo il pezzo riflesso rispetto alla diagonale che passa per il veleno. La risposta è sempre disponibile e sicura: i bracci hanno in comune soltanto il pezzo avvelenato.

Dopo ogni coppia di mosse torna una L simmetrica più piccola. Alla fine il secondo riceve il solo pezzo avvelenato e perde. Qui abbiamo sia una prima mossa precisa sia una regola per tutte le risposte.

Chomp è un gioco combinatorio a informazione perfetta: non ci sono carte nascoste o lanci di dadi. Per sapere se una posizione è vincente, si può esplorare l’albero delle mosse e memorizzare le posizioni già incontrate.

Questo algoritmo, per una tavoletta finita, dà anche mosse concrete. Il suo costo può però crescere molto con la dimensione. Il furto di strategia dimostra l’esistenza senza esplorare l’intero albero: offre una conclusione generale, non automaticamente un calcolo efficiente.

Le ipotesi sono decisive. La posizione iniziale deve essere un rettangolo completo, affinché ogni morso contenga l’angolo opposto al veleno. Una forma già rosicchiata può essere perdente: la L simmetrica ne è un esempio. Il rettangolo 1 × 1 è escluso perché il primo perde subito.

Per confrontare regole e argomento, si veda la presentazione della Cornell University. Le diverse orientazioni del pezzo avvelenato descrivono lo stesso gioco dopo una rotazione.

Che cosa succede con una sola riga di n pezzi, n almeno 2? Il veleno è sempre all’estremità destra.

Il primo sceglie il pezzo immediatamente a sinistra del veleno: tutti i pezzi sicuri vengono eliminati e al secondo resta soltanto quello avvelenato. Per una sola colonna si procede allo stesso modo dal basso. È una strategia costruttiva particolarmente semplice, coerente con il teorema generale.

Prova poi a partire da una L con bracci diversi: puoi accorciare il più lungo per consegnare all’avversario una L simmetrica? Sì: scegli il pezzo che lascia esattamente lo stesso numero di pezzi sicuri nei due bracci, quindi applica la strategia di risposta speculare.

Il gioco è comunemente associato a David Gale; una formulazione precedente di Fred Schuh usava la divisibilità fra interi. Joseph Malkevitch ricostruisce questi collegamenti nella sua scheda di York College, CUNY, con i riferimenti ai lavori di Schuh del 1952 e Gale del 1974.

Il furto di strategia compare anche in altri giochi, ma ogni applicazione richiede una giustificazione specifica. In Chomp il punto cruciale è l’uguaglianza fra la posizione ottenuta con due morsi e quella ottenuta scegliendo subito il secondo: “giocare per primi è meglio” da solo non è una dimostrazione.

Non è necessario che tutti conoscano il numero di visitatori. Basta che una sola persona possa raccogliere le informazioni.

Assegna a un prigioniero un ruolo diverso. Gli altri devono poter inviare un segnale che resti disponibile finché non viene letto.

Un segnale ancora acceso non può essere sovrascritto da un secondo segnale distinguibile.

Chi vuole segnalare deve aspettare di trovare la lampadina spenta. Dopo aver segnalato una volta, deve ricordarsene per sempre e non ripetere il messaggio.

Prima dell’isolamento designano un contatore. Gli altri 99 sono segnalatori. Il contatore parte da zero; ogni segnalatore ricorda se ha già inviato il proprio segnale.

• Un segnalatore che non ha ancora segnalato accende la lampadina soltanto se la trova spenta. Da quel momento considera il suo segnale inviato.
• Se la lampadina è già accesa, il segnalatore la lascia accesa: non ha ancora inviato nulla e riproverà in una visita futura.
• Dopo aver inviato il proprio segnale, un segnalatore non tocca più l’interruttore.
• Il contatore, quando trova la lampadina accesa, la spegne e aumenta di uno il proprio conteggio. Se la trova spenta, non cambia nulla.
• Quando il contatore raggiunge 99, dichiara che tutti hanno visitato la stanza.

Perché non può sbagliare? Ogni accensione proviene da uno dei 99 segnalatori, e ciascuno accende al massimo una volta. Solo il contatore spegne, quindi una stessa accensione non può essere contata due volte. La lampadina inizialmente spenta esclude segnali precedenti alla prima visita. Novantanove segnali contati corrispondono dunque a 99 persone distinte; il contatore è la centesima ed è presente nella stanza.

Perché prima o poi termina? Quando la lampadina è spenta e restano persone che non hanno segnalato, ogni turno ha probabilità positiva di selezionarne una. La probabilità di evitarle per sempre è zero. Dopo l’accensione, il contatore viene selezionato prima o poi con probabilità 1 e libera il canale spegnendo.

Ripetendo questo ragionamento per un numero finito di segnali, tutti vengono raccolti con probabilità 1. La strategia non dichiara mai il falso, qualunque sia la sequenza delle visite. Esistono però sequenze infinite che impediscono la conclusione: nel modello casuale hanno probabilità zero.

99 segnali distinti + il contatore presente = 100 visitatori certi.

La lampadina è una memoria condivisa di un bit. Le memorie personali contengono il resto: ogni segnalatore ricorda un sì o un no, mentre il contatore conserva un numero. Il protocollo funziona perché assegna significati univoci alle azioni e separa invio e ricezione.

Possiamo descrivere un invariante: il numero dei segnali già inviati è uguale al conteggio del contatore più 1 se la lampadina è accesa, oppure al solo conteggio se è spenta. Questa relazione rimane vera dopo ogni visita. È il motivo per cui i messaggi non vengono né inventati né persi.

La sicurezza della dichiarazione non dipende dalla casualità. Per la conclusione basta anche una sequenza deterministica equa, nella quale ciascuno venga chiamato infinite volte. Senza alcuna condizione di questo tipo, il carceriere potrebbe escludere per sempre una persona.

Nel modello indipendente e uniforme possiamo calcolare il tempo medio di questa strategia. Se restano k segnalatori da contare e la lampadina è spenta, l’attesa media per una nuova accensione è 100/k turni. Dopo l’accensione occorrono in media 100 turni per chiamare il contatore. Sommando per k da 99 a 1:

E[T] = 100 · (1 + 1/2 + … + 1/99) + 9900 ≈ 10417,74 turni

È la media di questo protocollo, non una prova che sia il più rapido possibile. Non esiste un limite deterministico al tempo d’attesa: per ogni durata finita rimane una probabilità positiva di non aver finito. Se ogni turno fosse un giorno, la media supererebbe 28 anni.

E se lo stato iniziale fosse sconosciuto? Le altre ipotesi restano identiche. La regola precedente potrebbe scambiare un’accensione iniziale per una visita: come correggerla?

Una soluzione è far inviare a ciascuno dei 99 segnalatori due segnali, sempre accendendo solo quando trova spento e senza spegnere mai. Ognuno tiene memoria di zero, uno o due invii. Il contatore spegne e conta come prima, ma aspetta di arrivare a 198.

Se anche un solo segnalatore non fosse mai entrato, gli altri 98 potrebbero generare al massimo 196 segnali. Aggiungendo l’eventuale accensione iniziale si arriverebbe al massimo a 197. Quindi 198 garantisce che tutti abbiano visitato. Non garantisce che tutti abbiano già inviato entrambi i segnali, ma questo non è l’obiettivo.

La conclusione arriva ancora con probabilità 1: se inizialmente era spento, sono disponibili 198 invii reali; se era acceso, c’è in più un possibile segnale iniziale. Lo stesso alternarsi fra accensione e lettura impedisce che il processo resti bloccato.

Questo rompicapo illustra due proprietà studiate anche nei sistemi distribuiti: la sicurezza, cioè evitare un risultato scorretto, e il progresso, cioè arrivare infine a un risultato. Una procedura può avere la prima senza la seconda. Qui il protocollo assicura la sicurezza, mentre la regola delle visite rende possibile dimostrarne il progresso.

Una versione del rompicapo e della soluzione compare nella raccolta di John Burkardt presso Florida State University. Le varianti cambiano le informazioni iniziali: prima di trasferire una soluzione, conviene controllare queste ipotesi.

Il gioco è diverso da I cento prigionieri e le cento scatole: là si sfruttano i cicli di una permutazione, qui si costruisce un canale di comunicazione persistente.

Se gli importi fissati sono S e 2S, quanto guadagni passando dalla busta piccola alla grande? Quanto perdi nel percorso opposto?

Esprimi entrambe le differenze usando lo stesso S, invece di una lettera il cui valore cambia da un caso all’altro.

Dopo aver osservato un importo, non tutte le preparazioni iniziali restano possibili.

Nel modello indicato, trovare 10 euro è compatibile con una busta più piccola ancora? E trovare 40 euro è compatibile con una busta più grande?

A buste chiuse non c’è vantaggio nel cambiare. Per ogni S fissato, cambiare produce +S se avevi scelto la busta piccola e −S se avevi scelto quella grande. I due eventi hanno uguale probabilità: il guadagno medio è zero. Entrambe le scelte hanno valore atteso 3S/2.

La formula ingannevole tratta A come una costante mentre usa probabilità che descrivono due situazioni nelle quali A assume valori diversi. Se S è fissato, A vale S nel primo caso e 2S nel secondo. La media corretta dell’altra busta è (2S + S)/2, non il 125% di un unico importo A.

Nel modello con S casuale equiprobabile fra 10 e 20, ci sono quattro esiti, ciascuno con probabilità 1/4. Indichiamo con B il contenuto dell’altra busta:

• S = 10: A = 10, B = 20.
• S = 10: A = 20, B = 10.
• S = 20: A = 20, B = 40.
• S = 20: A = 40, B = 20.

Prima di guardare, E[A] = E[B] = (10 + 20 + 20 + 40)/4 = 22,50 euro. Dopo aver aperto, invece:

• Vedi 10 euro: B è certamente 20. Conviene cambiare.
• Vedi 20 euro: B può essere 10 o 40, ora davvero con probabilità 1/2 ciascuna. Il valore atteso è 25 euro: conviene cambiare.
• Vedi 40 euro: B è certamente 20. Conviene tenere la busta.

Seguendo questa strategia ottieni rispettivamente 20, 10, 40, 40 nei quattro esiti. La media è 27,50 euro. Il miglioramento rispetto a 22,50 euro viene dall’informazione ottenuta aprendo la busta e dalla decisione che ne dipende. Cambiare sempre avrebbe lasciato invariata la media.

A buste chiuse: nessun vantaggio. Dopo l’apertura: decide il modello.

Se S è una variabile casuale positiva con E[S] finito, la scelta iniziale equa e indipendente dà E[A] = E[B] = 3E[S]/2. Il guadagno B − A è integrabile perché il suo valore assoluto è S; il suo valore atteso è zero.

Dopo aver osservato A = a, serve invece la probabilità condizionata p(a) che la busta scelta sia quella piccola. Quando l’evento osservato ha probabilità positiva, il valore atteso dell’altra busta è:

E[B | A = a] = 2a · p(a) + (a/2) · (1 − p(a))

Cambiare conviene, in valore atteso, esattamente quando p(a) > 1/3; si è indifferenti se p(a) = 1/3. Sapere che la scelta iniziale era equa non rende automaticamente p(a) uguale a 1/2 dopo l’osservazione. Occorre conoscere la distribuzione degli importi; per distribuzioni continue il condizionamento richiede il corrispondente modello con densità.

La finitezza della media è essenziale nei confronti globali. Se S è finito in ogni singola prova ma ha media infinita, entrambe le buste possono avere valore atteso infinito. Sottrarre quei valori non produce zero: infinito meno infinito non è definito. Esistono modelli di questo tipo con vantaggio condizionato per ogni importo osservabile; non dimostrano un guadagno medio finito ottenibile cambiando sempre.

L’organizzatore sceglie ancora S fra 10 e 20 euro, ma ora con probabilità rispettivamente 3/4 e 1/4. La scelta della busta resta equa e indipendente. Dopo aver visto 20 euro, conviene cambiare?

I due modi di osservare 20 hanno probabilità iniziali 3/8 e 1/8. Condizionando sull’osservazione, l’altra busta contiene 10 con probabilità 3/4 e 40 con probabilità 1/4. La sua media è 10 × 3/4 + 40 × 1/4 = 17,50 euro: conviene tenere i 20. Lo stesso importo osservato conduce a una decisione diversa perché è cambiata la distribuzione iniziale.

Il paradosso delle due buste viene usato per discutere il condizionamento e il significato del valore atteso. Una presentazione è disponibile fra i Math Fun Facts di Harvey Mudd College; per una discussione delle formulazioni si può leggere The Two Envelope Paradox di Eric Schwitzgebel e Josh Dever.

Il punto non è imparare una regola del tipo “cambia” o “non cambiare”. È abituarsi a domandare: quale esperimento produce gli importi, che cosa ho osservato e rispetto a quale informazione sto calcolando la media?