Nel 1956 Richard Bellman fece questa domanda, qui da me parafrasata: “Vi trovate in una foresta di cui sapete la forma e vi siete persi. Quanto è lungo il più breve percorso che nel caso peggiore vi porti fuori dalla foresta?” Per la cronaca, Bellman è stato uno dei guru della programmazione dinamica, quindi che abbia proposto un problema di ottimizzazione è normale. È anche chiaro che se fosse vissuto nella pianura padana e non in America il problema sarebbe stato ambientato col nebiun, che è molto meglio di una foresta per non sapere dove ci si trova: ma ormai il problema è noto come Bellman’s lost in a forest problem e ce lo teniamo così.

Il problema sembra semplice, ma non lo è affatto. Prendiamo per esempio un quadrato, per comodità [0,1]×[0,1]. Se sapessimo le coordinate dove ci troviamo e avessimo una bussola, potremmo uscire dalla foresta percorrendo un tratto di lunghezza al massimo 0,5 parallelo a un lato, come a sinistra nella figura. Se non conoscessimo le nostre coordinate ma avessimo la bussola, potremmo uscire percorrendo un tratto di lunghezza al massimo 1, come a metà in figura; magari andremmo nella direzione opposta a quella più vicina ma comunque usciremo. Se non sappiamo proprio nulla? Sicuramente la distanza minima nel caso peggiore è al massimo $\sqrt{2}$, come a destra in figura, ma magari c’è un modo più furbo… E invece no, si dimostra che per tutti i poligoni “grassi” (come spiegato qui) la soluzione ottimale è il diametro della figura. Questo vale tra l’altro per tutti i poligoni regolari dal quadrato in su (e per il cerchio, cosa che però si era già dimostrata in altro modo). E per il triangolo equilatero? Il testo che ho appena citato afferma che A. S. Besicovitch ha congetturato e Patrick Coulton e Yevgenya Movshovich hanno dimostrato che un certo percorso a zig zag in un triangolo equilatero di lato 1 ha lunghezza inferiore a 1: per la precisione, $3 \sqrt{21}/14 ≈ 0.981981$. Esistono altre figure per cui si è calcolata la “lunghezza di fuga” minima, ma il problema non è ancora completamente risolto.

Il tutto serve a qualcosa? Secondo il matematico Scott W. Williams, è “un problema milionario”, nel senso che le tecniche che presumibilmente porterebbero alla risoluzione potrebbero essere riciclate per ottimizzare le soluzioni di problemi nella vita reale…

Ultimo aggiornamento: 2024-09-04 15:48

bLa scorsa settimana abbiamo visto che è possibile costruire tre dadi non standard A, B, C tali che in media il dado C sia “migliore” di A, nel senso che lanciandoli è più facile che abbia il valore più alto; B sia “migliore” di A; C sia “migliore” di B. Ma si può fare di meglio, come Donald Knuth ha scritto nel Volume 4, Fascicolo 5 di The Art of Computer Programming.
Una premessa. Lake Wobegon è il paesino fittizio narrato da Garrison Keillor per radio e nei suoi libri: uno dei tormentoni radiofonici fa “Queste le notizie da Lake Wobegon, dove tutte le donne sono forti, tutti gli uomini sono belli, e tutti i bambini sono al di sopra della media.” Chiaramente le due prime affermazioni prendono in giro i romanzetti dove tutti gli uomini sono forti e le donne belle, e la terza prende in giro la matematica perché non è possibile che tutti stiano sopra la media… o no?
Considerate i tre dadi (sempre non standard) nella figura a fianco. Il primo ha un 5 e cinque 3, e gli altri due due 1 e quattro 4. Ora lanciamoli tutti insieme, e vediamo quando uno dei dadi ha un punteggio maggiore della media dei tre dadi (compreso sé stesso, quindi). Indico con (l,m,n} il risultato rispettivamente dei dadi D, E, F.

Per il dado D, il suo punteggio è maggiore della media nei casi (3,1,1), (3,1,4), (3,4,1), (5,*,*) (l’asterisco indica che qualunque valore va bene). Le probabilità rispettive sono 5/54, 10/54, 10/54 e 1/6; la loro somma è 17/27 che è maggiore di 1/2.

Per il dado E (ma lo stesso vale per il dado F), il suo punteggio è maggiore della media nei casi (3,4,*) e (5,4,1); le rispettive probabilità sono 5/9 e 1/27, che sommate danno 16/27 che è ancora maggiore di 1/2. In pratica, ogni dado se lanciato da solo ha un punteggio che statisticamente è maggiore della media della somma degli altri due!

John D. Cook spiega che l’apparente paradosso per cui A > (A+B+C)/3, B > (A+B+C)/3, C > (A+B+C)/3 si risolve notando che i tre eventi non sono disgiunti, e quindi quando uno è vero può anche esserne vero un altro.