Quiz Summary
0 of 3 questions completed
Questions:
- 1
- 2
- 3
Information
You have already completed the quiz before. Hence you can not start it again.
Quiz is loading…
You must sign in or sign up to start the quiz.
You must first complete the following:
Results
Time has elapsed
Categories
- 1
- 2
- 3
- Answered
- Review
- Two glass balls
- The king’s party
- Pirates dividing a treasure
- Summation
- Out of the box
- Simplification
- Question 1 of 3
1. Question
Two glass balls
You have two glass balls and you are standing in a 100-story building. If you throw a glass ball out of the window, it will not break if the floor number is less than X. However, it will always break if the floor number is equal or greater than X. You want to determine which floor has number X. What is the minimum number of drops for the worst case scenario to achieve your goal?
Hint
Design a strategy in which it is possible to use the summation rule.
Answer
Intuitively, you want the balls to cover at least all 100 floors. First, we have to come up with a strategy. Suppose you find the number
throws. A strategy could be to start at the -th floor. Then, we have the following two scenarios:
1. The first ball breaks. Since you don’t want to take the risk of breaking the second ball (because in that case you won’t find the floor number
), you go to the first floor and you go up one level every time until the ball breaks.
2. The first ball does not break. You go up to floor number
. Here, we have the following two scenarios:
2.1 In case the ball breaks here, you go to floor
and you go up one level every time until the ball breaks.
2.2 In case the ball does not break, you go up to level
.Continuing this strategy, the number of total throws will never result in more than
throws. To find , we need to solve the following equation: 
or 
. Solving this equation results in 
. - Question 2 of 3
2. Question
The king’s party
Someone breaks into the wine cellar of a king, where he stores 1000 bottles of wine. This person proceeds to poison one of the 1000 bottles, but gets away too quickly for the king’s guard. Nobody knows which one he poisoned. The king needs the remaining 999 safe bottles for his party in four weeks. The king has ten prisoners who deserve execution. The poison takes just less than four weeks to take effect. Any amount of the poisoned wine will kill whoever drinks it. How can he figure out which bottle was poisoned in time for the party?
Hint
Think about binary strings.
Answer
Since every prisoner can end up dead or alive, there are 2^10 = 1024 possible outcomes. Since 1024 > 1000, it’s actually possible to use an approach using binary strings. The king assigns each servant a number from 1 to 10. The king assigns each bottle a number from 0 to 999. When he labels them, he writes the number on the bottle in binary with ten digits, like this: 0: 000000000 1: 000000001 2: 000000010 3: 000000011 4: 000000100, … 999: 1111100111. The strategy is simple: the king assigned the prisioners a number from 1 to 10, indicating the position of the number in the binary string. If the string has a number one on the – let’s say – fifth- and sixth position, then the prisoners with number five and six have to drink the wine. After less than four weeks, suppose only prisoner number five and six die. This means the binary representation of poisoned wine has a ‘1’ at position five and six, and the rest are all zeros. Convert this binary number to a decimal and that gives you the number of the poisoned wine.
- Question 3 of 3
3. Question
Pirates dividing a treasure
Five pirates need to divide 100 coins. The pirates have a hierarchy, from level 1 to level 5. The pirate with the highest seniority has level 5 and the pirate with the lowest seniority has level 1. The pirate with the highest seniority proposes a division plan and all the pirates vote on it. If at least 50% of the pirates agree on the plan, the coins will be divided according to the proposal. If not, the highest senior pirate is kicked from the ship, and the next senior pirate may propose a plan. This process continues until a proposal is accepted. All pirates are extremely smart and extremely greedy. How does pirate #5 divide the treasure in order to survive with the maximum amount of coins?
Hint
Reduce the problem to two pirates, does pirate 2 need the vote of pirate 1? Gradually increase the problem from this point.
Answer
To understand the answer, we need to reduce this problem to only two pirates. Pirate #2 embodies 50% of the votes in this case, so he can easily propose that he gets all the 100 coins. Now increase the problem to three pirates. Pirate #3 knows that if his proposal does not get accepted, that pirate #2 will get all the coins and pirate #1 will be left with nothing. Therefore, he decides to bribe pirate #1 with one coin. Pirate #1 knows that one gold coin is better than nothing, so he has to vote for pirate #3. Since pirate #1 and #3 will vote for it, it will be accepted. If there are four pirates, pirate #4 needs to get one more pirate to vote for his proposal. Pirate #4 realises that if he dies, pirate #2 will be left with nothing (according to the proposal with 3 pirates) so he can easily bribe pirate #2 with one coin to get his vote. With two votes and four pirates, the proposal will be accepted. Now increase the problem to five pirates. Pirate #5 needs two 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 coin each to get their vote. In the end, he proposes, from pirate #5 – pirate #1: {98, 0, 1, 0, 1}. This proposal will get accepted and will provide the maximum amount of gold to pirate #5.
or 
. Solving this equation results in 
.