Un algoritmo per girare il mondo
Inviato: 14 lug 2011, 12:05
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).
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).