How many steps are required to break an m x n bar of chocolate into 1 x 1 pieces? We may break an existing piece of chocolate horizontally or vertically. Stacking of two or more pieces is not allowed.
Solution:
Consider a 3x4 bar chocolate.
You will first require 2 horizontal breaks -creating 3 -1x4 bars => Count = 2
You will require 3 vertical breaks on the 1st 1x4 bar => Count = 5
You will require 3 vertical breaks on the 2nd 1x4 bar => Count = 8
You will require 3 vertical breaks on the 3rd 1x4 bar => Count = 11
So for a 3x4 bar chocolate you will require 11 breaks = (3*4) -1
In general you will require mn-1 breaks
Thursday, May 13, 2010
Cards - 1
A blind man is handed a deck of 52 cards and told that exactly 10 of these cards are facing up. How can he divide the cards into two piles, not necessarily of equal size, with each pile having the same number of cards facing up?
Solution:
Blindman makes 2 piles, P1 - 42 cards and P2 -10, He then flips all the cards in P2.
Example : If there are 6 cards facing up in P1 and 4 in P2 after the split. When he flips all the cards in P2 he will have 6 cards facing up and 4 cards facing down - Hence both the piles have the same number of cards facing up.
Solution:
Blindman makes 2 piles, P1 - 42 cards and P2 -10, He then flips all the cards in P2.
Example : If there are 6 cards facing up in P1 and 4 in P2 after the split. When he flips all the cards in P2 he will have 6 cards facing up and 4 cards facing down - Hence both the piles have the same number of cards facing up.
Marbles -1
You have 50 red marbles, 50 blue marbles and 2 jars. One of the jars is chosen at random and then one marble will be chosen from that jar at random. How would you maximize the chance of drawing a red marble? What is the probability of doing so? All 100 marbles should be placed in the jars.
Solution:
Put a single red marble in one jar and the rest of the marbles in the other jar. This way, you are guaranteed at least a 50% chance of getting a red marble (since one marble picked at random, doesn’t leave any room for choice). Now that you have 49 red marbles left in the other jar, you have a nearly even chance of picking a red marble (49 out of 99).
So let’s calculate the total probability.
Solution:
Put a single red marble in one jar and the rest of the marbles in the other jar. This way, you are guaranteed at least a 50% chance of getting a red marble (since one marble picked at random, doesn’t leave any room for choice). Now that you have 49 red marbles left in the other jar, you have a nearly even chance of picking a red marble (49 out of 99).
So let’s calculate the total probability.
P( red marble ) = P( Jar 1 ) * P( red marble in Jar 1 ) + P( Jar 2 ) * P( red marble in Jar 2 )
P( red marble ) = 0.5 * 1 + 0.5 * 49/99
P( red marble ) = 0.7474
Thus, we end up with ~75% chance of picking a red marble.
P( red marble ) = 0.5 * 1 + 0.5 * 49/99
P( red marble ) = 0.7474
Saturday, May 8, 2010
Monkey and Coconuts
Ten people land on a deserted island. There they find lots of coconuts and a monkey. During their first day they gather coconuts and put them all in a community pile. After working all day they decide to sleep and divide them into ten equal piles the next morning.
That night one castaway wakes up hungry and decides to take his share early. After dividing up the coconuts he finds he is one coconut short of ten equal piles. He also notices the monkey holding one more coconut. So he tries to take the monkey's coconut to have a total evenly divisible by 10. However when he tries to take it the monkey conks him on the head with it and kills him.
Later another castaway wakes up hungry and decides to take his share early. On the way to the coconuts he finds the body of the first castaway, which pleases him because he will now be entitled to 1/9 of the total pile. After dividing them up into nine piles he is again one coconut short and tries to take the monkey's slightly bloodied coconut. The monkey conks the second man on the head and kills him.
One by one each of the remaining castaways goes through the same process, until the 10th person to wake up gets the entire pile for himself. What is the smallest number of possible coconuts in the pile, not counting the monkeys?
Solution:
2519 The solution for the answer is the LCM (Lowest Common Multiple) of 10,9,8,7,6,5,4,3,2,1 -1. LCM would give the least number which is divisible by all of these number and subtracting one would give us the number of coconuts which were initially there.Socks
Cathy has six pairs of black socks and six pairs of white socks in her drawer.
In complete darkness, and without looking, how many socks must she take from the drawer in order to be sure to get a pair that match?
Solution:
3
Socks do not come in in left and right, so any black will pair with any other black and any white will pair with any other white. If you have three socks and they are either colored black or white, then you will have at least two socks of the same color, giving you one matching pair.
3 and 5 Gallons
You have a three gallon and a five gallon measuring device. You wish to measure out four gallons of water, Assume there is infinite supply of water.
Solution:
Fill the five gallon container. Pour all but two gallons into the three gallon container. Empty the three gallon container. Put the two remaining gallons from the five gallon container into the three gallon container. Fill the five gallon container one more time. Pour one gallon from the five gallon container by filling the three gallon container. Now the five gallon container contains four gallons.
Solution:
Fill the five gallon container. Pour all but two gallons into the three gallon container. Empty the three gallon container. Put the two remaining gallons from the five gallon container into the three gallon container. Fill the five gallon container one more time. Pour one gallon from the five gallon container by filling the three gallon container. Now the five gallon container contains four gallons.
Ants
Three ants are sitting at the three corners of an equilateral triangle. Each ant starts randomly picks a direction and starts to move along the edge of the triangle. What is the probability that none of the ants collide?
Solution:
lets assume all three ants are looking towards the center. They will not collide if all of them are moving towards left or towards right. Even if one of the ants starts to move to the other direction there will be a collision. There are the following eight optio
RRR
LLL
RLL
RLR
RRL
LRL
LRR
LLR
The ants will not collide in case of LLL and RRR so the probability of not colliding is:
2/8 = 0.25
The probability of ants colliding is 6/8=0.75
Solution:
lets assume all three ants are looking towards the center. They will not collide if all of them are moving towards left or towards right. Even if one of the ants starts to move to the other direction there will be a collision. There are the following eight optio
RRR
LLL
RLL
RLR
RRL
LRL
LRR
LLR
The ants will not collide in case of LLL and RRR so the probability of not colliding is:
2/8 = 0.25
The probability of ants colliding is 6/8=0.75
Friday, May 7, 2010
TV Puzzle
Imagine you're on a game show on tv, and you're offered the choice of three prizes behind closed doors. One of the prizes is very valuable (usually a car), and behind the other two doors are worthless prizes (often goats). You don't know what's behind which door, but the game show host does. You choose a door (hoping to get the car). The host, instead of opening your selected door, raises the tension by opening one of the other two doors instead, behind which he knows there is a goat. Then he offers you the choice - do you stick with your previously-selected door, or do you switch to the other, still closed, door?
Solution:
You raise your chances of getting the car by switching. The chance of the car being behind your original choice is 1 in 3. Now that one of the other two doors has been removed, the chance that the car is behind the other closed door is now 2 in 3, which is over twice as likely. It's extremely counter-intuitive because it's common to think that the chances are now 50:50, but they're not. Another way to look at this: if you chose a goat, you should switch, and if you chose the car, you should stick. But in the first round, you probably chose a goat (which was twice as likely as choosing the car). So you will probably gain by switching doors, and probably lose by sticking with your original choice.
Solution:
You raise your chances of getting the car by switching. The chance of the car being behind your original choice is 1 in 3. Now that one of the other two doors has been removed, the chance that the car is behind the other closed door is now 2 in 3, which is over twice as likely. It's extremely counter-intuitive because it's common to think that the chances are now 50:50, but they're not. Another way to look at this: if you chose a goat, you should switch, and if you chose the car, you should stick. But in the first round, you probably chose a goat (which was twice as likely as choosing the car). So you will probably gain by switching doors, and probably lose by sticking with your original choice.
Chess Squares
How many squares are on a chess board?
Solution:
A 1×1 square can be placed on the chess board in 8 horizontal and 8 vertical positions, thus making a total of 8 x 8 = 64 squares. Let’s consider a 2×2 square. There are 7 horizontal positions and 7 vertical positions in which a 2×2 square can be placed. Why? Because picking 2 adjacent squares from a total of 8 squares on a side can only be done in 7 ways. So we have 7 x 7 = 49 2×2 squares. Similarly, for the 3×3 squares, we have 6 x 6 = 36 possible squares. So here’s a break down.
Solution:
A 1×1 square can be placed on the chess board in 8 horizontal and 8 vertical positions, thus making a total of 8 x 8 = 64 squares. Let’s consider a 2×2 square. There are 7 horizontal positions and 7 vertical positions in which a 2×2 square can be placed. Why? Because picking 2 adjacent squares from a total of 8 squares on a side can only be done in 7 ways. So we have 7 x 7 = 49 2×2 squares. Similarly, for the 3×3 squares, we have 6 x 6 = 36 possible squares. So here’s a break down.
1×1 8 x 8 = 64 squares
2×2 7 x 7 = 49 squares
3×3 6 x 6 = 36 squares
4×4 5 x 5 = 25 squares
5×5 4 x 4 = 16 squares
6×6 3 x 3 = 9 squares
7×7 2 x 2 = 4 squares
2×2 7 x 7 = 49 squares
3×3 6 x 6 = 36 squares
4×4 5 x 5 = 25 squares
5×5 4 x 4 = 16 squares
6×6 3 x 3 = 9 squares
7×7 2 x 2 = 4 squares
8×8 1×1 = 1 square
Total = 64 + 49 + 36 + 25 + 16 + 9 + 4 + 1 = 204 squares
8 ball Problem
You are given 8 identical looking balls. One of them is heavier than the rest of the 7 (all the others weigh exactly the same). You a provided with a simple mechanical balance and you are restricted to only 2 uses. Find the heavier ball.
Solution:
Weigh {1,2,3} on the left and {4,5,6} on the right. There are three scenarios which can arise from this. If the left side is heavier, then we know that one of 1, 2 or 3 is the heavier ball. Weigh {1} on the left and {2} on the right. By doing this, we will know if 1 or 2 is heavier. If they balance out, then 3 is the heavier one.
If the right side is heavier, then we know that either 4, 5 or 6 is the heavier ball. Weigh {4} on the left and {5} on the right. By doing this we will know if 4 or 5 is heavier. If they balance out, then 6 is the heavier one.
If {1,2,3} and {4,5,6} balance out, then we know either 7 or 8 is the heavier one. Weigh both of them to find out which one is heavier.
Solution:
Weigh {1,2,3} on the left and {4,5,6} on the right. There are three scenarios which can arise from this. If the left side is heavier, then we know that one of 1, 2 or 3 is the heavier ball. Weigh {1} on the left and {2} on the right. By doing this, we will know if 1 or 2 is heavier. If they balance out, then 3 is the heavier one.
If the right side is heavier, then we know that either 4, 5 or 6 is the heavier ball. Weigh {4} on the left and {5} on the right. By doing this we will know if 4 or 5 is heavier. If they balance out, then 6 is the heavier one.
If {1,2,3} and {4,5,6} balance out, then we know either 7 or 8 is the heavier one. Weigh both of them to find out which one is heavier.
5 Pirates and 100 Gold Coins
Five pirates discover a chest containing 100 gold coins. They decide to sit down and devise a distribution strategy. The pirates are ranked based on their experience (Pirate 1 to Pirate 5, where Pirate 5 is the most experienced). The most experienced pirate gets to propose a plan and then all the pirates vote on it. If at least half of the pirates agree on the plan, the gold is split according to the proposal. If not, the most experienced pirate is thrown off the ship and this process continues with the remaining pirates until a proposal is accepted. The first priority of the pirates is to stay alive and second to maximize the gold they get. Pirate 5 devises a plan which he knows will be accepted for sure and will maximize his gold. What is his plan?
Solution:
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}.
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.
Solution:
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}.
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.
GoldBar
You’ve got someone working for you for seven days and a gold bar to pay them. You must pay the worker for their work at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker? (Assuming equal amount of work is done during each day thus requiring equal amount of pay for each day)
Solution:
Make two cuts on the gold bar such that you have the following sizes of bars. 1/7, 2/7 and 4/7. For convenience sake, I would just refer to the bars as 1, 2 and 4.
At the end of Day 1: Give Bar 1 (You- 2 and 4, Worker- 1)
At the end of Day 2: Give Bar 2, Take back Bar 1 (You- 1 and 4, Worker- 2)
At the end of Day 3: Give Bar 1 (You- 4, Worker- 1 and 2)
At the end of Day 4: Give Bar 4, Take back Bar 1 and Bar 2 (You- 1 and 2, Worker- 4)
At the end of Day 5: Give Bar 1 (You- 2, Worker- 1 and 4)
At the end of Day 6: Give Bar 2, Take back Bar 1 (You- 1, Worker- 2 and 4)
At the end of Day 7: Give Bar 1 (You- Empty, Worker- 1, 2 and 4)
Solution:
Make two cuts on the gold bar such that you have the following sizes of bars. 1/7, 2/7 and 4/7. For convenience sake, I would just refer to the bars as 1, 2 and 4.
At the end of Day 1: Give Bar 1 (You- 2 and 4, Worker- 1)
At the end of Day 2: Give Bar 2, Take back Bar 1 (You- 1 and 4, Worker- 2)
At the end of Day 3: Give Bar 1 (You- 4, Worker- 1 and 2)
At the end of Day 4: Give Bar 4, Take back Bar 1 and Bar 2 (You- 1 and 2, Worker- 4)
At the end of Day 5: Give Bar 1 (You- 2, Worker- 1 and 4)
At the end of Day 6: Give Bar 2, Take back Bar 1 (You- 1, Worker- 2 and 4)
At the end of Day 7: Give Bar 1 (You- Empty, Worker- 1, 2 and 4)
Burning Sticks
You have two sticks and matchbox. Each stick takes exactly an hour to burn from one end to the other. The sticks are not identical and do not burn at a constant rate. As a result, two equal lengths of the stick would not necessarily burn in the same amount of time. How would you measure exactly 45 minutes by burning these sticks?
Solution :
The answer is really simple. Since the sticks do not burn at a constant rate, we can not use the length of the stick as any sort of measurement of time. If we light a stick, it takes 60 minutes to burn completely. What if we light the stick from both sides? It will take exactly half the original time, i.e. 30 minutes to burn completely.
0 minutes – Light stick 1 on both sides and stick 2 on one side.
30 minutes – Stick 1 will be burnt out. Light the other end of stick 2.
45 minutes – Stick 2 will be burnt out.
Solution :
The answer is really simple. Since the sticks do not burn at a constant rate, we can not use the length of the stick as any sort of measurement of time. If we light a stick, it takes 60 minutes to burn completely. What if we light the stick from both sides? It will take exactly half the original time, i.e. 30 minutes to burn completely.
0 minutes – Light stick 1 on both sides and stick 2 on one side.
30 minutes – Stick 1 will be burnt out. Light the other end of stick 2.
45 minutes – Stick 2 will be burnt out.
Subscribe to:
Posts (Atom)
