I quattro interruttori

Gianluca ha detto...

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).