mercoledì, ottobre 27, 2010

I quattro interruttori


Forse qualcuno ricorderà (o già conosceva) l'indovinello "I tre interruttori". Oggi vi propongo una versione più elaborata (e ben più difficile da risolvere!). Stavolta gli interruttori sono 4, e sono messi ai quattro angoli di un tavolo quadrato. Gli interruttori sono dei bottoni che possono assumere due possibili stati (0/1) e ad ogni pressione cambiano stato. Tuttavia il bottone in sé non cambia aspetto se è nello stato 0 oppure nello stato 1. In un'altra stanza è presente una lampadina (in posizione tale per cui non la si può toccare come nell'enigma "I tre interruttori" che si accende solo se i quattro interruttori sono nel medesimo stato (0,0,0,0 oppure 1,1,1,1). Quando si è nella stanza dei bottoni si può premere qualunque bottone qualunque numero di volte, ma per controllare se la lampadina è accesa occorre uscire dalla stanza e quando lo si fa la porta si chiude e il tavolo su cui sono i bottoni ruota compie una rotazione puramente casuale. Individuare la strategia ottimale per accendere la lampadina, laddove per strategia ottimale si intende quella che richieda il minimo numero di visite alla stanza dov'è contenuta la lampadina. Chiaramente si deve avere la certezza matematica di accendere la lampadina, quindi non va minimizzato il numero minimo di visite (potrebbe anche bastarne una, se si è fortunati), quanto piuttosto quello massimo nel caso in cui si sia "sfortunatissimi".

7 commenti:

Marco ha detto...

Non so se è la strategia ottimale, ma per il momento è l'unica che mi è venuta in mente.
Innanzitutto, come prima cosa vado a vedere se la luce è già accesa, hai visto mai!? ;-)
Poi, considerando che premere 1 o 3 bottoni non mi cambia niente, e che, allo stesso modo, le luci possono essere con valori opposti solamente di 1 o di 2, seguirò a ciclo il seguente schema:
- premo un solo bottone e controllo
- premo due bottoni su uno stesso lato e controllo
- premo due bottoni su due spigoli opposti in diagonale e controllo
Ho fatto qualche test e il numero massimo di volte che ho controllato la luce è stato 15, ma la maggior parte delle volte era inferiore a 10, con naturalmente anche eccesioni più fortunate.

Walter ha detto...

Non è la strategia ottimale, pensaci meglio ;-)

Marco ha detto...

Vale segnare i vari bottoni con un pennarello per distinguerli?

Walter ha detto...

No, non è concesso l'uso di espedienti "out-of-the-box". In pratica non si possono usare espedienti come toccare la lampadina, marcare i bottoni o altre cose simili.

Gianluca ha detto...

Ciao,

vi seguo da tempo...complimenti per il sito.
Ecco il mio contributo su questo gioco.

Prima di tutto alcune definizioni e considerazioni preliminari.
Possono esistere 3 tipi di configurazioni base, le atre tutte assimilabili a queste o con rotazioni tavolo o inversioni complete dello stato di tutti gli interruttori (entrambe, queste, operazioni ininfluenti, date le condizioni poste dal problema):
a) (un solo interruttore in uno stato diverso dagli altri)
10
00

b) (2 interruttori diversi, posti su una diagonale)
10
01

c) (2 interruttori diversi, posti lateralmente)
11
00

Le mosse possibili, invece sono di 3 tipi base:
A) mossa singola: premo un solo interruttore
B) mossa diagonale: premo 2 interruttori in angoli opposti
C) mossa laterale: premo 2 interruttori in angoli adiacenti.
Non è infatti importante quali interruttori si premano, ma solo le posizioni relative di quelli che si premono (dato che ad ogni controllo il tavolo gira…).
Le altre mosse sono tutte assimilabili a queste; p.e. se premo tre interruttori di fatto ho eseguito la mossa A più una inversione di stato di tutti gli interruttori.

Ora passo a descrivere la strategia che mi sembra ottimale.
Immaginando di partire da una conf. tipo b) o c), effettuo una mossa B): come risultato posso aver terminato (se partivo da conf. b) oppure trovami ancora in una conf. c).
Ora effettuo una mossa C): posso aver concluso (se ho preso proprio i due interruttori nello stesso stato) oppure trovarmi in una conf. b).
A questo punto basterà effettuare un’ultima mossa B) e avrò concluso. Riassumendo, eseguirò la sequenza B) - C) - B).

Ora immagino invece di partire dalla conf. a): effettuando la sequenza B) - C) - B), non avrò cambiato per nulla la configurazione (essendo questa stessa non influenzata dalle mosse tipo B) o C)).
Se dopo la sequenza B) - C) - B) la luce è ancora spenta, dunque, vuol dire che mi trovavo e mi trovo ancora in una conf. a); ma allora basterà eseguire la mossa A) per passare in una conf. b) o c) e poi di nuovo la sequenza B) - C) - B) per concludere in ogni caso possibile.

Riassumendo, nel caso peggiore effettuerò 7 mosse: B) - C) - B) - A) - B) - C) - B).

Gianluca

Walter ha detto...

Esatto, 3 punti per te, Gianluca :-)

Marco ha detto...

È vero!
Bravo Gianluca. :D