Don't take life too seriously: it's just a temporary situation

Appuntamento (problema dello)

Probabilità e statistica  Problemi 

Il problema dell’appuntamento fu introdotto da Steve Alpern nel 1976 e da questi formalizzato nel caso continuo nel 1995. Può essere espresso in questi termini: due persone si danno appuntamento in un parco, che non conoscono. Arrivate sul luogo, scoprono che il parco è enorme; ciascuno ha due possibilità: stare fermo, aspettando che l’altro lo trovi, oppure vagare, nella speranza di incontrare l’altro. Qual è la strategia ottimale?

In questi termini il problema è enormemente complesso: bisogna specificare la forma del parco e la distanza entro la quale i due potrebbero vedersi. Non sorprende quindi che i matematici abbiano preferito cimentarsi con le varianti monodimensionale, nella quale i movimenti sono lungo una linea, e discreta, nella quale i possibili luoghi d’incontro sono un numero finito noto n.

 

La variante continua sulla quale sono stati fatti più progressi è quella monodimensionale: i due di trovano lungo una linea (per esempio, una strada) a distanza di 2 unità, possono percorrere un’unità di distanza in un’unità di tempo e non sanno in che direzione si trovi l’altro; s’incontrano se si trovano contemporaneamente nello stesso punto.

Si dimostra facilmente che qualsiasi strategia deterministica, con una sequenza prefissata di passi, porta a una probabilità 1 / 2 che l’incontro non avvenga mai, quindi la strategia deve includere elementi casuali.

Nel 1995 Alpern propose di scegliere una direzione a caso, per poi muoversi una volta in quella direzione e le due seguenti in direzione opposta, sempre di un’unità di lunghezza alla volta; se l’incontro non avviene entro i tre spostamenti, si ripete la procedura. Questa strategia porta i due a incontrarsi in media dopo 5 spostamenti.

Indicando con A un movimento in avanti nella direzione prescelta e I uno in quella opposta, la strategia di Alpern si può codificare come AII, sottintendendo la scelta casuale della direzione e la possibile ripetizione.

Nello stesso anno Edward J. Anderson e Skander Essegaier proposero di scegliere casualmente tra le sequenze: AAIIII, AIIAII, AIAIII, AIIIAA, dimostrando che il numero medio di passi scende a circa 4.56676.

Nel 1999 Vic Baston propose le sequenze: AIIAAII, AIIIAAA, AIAIIIA e AAIIIII, riducendo il numero medio di passi a circa 4.4182.

Patchrawat Uthaisombut mostrò che, utilizzando 5 sequenze di 7 passi, scelte con una probabilità che dipende dal numero di tentativi effettuati e dalla sequenza impiegata precedentemente, il numero medio di passi scende a circa 4.39306 e che con nessuna strategia numero medio di passi può scendere sotto 3.95460.

Non è detto che quella di Uthaisombut sia la strategia ottimale: è possibile che strategie con altre sequenze permettano di migliorarla.

 

Per quanto riguarda la versione discreta, ci sono alcune varianti, ma almeno in quelle più studiate si suppone che le due persone coinvolte:

  • non si trovino all’inizio nello stesso punto;

  • possano incontrarsi solo in uno degli n punti, non lungo il percorso;

  • non possano comunicare;

  • adottino la stessa strategia;

  • dispongano di un generatore casuale (come per esempio un dado) per poter effettuare più scelte casuali;

  • eseguano ogni unità di tempo (un’ora o un giorno, non ha molta importanza, purché le unità siano uguali per i due personaggi) scelte simultanee, consistenti nello stare fermi o recarsi in un altro punto.

 

Solo nel 1990 Richard Weber e Eddie Anderson proposero una soluzione, che si rivelò corretta per n = 2, ma una semplice congettura per n > 2, perché la dimostrazione conteneva un errore irreparabile.

Se n = 2 la strategia migliore è per entrambi tirare una moneta e stare fermi o recarsi nell’altro punto con probabilità 1 / 2; l’incontro avviene in media dopo 2 unità di tempo.

Per n > 2 la strategia indicata da Weber e Anderson consiste nello scegliere di stare fermi per n – 1 unità di tempo con una probabilità p (che dipende da n) e recarsi in tutti gli altri punti, in ordine casuale, con probabilità 1 – p, impiegando n – 1 unità di tempo; se non ci si trova entro n – 1 unità, si ripete la scelta casuale con la stessa strategia.

Per n = 3 p = 1 / 3 e l’incontro avviene in media in 5 / 2 unità di tempo; per n = 4 p = (3 * sqrt(681) – 77) / 4 e l’incontro avviene in media in p = (15 + sqrt(681)) / 12 unità. Al crescere di n, p tende a circa 0.24748942 e l’incontro avviene in media in 0.82888497n unità circa.

 

Nel 2009 Junjie Fan dimostrò che la strategia di Weber e Anderson è ottimale per n = 4 tra tutte quelle che consistono nel ripetere le stesse mosse (casuali) dopo una sequenza di 3 unità di tempo. Lo stesso Fan dimostrò anche che se esiste un ordine dei punti noto a entrambi, per n = 4 esiste una strategia, sempre da ripetersi ogni 3 unità, leggermente migliore di quella di Weber e Anderson.

 

Nel 2012 Richard Weber dimostrò che per il caso di 3 punti la soluzione di Weber e Anderson è in effetti ottimale. Questa variante del problema è nota come “problema del caffé Mozart”, perché Alpern nel 2010 la presentò in questi termini: due persone si danno appuntamento al caffé Mozart a Vienna, ma, arrivate in città, scoprono che vi sono tre caffé con lo stesso nome; qual è la strategia migliore che devono seguire, senza poter comunicare fra loro, per incontrarsi nel minor tempo possibile? La risposta è la strategia di Weber e Anderson.

Alpern e S. Gal avevano dimostrato nel 2006 che per n = 3 se la soluzione di Weber e Anderson è ottimale, l’esistenza di un ordine dei punti nota a entrambi non permette di migliorarla, quindi dalla dimostrazioni di Weber segue che un ordine noto dei punti è inutile per n < 4, mentre quella di Fan lascia intuire che potrebbe essere utile per tutti i valori superiori.

 

La congettura che la strategia di Weber e Anderson sia ottimale per tutti i valori di n ricevette un duro colpo nel 2009, quando Weber dimostrò che nel caso n = 4 con una differente scelta dell’ordine dei punti da visitare, l’incontro avviene in media dopo circa 0.000147 unità in meno rispetto alla scelta casuale. Invece di scegliere l’ordine dei punti da visitare a caso, quando si decide di spostarsi, la strategia prevede quattro sequenze di tre visite agli altri posti in ordini differenti, ripetendo quindi un ciclo di 12 visite.

 

Nel 1990 V.P. Crawford e H. Haller proposero una variante, nella quale in ogni istante i due sanno dove si trovi l’altro, ma non cosa abbia intenzione di fare. In questo caso la strategia ottimale è la seguente:

  • per n = 2, applicare la strategia di Weber e Anderson descritta sopra, l’incontro avviene in media dopo 2 unità di tempo;

  • per n = 3 recarsi nel terzo punto; l’incontro avviene dopo 1 unità di tempo;

  • per n > 3, ignorare tutti gli altri punti d’incontro e applicare la strategia di Weber e Anderson per il caso n = 2 ai due punti nei quali si trovano; l’incontro avviene in media dopo 2 unità di tempo.

 

Nella pratica naturalmente sono possibili altre strategie; per esempio, nel 2007 un lettore propose sul quotidiano Guardian il problema in questi termini: ho perso mia moglie in un affollato festival musicale; qual è la miglior strategia per ritrovarla? Un lettore rispose: “inizia a conversare con una bella donna: la moglie riapparirà immediatamente!”

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.