Ogni passeggiata è un’esperienza unica. I colori, le emozioni, il profumo dell’aria sono sensazioni da vivere soggettivamente e che rendono ogni passeggiata un’esperienza a sé. Ma passeggiare, nel senso più essenziale del termine, significa andare a zonzo, o meglio, attraversare una serie di luoghi, insomma: fare un itinerario.

Questi percorsi sono davvero cosi vari? Quando facciamo una passeggiata, potremmo essere i primi al mondo a farla?

Scopritelo nel nuovo shottino, e poi cliccate qui, per saperne di più.

Dicevamo? Ah sì, “passeggiata”. Una delle prime passeggiate ad essere analizzata scientificamente è stata la celebre passeggiata dei sette ponti di Königsberg, che non è una birra, sebbene il nome risuoni proprio di doppio malto. Questa città, che oggi si chiama Kaliningrad, è attraversata dal fiume Pregel e da suoi affluenti ed era suddivisa in 4 zone collegate tra di loro da 7 ponti.

Era stata lanciata una sfida che suonava così:

è possibile fare una passeggiata attraversando tutti i sette ponti di Königsberg ma una volta soltanto?

Per gli appassionati di quiz si potrebbe porre lo stesso problema in questo modo:

è possibile congiungere 4 punti come nello schema che vi ho postato in alto a destra, senza mai staccare la penna dal foglio?

E voi che ne dite: si può fare o no?

Ci sono due modi per rispondere.

Il primo è: provarle tutte (brute force rulez!). In questo fantastico post del blog di Mayec Rancel è descritto un piccolo algoritmo che simula queste prove. L’algoritmo proposto da Mayec ci dice che dovremmo fare 372 tentativi prima di esaurire tutte le possibilità ed arrenderci, riconoscendo che la sfida è irrisolvibile. Le passeggiate in questo caso non sarebbero poi così tante, ma questo metodo diventerebbe presto inservibile se volessimo ambientare lo stesso problema in una città moderna con più percorsi e più zone.

Il secondo approccio, che personalmente preferisco, consiste nel ricercare un metodo risolutivo generalizzato. Una volta trovato una metodologia, possiamo applicarla a qualsiasi problema analogo, senza dover provare ogni volta tutte le passeggiate possibili. Eulero, un matematico e fisico svizzero del ‘700, ha fatto proprio così! Ha osservato che ogni volta che si entra e si esce da un nodo servono sempre due ponti liberi. Per passeggiare come voleva la sfida, era necessario che in ogni zona confluisse un numero pari di ponti, mentre a Königsberg le aree erano sempre raggiunte da un numero dispari di ponti. Sfida impossibile! Citando beceramente Wikipedia:

Un qualsiasi grafo è percorribile se e solo se ha tutti i nodi di grado pari, o due di essi sono di grado dispari; per percorrere un grafo “possibile” con due nodi di grado dispari, è necessario partire da uno di essi, e si terminerà sull’altro nodo dispari.

Ricordate la mappa della città che vi avevo postato poco sopra? Guardate la mappa topologica di Königsberg (schema a destra), il grado di un nodo è pari al numero di archi incidenti su esso. Possiamo fare una passeggiata che usi gli archi una sola volta, solo se i nodi di grado dispari del grafo non sono più di due.

Eulero aveva appena dato inizio alla topologia ed alla teoria dei grafi. Sì, è proprio quella roba che c’è dentro ad ogni navigatore satellitare e in molto altro ancora (…anche nel blocco schermo di qualche smartphone). In realtà, chi si è documentato per bene sulla dimostrazione originale di Eulero (ammetto di non averne avuto il tempo), sostiene che avesse usato un approccio combinatorio più che topologico.

Ma torniamo al tema principale: come possiamo descrivere il percorso di una passeggiata?

Sicuramente dobbiamo pensare a “qualcosa” legato alle zone che sono nei nostri dintorni. Esiste un sito, walkscore.com, che misura la camminabilità di tutte le zone del mondo (in realtà, lo fa per finalità di valutazione immobiliare). Si inserisce un indirizzo e l’algoritmo calcola quanto è facile raggiungere a piedi: parchi, ristoranti, bar, gelaterie e punti utili nei dintorni. Ad ogni punto viene assegnato un punteggio che decrescente con l’aumentare della distanza, infine si calcola un indice di camminabilità complessivo che varia tra 0 e 100, secondo questa legenda:

90–100 Walker’s Paradise
Daily errands do not require a car
70–89 Very Walkable
Most errands can be accomplished on foot
50–69 Somewhat Walkable
Some errands can be accomplished on foot
25–49 Car-Dependent
Most errands require a car
0–24 Car-Dependent

Notare anche il punteggio di mobilità coi mezzi pubblici e l’indice di ciclabilità. Quanto è camminabile il vostro vicinato? Provate anche il vostro indirizzo e fatemi sapere…

I punti di interesse possono essere davvero tanti, sopratutto in un centro cittadino. In un centro città di media grandezza ne abbiamo contati 50. Dimentichiamoci della geometria del luogo e supponiamo che da ogni punto A possiamo proseguire al punto B, senza per forza transitare da un punto C lungo il nostro itinerario. In fin dei conti se vogliamo andare da A a B non è detto che dobbiamo per forza passare lungo il percorso stradale che ci farebbe passare da C (magari conosciamo già il punto C e vogliamo camminare invece lungo una via laterale che conosciamo meno). Detto questo, possiamo descrivere la nostra passeggiata con i punti che visiteremo, tenendo anche conto la possibilità che non vogliamo passeggiare per niente (il famoso insieme vuoto).

Però c’è da fare un piccolo distinguo: l’ordine delle zone che visitiamo lungo il nostro itinerario ci interessa veramente? Cambia qualcosa andare prima in gelateria e dopo al cinema o mi basta sapere che andrò al cinema ed in gelateria ma non so bene in che ordine? Beh, dipende dalla percezione di ognuno di noi.

Se per voi l’ordine nell’andare a zonzo è un elemento discriminante, avete a disposizione un numero di passeggiate enorme. Per ognuno dei sottoinsiemi delle 50 località dovete calcolare il numero di sequenze ordinate degli elementi costituenti, insomma:

Viene fuori un numero spropositato che vale circa:

Se invece vi basta sapere dove andrete, ma l’ordine con cui passeggiate tra le località non vi cambia la vita, allora potete scegliere tra:

passeggiate, ovvero un milione di miliardi (1.125.899.906.842.624).

Possiamo quindi sperare di essere i primi passeggiatori a fare la passeggiata che ci stiamo accingendo a fare? Pensiamo allo spazio di passeggiate in cui l’ordine non conta (quello più piccolo dei due che abbiamo appena visto) e supponiamo che, ogni giorno, in questa città da 50 punti di interesse vengano fatte 100.000 passeggiate, che nessuno aveva mai fatto prima; ci vorrebbero:

anni per farle tutte. Circa 31 milioni di anni.

La prossima volta che farete una camminata, mettete per un attimo da parte le guide turistiche e passeggiate usando la vostra fantasia, sperimentando percorsi incredibili e creativi. Le alternative sono così tante che probabilmente sarete le prime persone al mondo a passeggiare in quel modo!

Perlomeno per qualche milioncino di anni.

Ack.

Il solito “grazie” a .mau. per avermi supportato nella realizzazione di questo shottino…scusate se vi ho portati un po’ in giro prima di rispondere al quesito iniziale, ma Science4Fun è così: una passeggiata a zonzo nel mondo della scienza applicata al quotidiano. Con qualche bollicina di seltz. Buon giro! : )

A.