19 April 2012

Divide equal set of Head/Tail Coins on a table Problem

here is a table on which a number of coins are placed. You also know that there are as many coins with Head up as many coins with Tail up. Now you have to divide the coins (number of coins is even) into two equal piles such that number of coins with Heads up and Tails up in either piles be the same. The catch is you are blind folded and you cannot determine the sides (for sure) if you are blinded

Solution-

If you are totally blind and choose to create two sets of 25, 25 following four possible combinations are possible.
1. all heads are one side and all tails on other side
2. reverse for 1
3. 10H 15T, 15H, 10T
4. reverse of 3.

The following diagram pictorially represents the above four combinations. If you look properly in the diagram set2 is just a inverse of set1.
So the above four combinations can be represented as
set1 = A and set2 = INVERSE(A)


What we need is A in set2 to get equals number of H & T in both sets.
Make set2 equal to set1 = INVERSE( INVERSE(set1) = SET2) 

Extension to this Problem - Assume you have 10 coins with heads up and 42 with tails up. Can you still divide them into two sets so that they have equal number of heads.

Solution - trick is here the symmetry we were discussing above is lost causing the above inverse solution to fail. We can gain that symmtery by making both sets of different size.

Let's have set1 with 10 elements and set2 with 42 elements and the following combination's may exist.
1. set1 - 10H, 32T and set2 - 0H, 10T
2. set1 - 9H, 33T and  set2 - 1H, 9T
3. set1 - 8H,34T and set2 - 2H, 8T
....................
....................
....................
10 set1 - 0H, 42T and set2 - 10H

If you observe the above combination's carefully we have achieved symmetry in H
Since this problem is converted into the above problem we can safely apply the above solution by reversing all coins in the smaller set.

No comments:

Post a Comment