1) Greetings!!!
From this week onwards we are also starting a series of puzzles for you to jog your mind...
Level 1: There are 24 identical marbles. One of them is heavier than the remaining of the marbles. You have a beam balance with you. The minimum number of weigh-ments required to find out the heavier marble is …………..? Explain!
2) Level 2: There are 10 machines which should produce 10kg objects each. However one of them is faulty and it is now producing 9 kg objects yet they are identical to the 10kg objects. You have one weighing machine in which you can measure only once. How do you find the faulty machine?
3) Level 3: Three intelligent men are asked to stand in a row in the same direction. Each of them is shown a basket which contained 3 red hats and 2 black hats. A person could not see the color of his own hat. The person in the front could not see any other person’s hat. The middle person could see the hat of the person ahead of him. The last person could see the hat of both the persons ahead of him. The last person in the queue was then asked.. Can you determine the color of the hat you are wearing? He replied saying no. The same question was then put the same person. He also replied saying no. Then the same question was put the first person in the queue. He replied saying yes. What was the color of his hat and how did he determine it? Explain. (Hint : They could hear other’s reply. Moreover the three people are strangers but intelligent).
4) Level 4: There is a 100 storey building. You have two eggs with you. There is a threshold floor beyond which the egg breaks. For eg: If the threshold floor is 51, the egg doesn’t break if you throw it from floors 50 downwards. It breaks from 51st floor onwards. How many tries would you take to determine the threshold floor of that building. The method should work for any threshold floor. Eg: If I throw the first egg from 50th floor and it breaks, then I’ll throw the second egg from 1st floor onwards to determine the threshold floor. So my worst case scenario is 49 tries to determine the threshold floor. Your objective is to minimize the number of tries to determine the threshold floor. (Hint: If an egg does not break after throwing it from a particular floor, then you can use that egg again to throw it from a different floor. The egg does not become weaker with the number of throws. It remains as strong as it was initially.)
5) Level 5: A business-man wants to organize a party next month. He has 1000 wine bottles with him. However one of them is poisonous. He has rats to test the wine bottles on. However, the poison takes one month to react, which means exactly a day before the party. You need to tell the minimum number of rats that the business-man would require to successfully find out the poisonous bottle. (Hint : Think binary!!!!)
1) 4 weighings. take 12+12...then 6+6...3+3...then final 1 weighing.
ReplyDelete2) take 1 object of 1st machine...2 of 2nd..3 of 3rd n so on....total will be n(n+1)/2. this will tell u which machine is faulty.
ReplyDelete3)Red
Cos last could only tel his own colour had the 2 persons in front be wearing 2 black. It means persons in front 2 rows are wearing either red and red or black and red.
Now even 2nd couldnt tel therefore it means the first person is wearing red.
4) 14 tries. n(n+1)/2=100....here n=14 will give u the number of tries.
ReplyDeleteLevel 1:
ReplyDelete3 weighments are required.
make groups of 8,8,8. Put any 2 on the beam balance. the one which tilts has the heavier marble. In case the beam is balanced
this means the remaining one group has the heavier marble.
Now from that 8, make group of 3,3,2,
Put 3,3 on one scale. repeat the previous step again
Then in step 3 u would be able to find the heavier marble.
Level 2:
Take 1,2,3,4,.....10 objects from machines 1,2,3.. etc and put them all on the weighing machine. In case of all the objects
being of same weight, the weighing machine should show 550 kg(sum of AP)
suppose machine 2nd is faulty then u will get reading on weighing scale as 548kg, in case of machine 4th being faulty, u
will get 546 kg and so on.
Level 3:
Answer is red
If last person said no this means, 1st and middle person has either both red hats or one red and one black hat.
Now since middle person has also said no, this means 1st person is wearing red hat, coz had 1st person wearing a black
hat, this would mean middle person is wearing a red hat which is not the case. Hence 1st person is wearing red hat.
First of All.. Congrats for bringing this up. It is yet another great initiative. Something, I will definitely look forward to. Now let’s get to the real stuff!!
ReplyDeleteLevel 1: Minimum number of steps required is 3.
Step 1: Divide 24 marbles in group of 6. So, we have 3 sets of 6 marbles each.
• Weigh the first two sets
o This will give the set (6 marbles) that contains the heavier marble. (If the first 2 sets weigh equal, then the 3rd set contains the heavier marble.)
Step2: Divide the set of 6 marble (obtained from step 1) again in 3 sets of 2 marbles each.
• Weigh the first two sets
This will give the set (2 marbles) that contains the heavier marble. (If the first 2 sets weigh equal, then the 3rd set contains the heavier marble.)
Step3: Weigh the 2 marbles obtained in step 2. We can get the heavier marble.
GYAN: This kind of puzzles can be solved by finding the cube root of the no. & then rounding to the whole no greater than the cube root.
So, for 2-8 marbles -> 2 weigh-ments
For 8-27 -> 3 weigh – ments
28 – 64 -> 4 weigh ments and so on..
Level 2: Hint: A m/c is capable of producing ‘n’ products & not just 1.
Level 4: This is really a good one!! I was able to know the threshold in 27tries. Can we do in less than this?
Level 5 : Minimum no of Rats: 10. Boy, the hint made this one a sitter.
Once again, great work.
Cheers!!
Rahul
Level 3: Rajiv, are we to assume that hats are only Red or Black? Is there anything else that should be known?
ReplyDeleteFirst of All.. Congrats for bringing this up. It is yet another great initiative. Something, I will definitely look forward to. Now let’s get to the real stuff!!
ReplyDeleteLevel 1: Minimum number of steps required is 3.
Step 1: Divide 24 marbles in group of 8. So, we have 3 sets of 8 marbles each.
• Weigh the first two sets
o This will give the set (8 marbles) that contains the heavier marble. (If the first 2 sets weigh equal, then the 3rd set contains the heavier marble.)
Step2: Divide the set of 8 marble (obtained from step 1) again in 3 sets of 3, 3 & 2 marbles.
• Weigh the first two sets
This will give the set (3 marbles) that contains the heavier marble. (If the first 2 sets weigh equal, then the 3rd set contains the heavier marble.)
Step3: Weigh the first 2 marbles obtained in step 2. We can get the heavier marble. (If the first 2 weigh equal, then the 3rd one is the heavier marble.)
GYAN: This kind of puzzles can be solved by finding the cube root of the no. & then rounding to the whole no greater than the cube root.
So, for 2-8 marbles -> 2 weigh-ments
For 8-27 -> 3 weigh – ments
28 – 64 -> 4 weigh ments and so on..
Level 2: Hint: A m/c is capable of producing ‘n’ products & not just 1.
Level 4: This is really a good one!! I was able to know the threshold in 27tries. Can we do in less than this?
Level 5 : Minimum no of Rats: 10. Boy, the hint made this one a sitter.
Once again, great work.
Cheers!!
Rahul
1. 3 weighings
ReplyDelete2. Take 1 object from Ist, 2 from 2nd and so on... you should have an electronic balance or some way to check the total weight you got.. simple math remains.
3. Red hat
4. 14 tries... n(n+1)/2<=number of floors in ques.
5. 10 rats.
1. Divide the 24 into 3 stacks of 8. Then divide the heaviest stack into 3 stacks of 3, 3 and 2 and weight the stacks of 3. The last try will give the result.
ReplyDelete3. Suppose there are 3 people A, B and C with C being the last one to be asked. Then A would not see two black hats; possibilities are one black one red or two red on B and C. If C wears a black then B could say with certainity that he wears a red but since it is still unclear that means C wears a RED hat.
ReplyDelete4. Suppose there are n trials, that means we can find the floor always within k trials. Hence we can try from beginning the floor n for the first egg and then subsequent (n-1) floors with the second egg. If the first n doesn't break the first egg then move to the next n and check then again move from n + (n-1) floors with the second egg. and so on. This would be an AP... n + (n-1) + (n-2)... +1 which is n(n+1)/2. and this should be more than the total number of floors we have. Thus making it 14 as 105 >100 we could get the result in a maximum of 14 trials.
5. Number all the 1000 bottles in the binary form. Now 1000 is <2^10 hence any number from 1 to 1000 could be written in a binary form in <=10 digits. Eg: 875 as 110110101. Now take 10 rats and consider them as the ABCDEFGHIJ respectively denoting the 10 digits of any binary number. Now feed the first rat i.e. J with the wines in all bottles where 1 comes in the unit's digit of binary. That means it will be fed the wine of 1, 3, 5, 7, 9 and even 875th bottle. Then take I and feed him with wine of every bottle where 1 comes in the digit at 10th place. Hence it will not be fed the wine of 875th bottle and in the same manner feed every rat according to the number on the wine's bottle. Now at the end of the month some rats would die because of the poisonous wine taken. Put them in the order ABC..J and consider all dead rats as 1 and living as 0 and reconvert the binary form to decimal and VOILA you'll get the number of the defective wine bottle.
Level 1 - Break them into 3 groups of 8 marbles.
ReplyDelete1 try will find out the heavier set.
Break that set into 3 sets of 3, 3, 2. Again one try to find out the heavy set.
If three in a set, keep one marble aside from that and weight the other two. If they are equal that means the third one is faulty else the one which is heavy is faulty. If two then simply weight them.
So total tries = 1 + 1 + 1 = 3.
Level 2 - Pick up 1 from first machine, 2 from second and like that 10 from the tenth machine. The sum should be 550 but it would be lesser than that and how much less will tell which machine is faulty.
Example - Suppose 2nd machine was faulty then the sum would be 548, which will give 550 - 548 = 2
Level 3 - If the last man sees two black hats in front of him, he would inmediately know his hat is red, as there are only two black hats in the lot. His "No" tells the other two men that at least one of them has a red hat.
With that information, if the middle man sees a black hat in front of him he would know for sure that his hat is red, but if he sees a red hat he can’t say anything. His "No" thus tells the first man that his hat is red.
Level 4 - 14 tries is enough to find out the threshold.
Let N the number of drops you need to find the first floor that breaks eggs. Go to the Nth floor and drop an egg. If it breaks you have (N - 1) more drops to test the (N - 1) floors below. If it doesn't breaks, go to the N + (N - 1) floor
and drop the same egg. If it breaks you have (N -2) drops left to test the N - 2 floors between Nth floor and 2N -1 floor. By a similar analysis you approach the top of the building with
N + (N - 1) + (N - 2) + (N - 3) + . . . + 1 <= 100
N ( N + 1 ) / 2 <= 100
This is a quadratic equation which yields N <= 13.65. If N = 13 you can only analyze a building of 91 floors. It takes N = 14 to test a 100 floor building.
Level 5 - 2^10 = 1024 So a max of 10 mice can figure out the poisonous bottle. For every combination between 1 to 1000, feed the mice one sip from that bottle in binary order.
Example - Suppose bottle number 8 = 0b0000001000, so feed mouse no.4 with a sip from bottle 8 and rest don't drink from it.
Now from the combination of mice dead we can figure out the number of poisonous bottle B-)
-- Dev Priya
College of Computing
Georgia Institute of Technology
1. Is the answer 3?
ReplyDeleteI break it in 8+8+8 and weighing any two of these sets.
From 8 break into 3+3+2 and weigh 3,3
From a set of 3 or 2 we can find out in one chance by weighing 1,1
2. From 1st machine produce 1 item, from 2nd produce 2, and so on..
Total sum should be 1+2+..+10 = 55
if the sum is (say ) 49 then 6th machine is faulty...
3. Color of 1st person's hat is red.
3rd one say no meaning Black,Black combo is not there for the 1st two
2nd would be able to see 1st hat which cannot be black since if it was black then 2nd one would have answered yes (red for his own hat).
So 1st one is red.
Level 3 :
ReplyDeleteCnsider the following situations
1. A -- Black
B -- Black
C -- Red
2. A -- Red
B -- Red
C -- Red / Black
3. A -- Black
B -- red
C -- Red /Black
4. A -- red
b -- Black
C -- Red / Black
It covers 7 possible combinations
Now if case 1 is there C can easily tell hat on his head. So that can't be our answer
Now take case 3. C sees A's and B's hat and can't determine his own. then B can see A's hat and he know's C was unable to tell colour of his hat so obviously B cant be wearing a black colour Hat else C would have answered So B can guess the colour of his Hat, which is also not our desired situation.
Now in case 2 & 4, neither C nor b can guess the answer but A has red Hat in both the cases, so he knows he is wearing red hat.
Level 4: 6 times you need to try to throw the egg to determine the threshold
ReplyDeletelevel 1 - weigh 3 times
ReplyDeletefirst divide into group of 8, weigh any 2, find the heavier one.
second divide into 3 marbles( one marble from one of the equal group) weigh any 2 group
then take any two out of the last and weigh
level 3 the first one can correctly identify it
ReplyDeletethe last one will have three options of first two hats which will lead him to confusion
RR RB BR
the second one will have confusion only if first one is red, thus options for him are
RR RB
since both the cases has first one as red thus the first one can correctly identify it as red
Level 2
ReplyDeletevolume of 9 kg will be different then the 10 kg product hence immerse in water to find the displacement of water in a container.
it can be verified using the weighing machine by finding the product with least displacement of water
Level 4: Earlier answer was when we dont have any limit on eggs.
ReplyDeleteWhen we just have 2 eggs, we need 14 tries. Solution
COnsider N* N+1 /2 > 99 for this N =14
Now 1st Egg : 14, 27, 39 , 50, 60, 69, 77, 84, 90, 95, 99
Let it break at 77
So we already have 7 tries
Now 2nd Egg: 70, 71, 72, 73, 74, 75, 76
Level 5 : 10 rats
ReplyDeleteWe can assign wine bottles no. from 1 to 1000 in binary
Wine 1: 0000000001
Wine 1000 : 1111101000
Now number rats from 1 to 10 and each rat would drink from wine if digit at nth position is 1. for eg. for 57 th wine 0000111001 rat 1,4,5,6 will taste it.
At 29th day check which all rats died
for eg.1, 6, 8, 9 died then
0110100001 417 wine was poisonous
Level 2 :
ReplyDeleteNumber machines 1 to 10.
Let Machine 1 produce 1 object, Machine 2 2, Machine 3 3 and so on.
Now if no fault machine total weight of objects would be
1*10 +2*10+3 *10+... == 550
Now assume 6th machine is faulty weight of obect would be be lesser by 6 , we will have 544Kg of weight. So we know 6th machine was faulty
level 4 : 14 tries
ReplyDeletelevel 5 : 10
Ans Puzzle 1: 4 weigh-ments, explanation: divide them in 2 parts, weigh, take the heavier one, again divide it in 2 parts (6 each), weigh n take the heavier one, repeat the process, n take the heavier part having 3 marbles, take any two n weigh them comparatively, if one is heavier it the the solution marble otherwise if they weigh same then the 3rd marble is the solution marble.
ReplyDeleteLevel 1: Three
ReplyDeleteDivide 24 marbles into 3 groups of 8 each (let A, B,C)
Round 1: Weight A and B, if both are equal then the marble is in C, if A is heavier then marble is in A else in B.
Let we get B as heavier . Now divide the 8 marbles into 3 groups of 3,3,2 let X,Y,Z
Round 2: Compare X and Y, if they r equal then problem is in Z else in the heavier of X and Y.
Round 3: Let problem in X, compare any 2 marble if they r equal then problem is in the 3rd marble otherwise the heavier of two.
(In case problem was in Z, just compare the 2 marbles and the heavier one is the problematic marble)
Hi Friends it was nice to see yor overwhelming response to the new initiative taken by Quizzing club at DMS, IIT Delhi. Keep Participating with the same enthusiasm in the upcoming Quizzes & Puzzles every week on Saturdays & Tuesdays respectively.
ReplyDeleteAnswers to Puzzle 1 are:
1)Answer: 3 times.
Divide the marbles into 3 groups of 8 each. 1st measurement : Measure any two groups. If both beams remain equal then the heavier marble is in the group not being measured else it is on the pan which is heavier. Then divide the 8 marbles into group of 3, 3 and 2. 2nd measurement: Measure the two groups of 3 marbles. If the pans balance then heavier marble is in the two marbles, else it is on the pan which is heavier. If its in the group of three marble then measure one marble on each pan. If its equal then the marble not being measured is heavier else the pan which is heavier has the heavier marble. If it is in the group of two marbles then its pretty simple.
2) Number the machines 1 to 10. Take 1 object from the 1st machine. 2 from the 2nd machine and so on. Weigh all of them together. It should ideally weigh 55kgs. Note the weight. If its 54 then the 1st machine is faulty. If its 53 then the 2nd machine is faulty and so on……
3) Answer: red hat
How the person in the front thinks:
The possible combination of hats can be
i) R R R
ii) R R B
iii) R B R
iv) R B B
v) B R R
vi) B R B
vii) B B R
Now he assumes himself to be wearing a Black cap.
He then thinks on behalf of the last person in the group. If the second person was also wearing the black cap(combination vii), then he would have said that he was wearing the red hat. But he did not say that. So that rules out combination vii.
He then thinks on behalf of the second person, still assuming that he is wearing the black cap. The second person would also think on similar lines above and would conclude that he himself is wearing a red hat(combination v or vi). But he is not able to conclude. So that rules out combination v and vi too.
He therefore concludes that I am wearing a red hat.
Note: This is just one way of reasoning. If worked out in this manner, it can actually be reasoned that all of them were wearing red hats.
4)Answer: 14 tries.
Throw first egg from 14. If it breaks then throw second egg from 1st floor onwards.
If it doesn’t then throw the 1st egg from(14 + 14-1) 27th floor. If it still doesn break then throw the egg from ( 27 + 14-2). Follow this pattern and you’ll require a maximum of 14 throws to determine the threshold floor
5)Answer: 10 rats
The trick is to minimize the problem. Think of it as 4 wine bottles. One of them being poisonous. Number the bottles 1 to 4. We can find out the poisonous bottle with the help of two rats. Let the 1st rat drink from the 1st bottle. Let the 2nd rat drink from the second bottle. Let both the rats drink from the third bottle. If only the 1st rat dies then 1st bottle is poisonous. If only the second rat dies then second bottle is poisionous. If both of them die then third is poisonous. If none of them die then fourth is poisonous. This can be extended for 8 bottles for which three rats will be required and so on…
A better solution for Level 4 :
ReplyDeleteLets us define a function F(n,c) as the maximum number of floors which can be tested with 'c' eggs and in 'n' attempts.
So, By definition : F(n,1) = n and F(0,c) = 0
Now you go to any floor and drop the egg from there, two possibilities arise depending on the egg will break or not.
=> F(n,c) = F(n-1,c) + F(n-1,c-1) + 1
For c = 2,
=> F(n,2) = F(n-1,2) + F(n-1,1) + 1
or F(n,2) = F(n-1,2) + (n-1) + 1
Now,F(n-1,2) = F(n-2,2) + (n-2) + 1
...
and,
F(1,2) = F(0,2) + 0 + 1
Adding all these we get :
F(n,2) = (n-1) + (n-2) + .....+ 1 + {1+1+1..... n times}
=> F(n,2) = n + n-1 + n-2 + ..... + 1
=> F(n,2) = n(n+1)/2
Now, F(n,2) - 100 should be minimum positive number {where n is an wholenumber}
By this method we can solve for any number of floors with any number of eggs.
Regards,
Anurag Kesarwani
DMS MBA 2010-12