Dannate tessere, dannati circuiti e dannata porta

Un problema che mi è stato posto giorni fa e alla cui soluzione sono arrivato dopo rosicati fallimenti.

Problema:
Hai tre tessere e sei davanti a una porta con tre fessure in cui puoi infilarle. Ciascuna tessera è la tessera corretta di una sola fessura e viceversa.
Ogni fessura è collegata ad un circuito che non puoi vedere e che inizialmente può essere o aperto o chiuso, e la porta si aprirà solo quando tutt'e tre i circuiti saranno chiusi. Puoi cambiare lo stato dei circuiti solo inserendo tutt'e tre le tessere, e il cambiamento avviene così: se il circuito è chiuso, si apre; se il circuito è aperto, si chiude solamente se nella sua fessura è inserita la tessera corretta.
Qual'è il minimo numero di inserimenti necessario ad aprire la porta?

Soluzione

Chiamiamo le tessere 1, 2 e 3 e rappresentiamo i diversi modi di inserirle come triple ordinate in cui la posizione della chiave corrisponde alla fessura in cui la inseriamo: ad esempio 213 significa che inseriamo la tessera 2 nella prima fessura, la tessera 1 nella seconda e la tessera 3 nella terza.
La seguente sequenza di inserimenti apre con certezza la porta con al più 8 tentativi: 123, 312, 231, 123, 213, 321, 132, 213.
Perché funziona?
Osserviamo che, presa la tripla corretta (quella che apre la porta se la inseriamo quando tutti i circuiti sono aperti), se ruotiamo (=scaliamo di posto) la posizione delle chiavi otteniamo una tripla totalmente scorretta (nessuna tessera è al posto giusto); con ruotare intendo che ad esempio 213 diventa 321.
Dunque, abbiamo due casi: o la tripla corretta è nelle prime quattro della sequenza in questione, o nelle ultime quattro.
Supponiamo che sia nelle prime quattro.

• Se uno o due circuiti sono inizialmente chiusi, allora se 123 non è quella corretta chiude subito tutto (perché è totalmente scorretta dato che ruotandola si ottiene quella corretta!), e resta tutto chiuso finché una delle tre seguenti non apre tutto;
• se invece uno o due circuiti sono inizialmente chiusi e 123 è quella corretta allora essa cambia lo stato dei circuiti ma poco male, perché poi 312 è totalmente scorretta e apre tutti i circuiti, e al quarto tentativo 123 trova tutti i circuiti aperti e li chiude, aprendo la porta.
• Se invece tutti i circuiti sono inizialmente aperti, è facile vedere che non ci sono problemi.

Infine, nel caso in cui quella corretta sia nelle ultime quattro il ragionamento è lo stesso: le prime quattro cambieranno lo stato dei circuiti e col ragionamento appena fatto le ultime quattro (contenenti la tripla corretta) in ogni caso apriranno la porta.