Posts

Showing posts with the label blind bartender's problem

Four Glasses Puzzle

Four glasses are placed on the corners of a square table. Some of the glasses are upright (up) and some upside-down (down). A blindfolded person is seated next to the table and is required to re-arrange the glasses so that they are all up or all down, either arrangement being acceptable, which will be signaled by the ringing of a bell. 

The glasses may be re-arranged in turns subject to the following rules. 

1.Any two glasses may be inspected in one turn and after feeling their orientation the person may reverse the orientation of either, neither or both glasses.

2.After each turn the table is rotated through a random angle. 

3.The puzzle is to devise an algorithm which allows the blindfolded person to ensure that all glasses have the same orientation (either up or down) in a finite number of turns. The algorithm must be non-stochastic i.e. it must not depend on luck.

Four Glasses Puzzle

Here is that algorithm!

Solution of Blind Bartender's Problem


What was the puzzle?

Below is the algorithm which makes sure the bell will ring in at most five turns.

1.On the first turn choose a diagonally opposite pair of glasses and turn both glasses up.
At this point, the position of other 2 glasses is not known.

Solution of Blind Bartender's Problem

2.On the second turn, choose 2 adjacent glasses. One of them was turned up in the previous step, so other may or may not in up position. If the other is down then turn it up and if remaining one X is also in up position then bell will be rung.

Solution of Blind Bartender's Problem

If the bell does not ring then there are now three glasses up and one down(3U and 1D).

Solution of Blind Bartender's Problem

3.On the third turn choose a diagonally opposite pair of glasses. If one is down, turn it up and the bell will ring.

Solution of Blind Bartender's Problem

And if you find both are up, then you must have chosen other diagonally opposite pair.

Solution of Blind Bartender's Problem

If so, then turn one down so that 2 glasses are up and other 2 are down.

Solution of Blind Bartender's Problem

4.On the fourth turn choose two adjacent glasses and reverse both. If both were in the same orientation then the bell will ring. 


Solution of Blind Bartender's Problem

And in case, if you find one is up and other down like -


Solution of Blind Bartender's Problem

still reverse orientation of both as - 


Solution of Blind Bartender's Problem

Now diagonally opposite pairs are either up or down.

5.On the fifth turn choose a diagonally opposite pair of glasses and reverse both.

Solution of Blind Bartender's Problem

The bell will ring for sure.

Solution of Blind Bartender's Problem

   
Follow me on Blogarama