un problema con infinite stanze... che non ricordo più

[andrea_sax]

Ciao a tutti,

ringrazio già chi mi vorrà aiutare, e mi scuso nel caso non avessi postato nella sezione giusta.

Oggi sto impazzendo perché mi è tornato in mente un problema che avevo letto diversi anni fa, ma non riesco a ricordarne i dettagli Ho sfogliato l'archivio delle gare di cesenatico, delle imo e delle BMO, ma non sono riuscito a trovarlo da nessuna parte.

Ecco quello che ricordo: un piano di un edificio è costituito da un numero finito di stanze, collegate da porte, ma nessuna di queste consente di entrare o uscire dall'edificio (dunque il tutto è "chiuso"). Inoltre, presa una coppia qualunque di stanze, è possibile trovare un percorso che conduca dall'una all'altra. Una persona si trova all'interno ed attraversa una di queste porte, quindi puo' decidere se imboccare la prima porta alla sua sinistra o la prima porta alla sua destra, e si troverà di fronte a questa scelta ad ogni porta che attraverserà. Trovare una successione di scelte dx/sx che consenta a questa persona di passare almeno una volta da ogni stanza (o forse, ma è lo stesso, che le consenta di arrivare ad una determinata stanza).

ATTENZIONE: mi ripeto, non vorrei che qualcuno perdesse tempo su un problema non corretto, non sono per nulla sicuro che questo sia il testo completo.

Per caso qualcuno di voi l'ha già visto e si ricorda dove, oppure ricorda il testo esatto?

[karlosson_sul_tetto]

A prima lettura mi ricorda moltissimo questo, però ci sono delle cose che sono diverse:
La succession sx/dx dev'essere la stessa per ogni possibile disposizione di stanze? Posso riconoscere una stanza in cui ci sono già stato? Posso farmi una "mappa" di tutte le stanze che visito? Ogni stanza è collegata a solo tre altre =(la porta da cui sei venuto, quella a destra e quella a sinistra) o ce ne possono essere anche altre?

[andrea_sax]

Effettivamente è molto molto simile! da quel che ricordo, la successione sx/dx non deve dipendere dalle stanze, credo che non fosse possibile riconoscere le stanze già visitate, per la mappa... per come l'avevo capito, bisognava dare una successione a priori, cioè valida per qualunque configurazione possibile, quindi non credo che sia possibile modificarla o scriverla "in corso d'opera", e dunque direi che la mappa non è concessa. Riguardo il numero di porte, non ricordo alcuna restrizione, direi che può essercene una come 100, e magari anche diverse verso la stessa stanza.

[karlosson_sul_tetto]

Dopo averci pensato, abbozzo un'idea che provvederò con una dimostrazione se la troverò.

Dato che le scelte sinistra/destra sono predeterminate prima, posso scrivere un numero decimale del tipo 0,00101101111010010... dove dopo la virgola 0 indica una svolta a sinistra e 1 una svolta a destra. Osservazione banale: il numero dev'essere necessariamente irrazionale (se non lo fosse sarebbe periodico quindi sarebbe possibile trovare una disposizione di stanze in cui fai un loop).
La sequenza che PENSO vada bene è 10100101000101001010000101001010001010010100000101001010001010010100001010010100010100101000000 ecc
(costruito cosi: parto dal gruppo 101, ci aggiungo una seguenza di due zeri e ripeto il gruppo; poi prendo il secondo gruppo ottenuto 10100101, ci aggiungo 3 zeri e riaggiungo il gruppo e cosi via).

Continuerò a pensare a come finire il problema, però non posso assicurare niente

[karlosson_sul_tetto]

Ok, penso di averlo risolto.
Fatte le considerazioni e le notazioni del post sopra, mi accorgo che il numero dei piani possibili (=grafi in cui mi posso trovare) ha cardinalità di $ \mathbb{N} $, cosi come il numero di posizioni iniziali possibili per ogni grafo (ovvero la stanza da cui parto e la porta che attraverso per prima). Un'altra cosa che noto è che conoscendo la disposizione delle stanze, è sicuramente possibile trovare un percorso destra-sinistra che passi per tutte le stanze. Non dimostrerò formalmente queste osservazioni perché sono mezzo morto ma se sono poco chiare ditelo pure.
Ora, posso scrivere in ordine tutte le possibili posizioni iniziali per tutti i grafi in cui mi potrei trovare. Comincio a leggere queste posizioni: dopo aver letto la prima, scrivo nel mio numero decimale di 0 e 1 la sequenza necessaria per percorrere tutto il grafo a partire da quella posizione. Passo alla seconda posizione, dalla quale faccio le mosse scritte precedentemente; arrivo ad un certo punto, dal quale so che esiste un percorso che passa ler tutte le stanze: lo scrivo. Poi passo alla terza, quarta, quinta ecc posizione, faccio le mosse che ho scritto precedentemente e aggiungo le mosse necessarie per fare il giro di stanze; continuo cosi facendo una lista infinita, la quale soddisfa le condizioni del problema.