Un algoritmo per girare il mondo

[Anér]

C'era una volta il buon Julian che si trovava in una strada imprecisata di una città imprecisata di una nazione imprecisata del mondo. Julian doveva tornare a Castelfidardo ma non aveva la più pallida idea di dove fosse né tantomeno sapeva come tornare a casa. Tuttavia Julian sapeva che nel momento esatto in cui fosse arrivato a Castelfidardo se ne sarebbe accorto. Allora accese il computer e sull'oliforum vide questo problema e si mise a leggere: "C'era una volta il buon Julian che si trovava...". Julian esclamò "Caspita, si tratta proprio del problema che fa per me!". Infatti il problema, che poi è questo problema, chiedeva di dimostrare che c'è un algoritmo che consente di visitare ogni grafo planare connesso finito, come è quello delle strade del mondo, senza sapere nulla sul grafo. In pratica Julian poteva percorrere le vie del mondo (gli archi del grafo) con questa regola: percorreva una via fino ad arrivare a un corcevia (un vertice del grafo); a questo punto contava quante strade partivano da quel crocevia, diciamo b strade, e in base al numero b e al numero di strade percorse fino a quel momento sceglieva la nuova strada da prendere, ovvero la prima, la seconda, ..., la (b-1)-esima a destra o la strada stessa da cui era venuto (ossia la b-esima). Scelta una strada la percorreva fino al crocevia successivo, aggiungendo 1 al numero di strade percorse. Julian risolse il problema, spense il computer, e fischiettando una canzone dei Korpiklaani si mise in marcia, e dopo molto tempo giunse a casa e visse felice e contento.
Sapreste trovare una legge perché Julian possa scegliere una strada ad ogni crocevia in modo da arrivare prima o poi a Castelfidardo? Per maggiore chiarezza vi aggiungo un po' di punti:
1)Julian si addormenta appena comincia a percorrere una strada e si sveglia non appena arriva al crocevia successivo; durante il sonno dimentica tutto, fuorché il numero di passi fatti fino a quel momento, a cui aggiunge subito 1 prima di preoccuparsi di scegliere la strada successiva. Julian ricorda altresì come funziona l'algoritmo, ma non ricorda come lo ha utilizzato effettivamente nelle piazze precedenti.
2)Julian parte da una piazza e fa la prima scelta considerando di aver fatto 0 passi; aggiunge un passo appena arriva a un nuovo corcevia, facendosi un segno sul braccio con un pennarello blu (in un'altra versione del problema si fa un graffio sul braccio).
3) Julian non sa come è fatto il mondo, né quanti crocevia contiene, né qual è il massimo grado di un crocevia (numero di strade che partono da esso), nè come sono fatti i paraggi del punto in cui si trova. Sa soltanto che il mondo è costante (non ci sono cambiamenti delle strade durante il suo cammino), ed è un grafo planare finito connesso.
4) Ogni volta che Julian arriva ad un crocevia le strade sono ordinate intorno a lui univocamente: la prima a destra, la seconda a destra, e così via. Tuttavia se Julian arriva allo stesso crocevia da due strade diverse chiaramente cambierà il significato di "la prima a destra" ecc.
5) Julian ha bisogno di una funzione $f\colon \mathbb{N}\times \mathbb{N}_0\rightarrow \mathbb{N}_0$ tale che $\forall (a,b)\in \mathbb{N}\times \mathbb{N}_0$ si abbia $1\leq f(a,b)\leq b$. Se Julian arriva a un crocevia da cui partono b strade e sa di aver fatto a passi, prenderà la f(a,b)-esima strada a destra (eventualmente tornerà indietro). Julian ricorda da quale strada del crocevia è appena arrivato.
6) Julian non può lanciare monete o dadi o cose simili: non gli è consentito affidarsi alla probabilità.
7) La f deve essere definibile in maniera finita, ovvero non dovete dimostrare che esiste f tale che... magari dimostrando che le f cattive sono numerabili e tutte le f sono tante quante i reali (cosa peraltro falsa).

[ghilu]

Alcuni hint per un problema carino.
Hint1. Non farsi spaventare dalle ipotesi apparentemente restrittive: volere è potere.
Hint2.

Testo nascosto:

Un po' di buonsenso: tu cosa faresti al posto di Julian, sperduto in un territorio sconosciuto, impopolato e dove non prende il cellulare?

Hint3.

Testo nascosto:

Mica ti metterai a vagare a caso? In realtà ci ho provato a fare un algoritmo abbastanza casuale da far visitare per forza tutto quanto. Sarebbe stata la soluzione più spettacolare, anche se quella meno "semplice".

Hint4.

Testo nascosto:

Io prenderei come punto di riferimento la partenza e mi metterei a visitare tutti i possibili percorsi da lì, come quando giochi a nascondino, conti tu e non vuoi perdere di vista il luogo della conta, ma al contempo vuoi trovare i tuoi amici. E dai,a questo punto è fatta..

[Anér]

La strada presa da Ghilu (che poi è simile a quella che mi ha detto abc al telefono) funziona piuttosto bene. Facciamo allora un cambiamento alle ipotesi del problema: supponiamo che ogni crocevia abbia le strade con dei cartelli che le numerano in senso orario (ovviamente non è detto che ai capi di una strada ci sia lo stesso numero); stavolta però Julian quando arriva ad un crocevia va al centro e fa qualche giravolta fino a dimenticare anche da che strada proveniva (ma ricordando quante strade aveva fatto). Metto qui un commento che spiega la differenza (profonda?) tra questo problema e quello precedente, ma che parla del problema precedente.

Testo nascosto:

Se ho capito bene ghilu vorrebbe scegliere un punto di partenza e poi fare tutti i percorsi possibili e immaginabili a partire da quel punto, tornarndo indietro ogni volta che un percorso non funziona. Stavolta però non si può tornare indietro.

Se poi volete cimentarvi nella terza variante, risolvete il problema originale nel caso in cui Julian sappia anche che il grafo è un albero, stavolta però cercate un algoritmo che sia anche efficiente (ovvero che minimizzi i giri inutili).

[Anér]

Propongo altre varianti:
1) Julian gira su un grafo infinito connesso (ovvero ogni coppia di vertici è collegata da un percorso finito), in cui ogni vertice ha grado finito; le strade che partono da un vertice sono ordinate tra loro, Julian ricorda sempre da che strada viene ma non ci sono i cartelli che numerano univocamente le strade; questo è uguale al problema originale (anche nella soluzione) se non che il grafo diventa infinito.
2) Julian gira su un grafo infinito connesso e in ogni piazza ci sono i cartelli che numerano univocamnete le strade, ma Julian non ricorda da che strada veniva quando arriva in una piazza. Dimostrare che stavolta non esiste un algoritmo.
3) Torniamo ai grafi finiti e supponiamo che Julian giri in macchina, per cui deve rispettare i sensi unici di alcune strade. Dunque ad ogni piazza ricorda da che strada veniva, può vedere quante strade partono da quella piazza e per ognuna in quali sensi si può percorrere, come sono ordinate intorno alla piazza (ma non ci sono i cartelli che le numerano).
4) Stessa cosa del punto 3 ma stavolta in ogni piazza ci sono i cartelli che numerano univocamente le strade e ogni volta che Julian arriva in una piazza fa un testacoda che gli fa dimenticare da che strada veniva.