Tuesday, December 31, 2013

Puzzle Time

Its amazing that in day to day life in office and discussion with colleges churn out some really interesting knowledge bits and these bits sometimes vibrate quite a bit of threads in your head. Here are some of those bits.
  
** River crossing: she-goat, wolf and cabbage 

Description:

A farmer is returning from market, where he bought a she-goat, a wolf and cabbage. On the way home he must cross a river. His boat is little, allowing him to take only one of the three things. He can’t keep the she-goat and the cabbage together (because the she-goat would eat it), nor the she-goat with the wolf (because the she-goat would be eaten). How shall the farmer get everything on the other side (without any harm)?

Solution:

farmer crosses with goat
farmer returns alone
farmer crosses with cabbage or wolf
farmer returns with goat
farmer crosses with whichever (cabbage or wolf) he didn’t take the first time
farmer returns alone
farmer crosses with goat
they are all on the other side

** Four glasses puzzle/ blind bartender's problem (
http://en.wikipedia.org/wiki/Four_glasses_puzzle)

Description: 

Four glasses or tumblers are placed on the corners of a square rotatable table. Some of the glasses are upright (up) and some upside-down (down). A blindfolded person is seated next to the rotatable 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 signalled 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.

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.
 

Solution:

An algorithm that guarantees the bell will ring in at most five turns is as follows:
  1. On the first turn choose a diagonally opposite pair of glasses and turn both glasses up.
  2. On the second turn choose two adjacent glasses. At least one will be up as a result of the previous step. If the other is down, turn it up as well. If the bell does not ring, then there are now three glasses up and one down.
  3. On the third turn choose a diagonally opposite pair of glasses. If one is down, turn it up and the bell will ring. If both are up, turn one down. There are now two glasses down, and they must be adjacent.
  4. On the fourth turn choose two adjacent glasses and reverse both. If both were in the same orientation then the bell will ring. Otherwise there are now two glasses down and they must be diagonally opposite.
  5. On the fifth turn choose a diagonally opposite pair of glasses and reverse both. The bell will ring.


No comments:

Post a Comment