Quante candeline?

Oggi sono uscito per una passeggiata a piedi e mi sono portato dietro un nuovo problema logico: «Un elfo è dentro la torta magica di un gigante. In pratica si trova in un cunicolo completamente buio a forma di ciambella dal cui soffitto sbucano le basi delle candeline (è la sua torta di compleanno ed ha ALMENO 2 anni). Alla base le candeline hanno un interruttore per accenderle che l’elfo può leggere e modificare. Al momento alcune candeline sono accese e altre spente. L’elfo può vedere la base di una candelina alla volta. Lo scopo dell’elfo è scoprire il numero esatto di candeline (come detto maggiore o uguale a due): l’elfo potrà muoversi avanti e indietro nel cunicolo quanto e come vuole ma non può lasciare segni sulle pareti o altro: può solo sfruttare gli interruttori...»

Non si tratta di un problema particolarmente difficile o interessante di per sé ma ho notato un’evoluzione nell’euristica della mia soluzione.

Finalmente, dopo averne risolti almeno una dozzina, non temo più che la soluzione sia una “furbata” che non ha niente a che vedere con la logica. Questo dubbio costantemente mi distraeva togliendomi capacità di concentrazione. Beh, forse è da due o tre problemi che inizio ad aver fiducia nella “qualità” dei problemi proposti dalle fonti (canali YouTube) che ormai riconosco.

Una seconda novità è che qui, più volte, mi sono ricordato di dover essere logico: di non aver cioè paura di andare al nocciolo del problema anche quando ciò mi porta a conclusioni controintuitive. In questo caso ci sono riuscito parzialmente: non sono andato dritto alla soluzione come avrebbe fatto uno Spock (il vulcaniano di Star Trek) ma, credo, ho divagato meno del solito.

SCIUPATRAMA
==--==--==--==

Inizialmente da buon informatico: le candeline accese o spente mi hanno portato a pensare ai numeri binari. Contemporaneamente mi sono reso conto che il problema per l’elfo è capire quando compie il giro della ciambella: per quanto ne sappiamo il gigante potrebbe avere anche 1000 o 100000 anni!
Voglio dire che se si sapesse che il gigante ha al massimo 200 anni si potrebbe spegnere tutte le candeline contandone 201 (per essere sicuri di averle spente tutte) e poi accenderle tutte una alla volta contando quante se ne accendono. Ma non sapendo il numero massimo di candeline non si può applicare questa strategia.
Ho iniziato a pensare di accendere/spegnere le candeline e invertire la direzione di marcia nel cunicolo ma senza arrivare a nulla.
Poi ho pensato di usare le candeline per contare usando numeri binari il numero di candeline incontrate, tornando ogni volta indietro per aggiornare il contatore binario (ma è dubbio che l'elfo possa avere la memoria perfetta per ricordare quale debba essere la configurazione binaria delle candeline accese o spente, soprattutto per numeri binari di molte cifre).
Contemporaneamente, come spiegato, ogni tanto mi ripetevo di dover essere logico e, quindi, di trovare la maniera per capire quando si è fatto il giro del cunicolo.
Alla fine, dopo 10-15 minuti, ho abbandonato la fuorviante idea dei numeri binari e ho trovato una soluzione semplice: usare due candeline accese per marcare l’estremità sinistra e destra della parte del cunicolo esplorata. Quando poi le due candeline accese coincidono vuol dire che abbiamo esplorato l'intero cunicolo e quindi trovato il numero cercato.

Questa è l’idea di base che poi ho perfezionato per renderla meno ambigua e, volendo, ottimizzarla un po’. Inoltre c’era il caso limite del gigante con solo due anni (e quindi due candeline) che non mi tornava molto…

Ma avendo questi elementi in mente la soluzione corretta (più lineare) è facile da trovare: inizialmente “inizializziamo” le due candeline che sicuramente esistono spegnendo la prima che troviamo e accendendo la seconda. La prima candelina spenta marca l’estremità sinistra del cunicolo esplorato, mentre quella accesa è l’estremità destra: è chiaro che quando la prima candelina si accende significa che si è fatto il giro completo della ciambella.

Supponiamo che il gigante abbia 10 anni, avremo [legenda: X candela non esplorata; 0 candela spenta; 1 candela accesa]:
10 candeline
XXXXXXXXXX

entriamo in un punto a caso del cunicolo, spegniamo una candelina e accendiamo la successiva:
XXX01XXXXX

ora spegnamo la candelina accesa e ci spostiamo a destra accendendo quella che troviamo:
XXX001XXXX

adesso torniamo 2 candeline a sinistra per verificare che la candelina marcatrice all’estremità sinistra sia sempre spenta.
Siccome questo è il caso ritorniamo tutto a destra, spegnamo la lampadina accesa e accendiamo la successiva:
XXX0001XXX

adesso torniamo 3 candeline a sinistra e verifichiamo che la candelina all’estremità sinistra sia sempre spenta.
Siccome questo è il caso torniamo tutta a destra e ripetiamo quanto fatto al passo precedente ovviamente tornando poi a sinistra di un passo in più ogni volta.
Alla fine arriveremo a questa situazione:
0010000000

Torniamo quindi indietro di 9 candeline e verifichiamo che la candelina all’estremità sinistra (la quarta) è sempre spenta. Andiamo tutto a destra, spegnamo la lampadina accesa e accendiamo la successiva:
0001000000

Adesso però, quando torniamo indietro di 10 candeline troviamo il marcatore acceso: questo significa che le candeline sono in tutto 10.

Caso con 3 candeline:
XXX

X01

100
(due va bene)

010
(tornando indietro di tre passi troviamo il marcatore acceso: significa che le candeline sono tre)

Caso con 2 candeline:
XX

01

10
(adesso tornando indietro di due candeline, siamo alla prima, la ritroviamo accesa: quindi le candeline sono 2)

Comunque, dopo aver risolto questo problema, mi sono reso conto che devo migliorare a usare la logica per scartare tentativi di soluzione che non portano da nessuna parte. Per esempio il contare in binario le candeline esplorate mi aiuta a riconoscere quando finisco il giro? Nì: se mi accorgo che il numero binario che devo aggiornare è stato modificato (ma non sempre è immediato accorgersene) allora potrebbe funzionare ma sarebbe estremamente e inutilmente più complicato della soluzione più semplice.
Per qualche motivo ho una forte resistenza ad abbandonare una strade per cercarne una nuova che non so se esiste e che mi devo immaginare: è un piccolo sforzo creativo che per qualche motivo esito troppo a fare...
Avrei dovuto subito rendermi conto che non c’era bisogno di usare le candeline come numeri binari ma che bastava usare una sorta di marcatore: poi alla fine ci sono arrivato ma probabilmente ho sprecato 8 minuti inutilmente.

La parte rossa indica la parte del tragitto in cui ero molto concentrato su tentativi di soluzione errate; la parte blu è il tratto di strada molto breve (probabilmente l’ho accentuato più del dovuto) dove finalmente ho sviluppato l’idea corretta; nella parte in verde l’ho poi perfezionata considerando e verificando anche i casi speciali con 2 o 3 candeline solamente: a questo punto però non ero più molto concentrato sul problema perché avevo già capito di averlo risolto e che mi rimanevano solo i dettagli, a occhio forse ci pensavo il 40% del tempo ripetendo e controllando più volte gli stessi passaggi; dal tratto viola in poi ho smesso di pensarci perché ho giudicato il problema completamente risolto (sono arrivato fino al Duomo prima di tornare indietro percorrendo un diverso tragitto)…

Conclusione: sarà interessante vedere se la prossima volta che esco a piedi con un problema sarò in grado di applicare effettivamente questi miei buoni propositi!

PS: ah! mi ero dimenticato di accennare a una possibile ottimizzazione: quando ci spostiamo a destra di una candelina se la troviamo accesa possiamo spegnerla e passare alla successiva: torneremo indietro solo quando ne troviamo una spenta che accendiamo...

Share