Easy | Strategy |

Five pirates need to divide 100 Gold Coins. Pirates have hierarchy, from Level 5 to level 1. The level-5 pirate proposes a division plan and all the pirates vote on it. If at least 50% of the pirates agree on the plan, the gold is split according to the proposal. If not, level-5 pirate is kicked from the ship, and the level-4 pirate now proposes a plan. This process continues until a proposal is accepted. All pirates are extremely smart and extremely greedy. How does level-5 Pirate divide the treasure?

Hint

Here n=5, think in terms of what happens if n=1,2,3...

Answer

Division is: 98,0,1,0,1

Solution

To understand the answer, we need to reduce this problem to only 2 pirates. So what happens if there are only 2 pirates. Pirate 2 can easily propose that he gets all the 100 gold coins. Since he constitutes 50% of the pirates, the proposal has to be accepted leaving Pirate 1 with nothing.

Now let's look at 3 pirates situation, Pirate 3 knows that if his proposal does not get accepted, then pirate 2 will get all the gold and pirate 1 will get nothing. So he decides to bribe pirate 1 with one gold coin. Pirate 1 knows that one gold coin is better than nothing so he has to back pirate 3. Pirate 3 proposes {pirate 1, pirate 2, pirate 3} {1, 0, 99}. Since pirate 1 and 3 will vote for it, it will be accepted.

If there are 4 pirates, pirate 4 needs to get one more pirate to vote for his proposal. Pirate 4 realizes that if he dies, pirate 2 will get nothing (according to the proposal with 3 pirates) so he can easily bribe pirate 2 with one gold coin to get his vote. So the distribution will be {0, 1, 0, 99}.

Smart right? Now can you figure out the distribution with 5 pirates? Let's see. Pirate 5 needs 2 votes and he knows that if he dies, pirate 1 and 3 will get nothing. He can easily bribe pirates 1 and 3 with one gold coin each to get their vote. In the end, he proposes {1, 0, 1, 0, 98}. This proposal will get accepted and provide the maximum amount of gold to pirate 5.

PS:This puzzle gives a basic idea of game theory and dynamic programming.

Now let's look at 3 pirates situation, Pirate 3 knows that if his proposal does not get accepted, then pirate 2 will get all the gold and pirate 1 will get nothing. So he decides to bribe pirate 1 with one gold coin. Pirate 1 knows that one gold coin is better than nothing so he has to back pirate 3. Pirate 3 proposes {pirate 1, pirate 2, pirate 3} {1, 0, 99}. Since pirate 1 and 3 will vote for it, it will be accepted.

If there are 4 pirates, pirate 4 needs to get one more pirate to vote for his proposal. Pirate 4 realizes that if he dies, pirate 2 will get nothing (according to the proposal with 3 pirates) so he can easily bribe pirate 2 with one gold coin to get his vote. So the distribution will be {0, 1, 0, 99}.

Smart right? Now can you figure out the distribution with 5 pirates? Let's see. Pirate 5 needs 2 votes and he knows that if he dies, pirate 1 and 3 will get nothing. He can easily bribe pirates 1 and 3 with one gold coin each to get their vote. In the end, he proposes {1, 0, 1, 0, 98}. This proposal will get accepted and provide the maximum amount of gold to pirate 5.

PS:This puzzle gives a basic idea of game theory and dynamic programming.

Source: Technical Interview

Enable Like and Comment Easy | Strategy |

Hundred tigers and one sheep are put on a magic island that only has grass. Tigers can live on grass, but they want to eat sheep. If a Tiger bites the Sheep then it will become a sheep itself. If 2 tigers attack a sheep, only the first tiger to bite converts into a sheep. Tigers don’t mind being a sheep, but they have a risk of getting eaten by another tiger. All tigers are intelligent and want to survive. Will the sheep survive?

Hint

Instead of 100, think of 1 or 2 tiger's case.

Answer

Sheep survives!

Solution

If there is 1 tiger, then it will eat the sheep because he does not need to worry about being eaten. Sheep will not survive.

If there are 2 tigers, both of them knows that if one eats the Sheep, the other tiger will eat him. So, the sheep will survive.

If there are 3 tigers, then they each of them knows that if one tiger eats up the sheep, then Iceland will be left with 1 sheep and 2 tigers and as shown in the previous case, the sheep will survive. Hence each tiger will try to eat up the sheep. The sheep will not survive.

If there are 4 tigers, then the sheep will survive.

And so on….

So, If there are even number of tigers the sheep will survive, else it will die. Hence, if there are 100 tigers the sheep will survive.

If there are 2 tigers, both of them knows that if one eats the Sheep, the other tiger will eat him. So, the sheep will survive.

If there are 3 tigers, then they each of them knows that if one tiger eats up the sheep, then Iceland will be left with 1 sheep and 2 tigers and as shown in the previous case, the sheep will survive. Hence each tiger will try to eat up the sheep. The sheep will not survive.

If there are 4 tigers, then the sheep will survive.

And so on….

So, If there are even number of tigers the sheep will survive, else it will die. Hence, if there are 100 tigers the sheep will survive.

Source: Common

Enable Like and Comment Easy | Strategy |

A duck is swimming at the center of a circular lake. A fox is waiting at the shore, not able to swim, willing to eat the duck. It may move around the whole lake with a speed four times faster than the duck can swim. As soon as duck reaches the surface, it can fly, but not within the pond. Can the duck always reach the shore without being eaten by the fox?

Hint

Fox is chasing duck brainlessly. If duck's angular velocity is (somehow) more than fox, duck may actually create some sort of phase lag.

Solution

At radius of slightly less than r/4 the duck can swim in circles, forcing the fox to run around. once the duck is at a phase of pi from fox it starts swimming towards the shore and flies.

Source: Technical Interview

Enable Like and Comment Easy | Strategy |

100 prisoners are lined up and assigned a random hat, either red or blue. There can be any number of red hats. Each prisoner can see the hats in front of him but not behind. Starting with the prisoner in the back of the line and moving forward, they must each, in turn, say only one word which must be "red" or "blue". If the word matches their hat color they are released, if not, they are killed on the spot. They can hear each others answers, no matter how far they are on the line. A friendly guard warns them of this test one hour beforehand and tells them that they can formulate a plan where by following the stated rules, 99 of the 100 prisoners will definitely survive, and 1 has a 50/50 chance of survival. What is the plan to achieve the goal?

Hint

Red and blue can be thought of as 0 and 1. Think of modulo 2 sums now.

Solution

Number prisoners from 100 to 1, with 100 being the last person in line, being able to see 99 other hats. Prisoners agree that if the number of red hats that the 100th person can see is even, then he will say “red”. if they add up to an odd number, he will say “blue”. this way number 99 can look ahead and count the red hats. if they add up to an even number and number 100 said “red”, then 99 must be wearing a blue hat. if they add up to an even number and number 100 said “blue”, signalling an odd number of red hats, number 99 must also be wearing a red hat. number 98 knows that 99 said the correct hat, and so uses that information along with the 97 hats in front to figure out what color hat is on 98’s head.

Easy | Strategy |

A traveler wants to go to the mystic. He meets a pair of twins at a fork in the road: one path leads to the jungle, the other to the mystic. One of the twins always says the truth, the other always lies. What yes/no question should he ask one of the twins to determine the path that goes to the mystic?

Hint

Ask one about the other!

Solution

The two-brother problem may be solved in two different ways:

The traveler may ask, "Would your brother agree that the road on the left leads to the mystic?" The answer is guaranteed to be 'Yes' if and only if the road on the right leads to the mystic.

The traveler may ask, "If I were to ask you whether the road on the left leads to the mystic, would you say 'Yes'?" The 'if i were to ask you' construct makes both twins tell the truth. So if the answer is 'Yes', the road on the left indeed leads to the mystic, otherwise the road on the right does so.

(solution was taken from gurmeet's blog)

The traveler may ask, "Would your brother agree that the road on the left leads to the mystic?" The answer is guaranteed to be 'Yes' if and only if the road on the right leads to the mystic.

The traveler may ask, "If I were to ask you whether the road on the left leads to the mystic, would you say 'Yes'?" The 'if i were to ask you' construct makes both twins tell the truth. So if the answer is 'Yes', the road on the left indeed leads to the mystic, otherwise the road on the right does so.

(solution was taken from gurmeet's blog)

Source: Common

Enable Like and Comment Latest solved Puzzles

Color Switches Weird Sequences Intersecting Pillars Consecutive sums Scaling a Square Difficulty Level

© BRAINSTELLAR |