Olimpo Informatico

[ZapoTeX]

Emy entra in una stanza non illuminata ma dotata di 3 interruttori numerati con 1, 2 e 3, di cui non conosce lo stato (acceso o spento). Ogni interruttore può essere acceso o spento e, affinché la stanza sia illuminata, occorre che tutti e tre siano accesi. Emy preme l´interruttore 1 e la stanza non si illumina. Preme allora l´interruttore 2, ma la stanza non si illumina ancora. Cerca allora una strategia che le permetta di illuminare la stanza in un numero minimo di tentativi. Applicando questa strategia, quale sequenza di interruttori Emy deve azionare, nel peggiore dei casi?

giochino inventato dal centro pristem per la semifinale italiana del 2000

[emilio.roda]

Proviamo...

[ulisse]

Le possibili configurazioni di n interruttori (escluso la prima di partenza) sono quelle dette da emilio.

La configurazione degli interruttori può essere rappresentata da una stringa binaria di lunghezza n.

A quest'ora ho zero energie quindi mi limito al caso n=3.
Chiamiamo 000 la configurazione iniziale.
Emy ha provato la 100 e poi, pigiando il secondo interruttore ha provato la configurazione 110.

Il suo problema è quello di provare tutte le configurazioni residue passando da una all'altra tramite il cambio di stato di un singolo interruttore e, soprattutto, senza provare due volte la stessa configurazione.

Una soluzione possibile è la seguente:

[ZapoTeX]

La soluzione è corretta. Mi ricordo che le soluzioni possibili erano tre, di cui due basate sulla stessa idea (tra cui quella di Ulisse), e una un po' diversa, ma il numero di interruttori da pigiare era sempre quello.

Ciao!