Questo indovinello mi è stato fatto da un collega americano alla fine di una lunga sessione di meeting in un fresco autunno californiano.
Ci sono 4 interruttori montati su di una tavola rotante, gli interruttori sono del tipo pulsante (quindi non c'è modo di sapere a priori lo stato, che siano accesi o spenti). Se tutti gli interruttori sono in "acceso" o "spento" si accende una lampadina. La lampadina si trova un ina stanza adiacente, per vedere se è accesa o spenta l'unico modo è aprire una porta e controllare, non appena apro la porta la tavola rotante (su cui sono montati gli interrutori) ruota di una quantità casuale multiplo di un angolo retto (consentito anche che non si muova).
Qual'è in massimo numero di aperture della porta che mi garantiscono di riuscire a vedere la lampadina accesa?
La risposta sotto è quella che spedii al mio collega dopo qualche giorno, quindi è in inglese.
We have 16 possible configurations (N = 2^4 = 16), not so many at the end.
Start, first of all I think the the begin situation is random, so I can be lucky, then open the door for the first time and take a look, if bulb is on I finished, point game, win, end....
Probability is 2/16 = 1/8 = 12.5%, not so bad, but normally I'm not so lucky.
So just try to change the point of view, don't think about which one is on or off but how many are on or off and in which configuration, don't think about order (otherwise probably with the table rotation is something of crazy).
When I open the door table run randomly, so what I know? Nothing about the position of switchs but I'm sure that the light is off, so the system is in one of these alternatives:
3 ON 1 OFF
2 ON 2 OFF
1 ON 3 OFF
To be honest, we don't need to take care if switch are on or off ("all on" or "all off" is the same), just consider the different status of switches. And don't care about position.
So the alternatives can be resumed as follow, where "a" is the switch status that can be 0 or 1 (boolean logic):
Configuration C1 (two buttons in the same state along a diagonal):
a a!
a! a
Configuration C2 (two buttons in the same state in adjacent location):
a a
a! a!
Configuration C3 (one button in one state and the other in the other one):
a a!
a! a!
I must be sure that something change when I press switch, so for example is completely useless to press all 4 buttons.
Due to the configuration above seems that a possible strategy is press at maximum two buttons together becouse is the worst case (two button in one status and 2 in the other status, otherwise only one in a different status).
So, the move can be:
Move M1: Press one button (not important which one, table rotate.... So the positioning is random, I have a simple mind, so the first upper left if the easy one).
X O
O O
Move M2: Press two buttons in diagonal
X O
O X
Move M3: Press two adjacent buttons (Again, positioning is random, so is non important wich edge, I choose the "upper")
X X
O O
Ok, now?
The target is to open the door he minimum numbers of times.
Paper and pencil and I made some test and in my opinion the way is to consider initially that two buttons are in a different state.
Suppose the system is in "Configuration C1", then use "Move M2".
Open the door (second time), light is on? Yes? Right stategy! So in this case the buttons was in "Configuration C1" and we finished (Hurray).
Status (T0):
a a!
a! a
Open door (1)
Move M2 (1)
Status (T1):
a! a!
a! a!
But... Light is off (damn!) the table rotate (I hate you table!).
I suppose that the system was at beginning in "Configuration C2" and using "Move M2" we remain in "Configuration C2".
So we use "Move M3" and open the door (third attempt).
Light is on? Lucky guy! Is not? If we start from "Configuration C2" right now we move to "Configuration C1", so with "Move M2" we switch on the lights and our mood improves.
Status (T0):
a a
a! a!
Open door (1)
Move M2 (1)
Status (T1):
a! a
a! a
Open door (2)
Move M3 (2)
Status (T2):
a a!
a! a
Move M2 (3)
Status (T3):
a! a!
a! a!
But is possible that the bulb is not on (argh!).
So if bulb is off I wrong to suppose that the starting condition was "Configuration C1" or "Configuration C2", so the only other possibility is starting condition was "Configuration C3".
So let's resume, we did this operations starting from "Condition 1" and after 3 moves the light is off:
Status (T0):
a a!
a! a!
Open door (1)
Move M2 (1)
Status (T1):
a! a!
a! a
Open door (2)
Move M3 (2)
Status (T2):
a a
a! a
Open door (3)
Move M2 (3)
Status (T3):
a! a
a! a!
Open door (4)
The only way to don't enter in an infinite loop is to change only the status of one switch with "Move M1".
Open the door, at this point or bulb switch on or we enter in "Configuration C1" or "Configuration C2", so with maximum more 3 moves (and 3 door openings) and we finish.
Status (T4):
a a
a! a!
Open door (5)
So, at the end, if I am a really unfortunate boy I need to open the door maximum 8 times (or maybe 7, the 8th is not necessary, I know that the light will be on but I'm curious so I will open the door 8 times).
Move sequences of an unlucky attempt:
M2
M3
M2
M1
M2
M3
M2
Non ho resistito e alla fine, nonostante la soluzione sembrasse solida, ho deciso di creare un veloce programmino di test in C++ per validare il mio ragionamento.
Se avessi fatto più di 8 tentativi di apertura porta mi sarebbe apparso un errore e si sarebbe fermato il test con molta infamia e nessuna lode.
Di seguito l'esempio dell'output di debug per un caso sfortunato in cui si vada ad aprire la porta ben 8 volte.
There are 4 switches mounted on a rotary table in a room and a bulb is placed in an adjacent room.
The switches control the bulb and the only way to check if light is on or off is to open the door.
Door opening launch a table rotation of a random value (multiple of 90 degrees).
Light is on only if all switches are off or all switches are on.
How many door openings are necessary at maximum for be sure that the light is on?
----------------------------------------------------
Simulation 1
----------------------------------------------------
Starting point
1 1
1 0
Check bulb, door opening. Attempt # : 1 -> Light is OFF
Table rotate of 90 degrees°
1 1
0 1
Move type 2:
0 1
0 0
Check bulb, door opening. Attempt # : 2 -> Light is OFF
Table rotate of 180 degrees°
0 0
1 0
Move type 3:
1 1
1 0
Check bulb, door opening. Attempt # : 3 -> Light is OFF
Table rotate of 90 degrees°
1 1
0 1
Move type 2:
0 1
0 0
Check bulb, door opening. Attempt # : 4 -> Light is OFF
Table rotate of 180 degrees°
0 0
1 0
Move type 1:
1 0
1 0
Check bulb, door opening. Attempt # : 5 -> Light is OFF
Table rotate of 270 degrees°
0 0
1 1
Move type 2:
1 0
1 0
Check bulb, door opening. Attempt # : 6 -> Light is OFF
Table rotate of 0 degrees°
1 0
1 0
Move type 3:
0 1
1 0
Check bulb, door opening. Attempt # : 7 -> Light is OFF
Table rotate of 270 degrees°
1 0
0 1
Move type 2:
0 0
0 0
Check bulb, door opening. Attempt # : 8 -> Light is ON -> END
Sotto una simulazione di un miliardo di casi, direi che con questo abbiamo tagliato la testa al toro. Insomma, oserei dire che funziona! Notare la distribuzione uniforme del numero di apertura porte effettuate (tra 1 e 8).
Number of simulation to be performed? 1000000000
Simulation result:
Light on, attempt #1 :124978789 (12.4979%)
Light on, attempt #2 :124969398 (12.4969%)
Light on, attempt #3 :125038420 (12.5038%)
Light on, attempt #4 :124985988 (12.4986%)
Light on, attempt #5 :125015993 (12.5016%)
Light on, attempt #6 :125010382 (12.501%)
Light on, attempt #7 :125010537 (12.5011%)
Light on, attempt #8 :124990493 (12.499%)