Spegnere le luci

[0-§]

Era da un bel po' che non tornavo in questi lidi: grazie al periodo di riposo post-laurea, a breve posterò qualche problema che mi sono segnato in questi tempi.

Asdrubale Schioppacanestri è stato di recente assunto come bidello nella facoltà di Cacopedia Minore (vedi ad es. qui) e ogni sera ha l'incarico di ripulire i vari uffici, spegnere le luci e chiudere tutto. Il palazzo principale della facoltà è di forma circolare: tante stanze una a fianco all'altra, aventi la stessa forma e tra di loro indistinguibili. In ciascun ufficio infatti ci sono gli stessi mobili e la mancanza di finestre [*] impedisce di capire in quale parte dell'edificio ci si trovi. Asdrubale, inoltre, ignora a priori quante siano le stanze del palazzo.

Quando inizia il suo giro di ricognizione, alcune stanze hanno la luce accesa e alcune no; il compito di Asdrubale è quello di spegnere le luci in ciascuna stanza, per poi uscire dal palazzo. Come può portare a termine il suo compito?

Alcune precisazioni:
1- Le stanze sono in cerchio e tutte identiche tra loro. Può esserci una stanza sola, come possono essercene un centinaio;
2- Asdrubale deve lasciare le stanze esattamente come le ha trovate (luci a parte), quindi non può lasciare qualche oggetto al loro interno per distinguerle;
3- Le luci sono poste sul soffitto, quindi non può usare trucchi come sentire la temperatura delle lampadine per valutare da quanto tempo la lampadina è accesa, onde distinguerle;
4- Al termine del lavoro, Asdrubale vuole essere assolutamente certo di avere spento tutte le luci, altrimenti chi lo sente poi il direttore la mattina dopo;
5- Siccome è quasi ora di cena, Asdrubale vorrebbe finire il lavoro il più in fretta possibile;
6- Tutto il personale della facoltà è già rincasato, quindi Asdrubale non può chiedere aiuto ad altri;
7- Le porte per entrare e uscire dal palazzo sono disposte a fianco di ciascuna stanza e sono anch'esse identiche, pertanto non è possibile orientarsi con esse;
8- No, non potete abbattere il contatore generale

Sapreste aiutare Asdrubale?


[*] Il palazzo, come tutti gli edifici della facoltà, è stato naturalmente progettato dal dipartimento di Architettura Astutissima della stessa facoltà, le cui sedi vantano molte soluzioni architettoniche originali e intelligenti (ma purtroppo mai le due cose assieme).

[Pasquale]

Stando all'esposizione del quesito, sembra che Asdrubale debba visitare tutte le stanze (ripulire, ecc.) e per farlo deve farlo con le luci accese, per cui se sono spente le deve accendere; quindi, quando esce da ogni stanza, spegne e chiude la porta. Quando ha fatto questo in tutte le stanze, ha terminato il suo compito e se ne va dalla porta a fianco dell'ultima stanza visitata.
Se potesse farlo, a cosa gli servirebbe sentire la temperatura delle lampadine? A perdere più tempo?
In cosa bisogna aiutarlo? Fargli visitare un numero minore di stanze? Solo quelle con le luci accese? Non fargli visitare due volte la stessa stanza?

[0-§]

sembra che Asdrubale debba visitare tutte le stanze (ripulire, ecc.) e per farlo deve farlo con le luci accese, per cui se sono spente le deve accendere

Diciamo che Asdrubale sa di avere già ripulito le stanze, per cui il suo unico obiettivo adesso è spegnere le luci in tutte le stanze. Non è necessario visitarle tutte, anzi l'obiettivo è spegnere le luci nel minor numero di "mosse" (ossia di stanze visitate).

Quando ha fatto questo in tutte le stanze, ha terminato il suo compito e se ne va dalla porta a fianco dell'ultima stanza visitata.

Il problema del metodo di Pasquale è che Asdrubale non può sapere di avere passato tutte le stanze: nella condizione iniziale infatti alcune stanze sono già con la luce spenta.
A un certo punto, terminato il giro (e spente tutte le luci), inizierà a trovare una sfilza di stanze con la luce spenta: ma come fa a sapere che in quelle stanze c'è già stato? Magari sono stanze in cui la luce era già spenta e continuando a camminare potrebbero esserci altre stanze in cui ancora non è passato (e questo perché le stanze sono indistinguibili, a parte il fatto di avere la luce accesa o spenta, e Asdrubale non sa quante siano). Così facendo, Asdrubale sarebbe obbligato a continuare a girare in tondo nel palazzo fino alla mattina dopo, e per giunta senza mai essere sicuro di avere veramente controllato in tutte le stanze!

Se potesse farlo, a cosa gli servirebbe sentire la temperatura delle lampadine?

Questo vincolo serve a evitare soluzioni "creative" che richiedono di stabilire se in una stanza la luce è stata spenta da poco o da molto.

In cosa bisogna aiutarlo? Fargli visitare un numero minore di stanze? Solo quelle con le luci accese? Non fargli visitare due volte la stessa stanza?

Asdrubale vuole visitare il minor numero di stanze possibile. Non ci sono problemi nell'entrare in stanze con la luce spenta o in stanze in cui è già stato, ma al termine deve essere sicuro di averle controllate tutte.

[delfo52]

non può lasciare qualche oggetto al loro interno per distinguerle

se ne deduce che può lasciare qualcosa all'esterno? un post-it sulla prima porta farebbe comodo!

[0-§]

se ne deduce che può lasciare qualcosa all'esterno?

Nemmeno: le stanze sono e devono restare (in ogni istante) indistinguibili, eccetto appunto per la luce.
Ricordo che non si tratta di ricavare soluzioni di pensiero laterale, ma un algoritmo (il più efficiente possibile) per spegnere tutte le luci.

P.S. Per essere del tutto chiari: le stanze sono sì uguali tra loro, ma Asdrubale chiaramente è in grado di riconoscere quando passa da una stanza all'altra, pertanto è in grado di contare di quante stanze si è mosso

[Pasquale]

Il primo giorno di lavoro, ragionevolmente, potrei aprire in sequenza le porte una ad una, conteggiandole tutte ed accendendo la luce in ogni stanza con la luce spenta, continuando così, fino a raggiungere un totale di 10.000 stanze visitate, senza aver trovato già da un pezzo alcuna stanza con la luce spenta; a questo punto, inizierei a spegnere la luce in ogni stanza, avviando un nuovo conteggio per ognuna di tali operazioni, fino a trovare una prima stanza con la luce spenta (da non conteggiare), raggiungendo così nel conteggio il numero N di luci spente in questa seconda operazione, che deve essere maggiore o uguale alla quantità di luci accese nella prima operazione.
Qui mi fermerei per andare via, ritenendo, ragionevolmente, di avere spento tutte le luci.
Dal secondo giorno di lavoro in poi, conteggiando una ad una tutte le stanze visitate in sequenza, spegnerei ogni luce trovata accesa, fino a raggiungere nel conteggio un totale di N stanze visitate.
Se vogliamo essere più ragionevoli, potremmo anche diminuire il 10.000 del primo giorno, ma se dobbiamo ipotizzare l'esistenza di un'infinità di stanze, allora non saprei come regolarmi.
In sostanza si tratta di un'operazione tendente a conoscere il numero di stanze esistenti, che non risponde a quanto richiesto da ZeroInf, ma finora non mi è venuto di meglio.

[franco]

Asdrubale inizia da una stanza (che chiamiamo per comodità stanza $0$) e ne esce lasciando deliberatamente la luce accesa.
A quel punto inizia a controllare le stanze muovendosi in senso orario sino a che ne trova una con la luce accesa (diciamo la numero $A$); la spegne e torna indietro di $A$ passi alla $0$.
Se alla $0$ trova la luce accesa ripete l'operazione sino a trovare una nuova luce accesa alla stanza numero $B$ e ancora torna indietro alla $0$ contando $B$ passi.
Ci sarà un momento in cui, dopo aver spento la luce alla stanza $N$, Asdrubale ritornerà alla $0$ e troverà la luce spenta.

A questo punto ci sono 2 possibilità (*):
- la lampadina si è fulminata (ma Asdrubale può verificarlo facilmente azionando l'interruttore)
- la luce è spenta perché l'edificio ha $N$ stanze e quindi la numero $N$ coincide con la $0$

Naturalmente tutto questo vai e vieni si limita al primo giorno di lavoro. Una volta appurato che le stanze sono N basterà i giorni successivi contarle durante il giro di controllo luci.


(*)In realtà ci sono anche altre possibilità: fantasmi, ragazzi burloni, extraterrestri con comandi a distanza, ... ma in tal caso Asdrubale non ha scampo

ciao

[franco]

PS

Probabilmente l'algoritmo è più efficiente se Asdrubale ad ogni tentativo inverte il senso di rotazione (va alla A in senso orario, alla B in senso antiorario, alla C nuovamente in senso orario ...).
Camminerà un po' meno però rischia più facilmente di perdere l'orientamento e non capirci più nulla

[Pasquale]

Bellissima la tua soluzione Franco: non lascia margini a situazioni indefinite come la mia del primo giorno; si anch'io lascerei la stessa direzione, ma se cambiarla significasse un risparmio, si può sempre fare, tanto si tratta di una situazione teorica.
Non so se Zeroinf abbia in mente un algoritmo risolutivo sin dal primo giorno, che potrebbe essere lo stesso tuo; vale a dire che una volta trovata spenta la prima lampadina, il giro è finito e Asdrubale se ne va, così regolandosi ogni volta.
Forse si potrebbe risparmiare negli andirivieni, facendo le stanze a due a due: si arriverebbe in minor tempo alla prima lampada, se le stanze sono pari (questo si saprebbe dai conteggi); quindi si procederebbe sempre a due a due, sulle stanze saltate nella prima tornata (diciamo che in questo caso si sarebbe individuato N/2.
Nel caso di stanze dispari, devo scappare e poi ci penserò (ho fatto tutto in fretta, è un abbozzo di idea, ma mi sembra una strada possibile). Ciao.

[franco]

Dipende da che criterio usiamo per valutare l'efficienza.
Per minimizzare il numero di stanze controllate credo convenga girare sempre nello stesso verso.
Per minimizzare il percorso credo convenga alternarlo.
(Ma in entrambi i casi sono solo congetture)
Ciao

[0-§]

La soluzione di Franco è senza dubbio corretta e dà luogo all'algoritmo più semplice.
Tuttavia c'è un margine di miglioramento

si anch'io lascerei la stessa direzione, ma se cambiarla significasse un risparmio, si può sempre fare, tanto si tratta di una situazione teorica

Non vedo controindicazioni al cambio di direzione e questo effettivamente riduce la distanza percorsa, anche se non il numero di stanze visitate.

Non so se Zeroinf abbia in mente un algoritmo risolutivo sin dal primo giorno, che potrebbe essere lo stesso tuo; vale a dire che una volta trovata spenta la prima lampadina, il giro è finito e Asdrubale se ne va, così regolandosi ogni volta.

Sì, pensavo appunto a un algoritmo che dia la garanzia di funzionare fin dal primo giorno (o per meglio dire, il primo giorno, perché dal secondo giorno Asdrubale sa quante sono le stanze e il problema non si pone).

Forse si potrebbe risparmiare negli andirivieni, facendo le stanze a due a due: si arriverebbe in minor tempo alla prima lampada, se le stanze sono pari (questo si saprebbe dai conteggi); quindi si procederebbe sempre a due a due, sulle stanze saltate nella prima tornata (diciamo che in questo caso si sarebbe individuato N/2.
Nel caso di stanze dispari, devo scappare e poi ci penserò (ho fatto tutto in fretta, è un abbozzo di idea, ma mi sembra una strada possibile).

La proposta di Pasquale è originale (non l'ho trovata dove ho pescato in origine questo problema) e meriterebbe di venire sviluppata.

Ciao
0-§

[Pasquale]

Mi sa che visitando le stanze una si ed una no, Asdrubale non ha sempre modo di stabilire, se le stanze sono in quantità pari o dispari.
Ad esempio, poniamo che le stanze fossero 5: in tale caso, saltando dalla 1^ alla 3^ e poi alla 5^, alla 2^, alla 4^ ed infine alla 1^ stanza, in 5 salti le si visiterebbero tutte e giunti alla 1^, il lavoro sarebbe terminato (stanze di numero dispari si visitano tutte con salti di numero dispari).
Tuttavia, non è vero il contrario, cioè non è detto che con salti effettuati in quantità dispari anche il numero delle stanze sia tale.
Infatti, poniamo che le stanze fossero 10, saltando dalla 1^, alla 3^, 5^, 7^, 9^ e per ultima alla 1^ stanza, anche qui in 5 salti si giungerebbe a spegnere la 1^ stanza, ma tutte le stanze pari non sarebbero state visitate ed occorrerebbe quindi completare il lavoro con altrettanti nuovi salti nelle posizioni di ordine pari.
Questa situazione di indefinibilità, nel caso dei salti in quantità dispari, implicherebbe per sicurezza la necessità di continuare il lavoro nelle posizioni pari, pur se già fatto.
Spero di essere stato chiaro.

[0-§]

Che mi dite del seguente metodo?

1) Asdrubale accende la luce della stanza in cui si trova.
2) Asdrubale si muove, in senso orario, di una stanza, passando alla stanza successiva. Se la luce è accesa, la spegne.
3) Asdrubale torna indietro (in senso antiorario) di una stanza, fino alla stanza da cui è partito. Se trova la luce è spenta, ha finito; altrimenti prosegue con il prossimo passaggio.
4) Asdrubale si muove, in senso antiorario, di due stanze; se trova stanze con le luci accese, le spegne.
5) Asdrubale torna indietro (in senso orario) di due stanze, fino alla stanza da cui è partito. Se trova la luce spenta, ha finito (come al punto 3), altrimenti prosegue.
6) Asdrubale si muove, in senso orario, di quattro stanze; se trova stanze con le luci accese, le spegne.
7) Asdrubale torna indietro (in senso antiorario) di quattro stanze, fino alla stanza da cui è partito. Se trova la luce spenta, ha finito (come al punto 3), altrimenti prosegue.

Eccetera. In pratica, a ogni iterazione Asdrubale raddoppia il numero di stanze visitate e inverte in senso di rotazione.
Il metodo funziona in tutti i casi? Se ci sono R stanze, quante stanze dovrà visitare Asdrubale (contando anche quelle in cui entra per controllare, ma senza spegnere la luce) nel caso peggiore? E come valore medio atteso, nell'ipotesi che ogni stanza abbia il 50% di probabilità di avere la luce accesa?