2

You have four switches that could be on or off that are configured in a 2x2 grid. You are given an initial configuration that is random and you are blindfolded.

(a) Can you possibly find the configuration where they are all on? (trivial, consider the 16 possible combinations)

(b) The switches are now in a 2x2 grid still. Each turn you are allowed to hit any number of the switches on/off, but at the end of each turn the switches rotate a random number of positions. Now is it possible to find the configuration where they are all on?

Asaf Karagila
  • 393,674
Jasper
  • 41
  • No it cannot be guaranteed, but randomly hiting switches will almost surely find the configuration where they are all on. – Winther Oct 16 '14 at 20:41
  • Did you happen to mean "find the configuration where they are all on or all off"? If yes, then please see my answer below (if no, then I will delete it). – barak manos Oct 16 '14 at 21:23

1 Answers1

0

Pretend that a light goes on when all switches are on or all switches are off.

Let's attribute these $2$ states to group N, and split the remaining $14$ states to groups ABCD:

 A | 0101, 1010             
---|------------------------
 B | 0011, 0110, 1100, 1001 
---|------------------------
 C | 0001, 0010, 0100, 1000 
---|------------------------
 D | 0111, 1110, 1101, 1011 
---|------------------------
 N | 0000, 1111
  • A: two opposite switches are on and two opposite switches are off
  • B: two adjacent switches are on and two adjacent switches are off
  • C: one switch is on and three switches are off
  • D: three switches are on and one switch is off
  • N: all switches are on or all switches are off

The purpose is to find a sequence of operations that will bring any state in groups ABCD to a state in group N:

  • For group A, there is an operation X that brings each one of its states to a state in group N, so it's sufficient to find a sequence of operations that will bring any state in groups BCD to a state in groups AN
  • For group B, there is an operation Y that brings each one of its states to a state in groups AN, so it's sufficient to find a sequence of operations that will bring any state in groups CD to a state in groups ABN
  • For groups CD, there is an operation Z that brings each one of its states to a state in groups ABN

Let's define these operations, from which we will perform one at each turn:

 X | xor 0101 | press the 1st switch and the 3rd switch
---|----------|-----------------------------------------
 Y | xor 0011 | press the 1st switch and the 2nd switch
---|----------|-----------------------------------------
 Z | xor 0001 | press the 1st switch

Let's define the order of operations, at the end of which the light will be on:

enter image description here

So by performing the sequence of operations XYXZXYX, you are guaranteed to reach one of the two designated states at some point during the sequence, regardless of the initial state of the grid.

barak manos
  • 43,109
  • This answers the question of "finding the configuration where all the switches on or all the switches off". If that was not OP's intention, then I will delete it. – barak manos Oct 16 '14 at 21:25