8 PEOPLE PUZZLE

There are 8 people, who need to cross a river in  single boat. People are 1 Cop, 1 Thief, 1 Man and his 2 Daughters, 1 Women and her 2 sons. As usual the conditions that has to be satisfied while crossing the River are given below:
•    When Police man is not on that river bank, Thief will beat all the people available on that river bank.
•    When Women is Not on that river bank, Man will beat her 2 sons.
•    When Man is Not on that river bank, Woman will beat his 2 daughters.
•    Only Two people can travel in the boat at any given time.
•    2 Sons and 2 daughters doesn’t know to drive the boat.
ANSWER
Please follow Step by Step process as defined below:
Initial stage Cop, Thief, Men, Daughters, Women, Sons are at River Bank – 1
1.    Pick up Cop-Thief pair and travel to River bank – 2
2.    Drop the Thief at River bank – 2 and cop only will reach back River bank – 1
3.    Cop will Pick up Daughter – 1 at river bank -1 and travels to River Bank -2
4.    Cop will drop the daughter – 1 at river bank – 2 and picks thief along with him and reaches back to River bank – 1
5.    Both Cop and thief pair will drop at River bank -1
6.    Now Man along with his Daughter – 2 travels from River bank -1 to River Bank -2
7.    Man will drop his Daughter -2 at river bank – 2 and reaches back River Bank – 1 single
8.    Now Man will pick up Women at River bank -1 and reaches to River bank – 2
9.    Man will get down at river bank-2 and Women alone will return back to River bank – 1
10.    Women will get down at River bank -1 . Cop and Thief pair will travel from River bank – 1 to River bank – 2
11.    Cop and Thief will get down at River bank – 2. Man alone will travel back to River bank -1
12.    Man picks up woman at River bank -1 and reaches back to River bank -2
13.    Man will get down at River bank – 2 and women alone will sail back to River bank -1
14.    Women will pick up her Son – 1 at River bank – 1 and travels back to River bank – 2
15.    Women along with her son – 1 will get down at River bank -2.
16.    Cop and Thief  pair will travel from River bank – 2 back to River bank – 1
17.    Cop will drop Thief at River bank -1 and picks Son -2 and reaches River bank -2
18.    Cop will drop son-2 at river bank -2 and sails back to River bank -1 to pick up thief
19.    Both Cop an Thief pair will reach back River bank – 2 safely.

Egg Drop

Assume that we have m eggs, and n drops are allowed. Let us represent the height of the tallest building by g (m, n), for which we can find a solution with these constraints.

g (m, n) = g(m – 1, n – 1) + g (m, n – 1) (n > 0)
g (m, 0) = 1.

This is because if we drop the first egg from the g(m – 1, n – 1)-th step, if it breaks, we still have

(m – 1) eggs and (n – 1) steps, which are enough to detect in a building of height up to g (m – 1, n – 1).

On the other hand, if it does not break, we have m eggs and (n – 1) steps, which can give us extra

g (m, n – 1) height to be able to detect.

For fixed n, the expression of g(m, n) can be calculated explicitly., e.g..

g (2, n) = n * (n + 1)/2, (n >= 3 )

Explanation

n + (n-1) + (n-2) + (n-3) + (n-4) + … + 1 >= 100

n (n+1) / 2 >= 100

3 Eggs

h(3,m) = (m-1)m/2 +1 + (m-2)(m-1)/2+1 + … = SUM (1/2)j^2 – (1/2)j +1 for j from 1 to m and

we get (1/12)m(m+1)(2m+1) – (1/4)m(m+1) + m = (1/6)(m^3 -m) + m = (1/6)(m-1)m(m+1) + m.

(1/6)(m-1)m(m+1) + m < 100 which gives m =9

So 9 is enough.

CODE

When we drop an egg from a floor x, there can be two cases (1) The egg breaks (2) The egg doesn’t break.

1) If the egg breaks after dropping from xth floor, then we only need to check for floors lower than x with remaining eggs; so the problem reduces to x-1 floors and n-1 eggs
2) If the egg doesn’t break after dropping from the xth floor, then we only need to check for floors higher than x; so the problem reduces to k-x floors and n eggs.

/* Function to get minimum number of trails needed in worst
  case with n eggs and k floors */
int eggDrop(int n, int k)
{
    // If there are no floors, then no trials needed. OR if there is
    // one floor, one trial needed.
    if (k == 1 || k == 0)
        return k;
 
    // We need k trials for one egg and k floors
    if (n == 1)
        return k;
 
    int min = INT_MAX, x, res;
 
    // Consider all droppings from 1st floor to kth floor and
    // return the minimum of these values plus 1.
    for (x = 1; x <= k; x++)
    {
        res = max(eggDrop(n-1, x-1), eggDrop(n, k-x));
        if (res < min)
            min = res;
    }
 
    return min + 1;
}