Puzzles and Brain Teasers

Puzzles and Brain Teasers

Pirates

You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.)

Ans: 98 coins with top pirate

This is a game theory problem which involves some reasoning.
Lets start to the solution as if there are only 2 pirates. In this case, the top-ranked pirate (Pirate B) would get 100 gold coins, and Pirate A wouldn't get any, because Pirate A has no way to vote down the plan.

Let's work backwards from there. Clearly, Pirate A doesn't want it to come down to just two people. So consider if there were three pirates. Then, Pirate A would accept even just one coin to avoid letting things get down to two people. Thus, if there were three pirates involved, Pirate C should offer Pirate A a single coin; Pirate A would agree because one coin is better than zero. Pirate B could not overrule this plan.

Lets say there are 4 pirates, Pirate B would accept even just one coin to avoid letting things get down to three pirates; if it got down to three, as we have shown above, Pirate B would get nothing. Thus, Pirate D could offer to keep 99 coins and pay Pirate B a single coin; Pirate A and Pirate C would get nothing, but they don't have enough votes to override the plan.

Coming to actual five pirates case , Pirate A and Pirate C are anxious to avoid letting things get down to four pirates, because then they'd get nothing. So if Pirate E offered Pirate A and Pirate C a single coin each, then they'd vote in favor of the plan, since one coin would be better than nothing.
So Pirate E keeps 98 coins for himself.


Generalized answer is
If there are odd number of pirates then
the number of coins with top pirate = total number of coins - number of odd numbers below the number.
else
the number of coins with top pirate = total number of coins - number of even numbers below the number.

Proff for above formulae can be established by following
In case of 6 pirates: Pirate F would have to offer a coin to Pirates B and D to satisfy everyone's self-interests.
In case of 7 pirates : Pirate G would have to offer a coin to Pirates A, C, and E. 

Rope bridges

Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it's only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes?

Solution

To get everyone across in 17 minutes, we need the two slowest people to travel across together; otherwise we're wasting too much time. Once we
get them across, how do we not make one of them walk back with the flashlight? Just have one of the faster people already there waiting to


sprint the flashlight back across.
person A: 1 minute
person B: 2 minutes
person C: 5 minutes
person D:10 minutes

1. A & B cross. total time: 2 minutes.

C |--------------------------| A
D |                                       | B
   |--------------------------| flashlight

2. B comes back. total time: 4 minutes.

C |--------------------------| A
D |                                       |
B |--------------------------|
flashlight

3. C & D cross. total time: 14 minutes.

B |--------------------------| A
   |                                        | C
   |--------------------------| D
                                             flashlight

4. A comes back. total time: 15 minutes.

A |--------------------------| C
B |                                          | D
   |--------------------------|
flashlight

5. A & B cross. total time: 17 minutes.

|--------------------------| A
|                                             | B
|--------------------------| C D
                                               flashlight
 
Another valid solution is to have A bring the flashlight back in step 2.

Measuring water

If you had an infinite supply of water and a 5 gallon and 3 gallon bucket, how would you measure exactly 4 gallons?

Answer:

                        5          3

Fill up 3            0          3

Tip into 5          3          0

Fill up 3             3          3

3 to 5                5          1

Tip out 5           0          1

3 to 5                1          0

Fill up 3            1    +    3 = 4

You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighings?

Break the balls into the following groups: (1,2,3),(4,5,6),(7,8)

Step 1. Weigh (1,2,3) against (4,5,6)
Two possible outcomes:
The two groups are equally heavy. (Case A)
One of these groups is heavier than the other. (Case B)

Case A --> Weigh 7 against 8. Now you have identified the heavier ball in 2 weighing.
Case B --> Take the heavier group (assume it to be (1,2,3)), take any two balls and weigh them against each other. Either one of these is heavier else the third ball is.

How many golf balls can fit into a school bus?

Interesting question!

I am assuming the values of the size of the bus and golf ball here.

Assuming the size of the bus to be 35 ft X 7.5 ft X 6.5 ft.

The volume of the bus = 1706.25 cubic foot.

1 cubic foot = 1728 cubic inches

Therefore, 1706.25 * 1728 = 2948400 cubic inches.

Radius of golf ball = 0.85 inches.
Volume of golf ball = 4/3 * pi * (radius^3) = 2.5 cubic inches.

The number of golf balls that can be accommodated in the bus : 2948400/2.5  = 1179360.

Note: Assuming 25% of the space is occupied by the seats in the bus, that leaves us 75% of space to accommodate the balls.


Using only a four-minute hourglass and a seven-minute hourglass, measure exactly nine minutes—without the process taking longer than nine minutes.

A. Start both hourglasses at 0 minutes. Flip over the four-minute glass when it runs out (at 4:00); ditto for the seven-minute glass (at 7:00). When the four-minute glass runs out the second time (at 8:00), the seven-minute glass will then have one minute of sand in its lower bulb. Flip the seven-minute glass over again and let the minute of sand run back. When the last grain falls, that will be nine minutes.

There are 25 horses and only 5 tracks. No of matches to find top 3 horses.

There are 25 horses and only 5 tracks. So only 5 horses can run the race at a time. How many minimum no of races should be conducted to find the 3 best horses?
Sol: The answer is 7.
Round 1: Take 5 horses at a time. 5 winners of each race will go to round2.
Round 2: Winner of this will be top most horse.(call it W1)
Round 3: Final race comprises of following 5 horses.
h1: 2nd horse of round2
h2:3rd horse of round2
h3:2nd horse of W1's group during round 1
h4:3rd horse of W1's group during round1
h5:2nd horse of h1's group during round1 

Two tribes one always tells true other false....

There were 2 tribes living on an island. The east tribal people always tell a lie. The west tribal people always tell the truth. Alan and Bryan came from the same tribe. However, we do not know which tribe they came from. When they were asked the marital status, Alan said: “Both of us are married.” But Bryan said: “I am not married”. Are they really married?


Ans:

Both are from same tribe. It means either both of them will lie or both will tell true. If we look at the statements both of them contradicts about Bryan's marital status. It means one of them is not telling truth, as they are from same tribe it concludes that they are from east tribe. It means Bryan is married and Alan's status is unclear. 

Distance between trains

One train runs from A to B at 105 miles per hour; the other runs from B to A at 85 miles per hour. How far apart were the two trains 30 minutes prior to their crossing?

Solution:

Two trains are 95 miles apart 1/2 Hr before they crossed each other

Relative Speed of the trains = 85+105 = 190MPH

One hour before they crossed, they would have been 190 miles apart.

Distance between the trains 1/2 hr before they crossed would be 190/2 = 95miles

Two Egg problem:

• You are given 2 eggs.
• You have access to a 100-storey building.
• Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.
• You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.
• Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process 

For an optimal solution, if the first segment is of size N, then the second has to be of size N-1, and so on (because when you start testing the second segment, you've already dropped the egg once for the first segment).

So you need to solve n+(n-1)+(n-2)+...+1<=100, from where (n)(n+1)/2<=100 (this function transform is done with arithmetic series aka sum of an arithmetic sequence), now if you solve for n (wolframalpha: Reduce[Floor[n + n^2] >= 200, n] ) you get 14. Now you know that the first floor where you need to make the drop is 14th floor, next will be (14+14-1)th floor and whole sequence:

14; 27; 39; 50; 60; 69; 77; 84; 90; 95; 99; 100 

If you break the first egg, you go back to the last one and linearly check all options until you break the second egg, when you do, you got your answer. There is no magic.

References:

http://techbrother.blogspot.co.uk/2007/12/pirate-gold-coins-division-problem.html
http://thebrainteasers.com/
http://courses.csail.mit.edu/iap/interview/Hacking_a_Google_Interview_Practice_Questions_Person_B.pdf
http://googlesystem.blogspot.co.uk/2006/08/tough-questions-from-google-job.html
http://www.wired.co.uk/magazine/archive/2012/05/start/want-to-work-at-google