Interview Question: Puzzle - 100 Prisoners

In my latest interview I encountered the following puzzle.

There are 100 prisoners in the prison. All of them have either black or white cap.

Jailer has asked them to stand in the queue such that nth guy can see caps of all the guys standing ahead of him, but he can not see his own cap.

It means Guy standing at 100th position can see caps of all other 99 guys. Prisoner standing at 99th position can see caps of rest of 98 guys standing ahead of him.

Now jailer proposes to release the guy who can guess correct color of his own cap.

Assuming All the prisoner are nice guys ;), who can sacrifice for others, device a method which can help to release maximum number of prisoners.

Puzzle: 5 Greedy and Super Intelligent Pirates

 

Problem Statement

One group of 5 pirates looted one ship having 1000 gold coins. Each pirate is fearsome, super intelligent and greedy.

Conditions:

1. These pirates have hierarchy based on their age. Pirate, having superior age. has first right to take the decision.

2. Each of the pirate will vote on each decision and decision is accepted if and only if at least 50% people are in favor of the decision otherwise leader(one, who took the decision) of the group will be killed.

Senior most guy of the group took one decision in order to distribute the gold coins and he was not killed? What was his decision?

Solution

As pirates are greedy and intelligent, so they know what is best for them. We have to tackle the puzzle from SMALLER to BIGGER number.

Lets assume if there are only 2 pirates and pirate 4 is senior. Whatever decision pirate 4 will take, pirate 5 has to accept it. So he is at the loosing side. In this situation anyone can buy pirate no 5 in small amount of money.

Now lets assume if there are only 3 pirates and pirate 3 is the senior most guy. Pirate 3 has to convince only one guy and it is highly probable he will go to Pirate 5. As pirate 5 has a danger of not getting anything and pirate 4 will try to make most by killing 3. In this scenario an intelligent pirate 3 will not take risk to convince pirate 4. He will offer one coin to pirate 5 and will win his vote.

Lets assume 4 pirates are there on the ship. In this case pirate 4 will give one coin to pirate two and will not give anything to other 2 pirates. As it is quite evident pirate 4 will not deny 1 coin as he will not receive anything if pirate 4 dies.

Now lets come to actual problem. With the above four discussion it is quite obvious. Senior most guy will offer 1 coin each to 3rd and 5th guy and for other 2 he will offer his consolation.

So solution of this puzzle would be

998 coins will go to senior most person and he will give one to 3rd and one to 5th guy and everyone will be happy forever.