Five Jars of Pills.

The previous post  reminded me of another puzzle.

Lets say there are 5 jars of pills. One of the 5 jars contains contaminated pills. All pills weigh 10 grams, except contaminated pills. contaminated pills weigh 20 grams. Lets say you are given a scale / spring balance, which can give you the weight measurement, Whats the least number of measurements you need to find out the jar with contaminated pills.

.
.
.
.
.
.
.
.

Solution : Most people try to solve the problem, similar to the well known puzzle, but there is key difference here. Here, we have spring balance and not simple balance, hence we can not use principle of equality for elimination.

Well, the answer is 1, and is based on simple math. Here's how. Label the jars as Jar1, Jar2, Jar3, Jar4, Jar5

Take 1 pill from 1st jar, 2 pills from 2nd jar, 3 pills from 3rd jar, 4 pills from 4th jar and 5 pills from 5th jar and measure the total weight of 1+2+3+4+5 i.e. 15 pills.

If the measurement is

160 grams then the contaminated pill is from Jar 1 [ 20 + (2 * 10) + (3 * 10) + (4 * 10) + (5 * 10) = 160 ]
170 grams then the contaminated pill is from Jar 2 [ 10 + (2 * 20) + (3 * 10) + (4 * 10) + (5 * 10) = 170 ]
180 grams then the contaminated pill is from Jar 3 [ 10 + (2 * 10) + (3 * 20) + (4 * 10) + (5 * 10) = 180 ]
190 grams then the contaminated pill is from Jar 4 [ 10 + (2 * 10) + (3 * 10) + (4 * 20) + (5 * 10) = 190 ]
200 grams then the contaminated pill is from Jar 5 [ 10 + (2 * 10) + (3 * 10) + (4 * 10) + (5 * 20) = 200 ]


Think about the variation : What if you just know contaminated pills are of different weight, but do not know whether they are overweight or underweight.

Find the Defective ball.

Here's a very well known puzzle.

You are given 9 balls of equal size, color and texture. one of them is defects. All balls have the same weight, except the defective one which has a higher weight.  Lets say you are given a simple balance for measurement,  How many measurements would you need to find out the defective one ?
..
.
.
.
.
.
.
.
.
.
.

Solution :-

Most people either come up with the answer as 3 or 4. But the answer is two. The trick is to do elimination. In this case, from the 9 balls 6 of them can be eliminated by dividing 9 balls into 3 sets of 3 balls each. Lets call them Set A, Set B and Set C.

Place A on one side of the simple balance and B on the other side of balance and measure. If they measure equally, then the defective (overweight) ball is on the third set C. If A weighs more than B, (then the weight of B & C will be equal), the defective (overweight) ball is in Set A, whereas if B weighs more than A, then its in Set B. In a single measurement, we could eliminate 6 out of 9 balls and narrow down the search to 3 balls.

Now, lets call three balls x,y,z. Measure x against y in the simple balance.

if x = y then z is the defective ball
if x > y then x is the defective ball
if y > x then y is the defective one.

So, the answer is 2 measurements.

Variation : For the same 9 balls and 1 defective ball problem, lets say the defective ball has a different weight, but we do not know whether its overweight or underweight. Whats the least number of measurements then ? 

Tablet Puzzle.

An interesting puzzle I came across :

Puzzle :-

A patient is given 2 vials of tablets labeled A & B. He has to take one tablet from each vial dialy. Neither can he skip nor can he take overdose, as either of this would prove fatal.

One day - after taking one tablet from vial A, 2 fall from vial B. Now he has 1 tablet from A and 2 tablets from B. By a clever logic - he manages to avoid overdoes even though there is no way to differentiate the tablets to be from A or B. They are same in color, texture, size, appearances. Of course, he does not waste the 3 tablets, i.e. the solution is not to throw these three and take 1 from A, and 1 from B :)

.
.
.
.
.
.
.
.
.

Solution :-

He divides the tablets into halves. He gets 2 pieces of each. After this he consumes of one half of each. i.e. he would have consumed 2 halfs of tablets from B, making it a single B tablet and 1 half of tablet from A. now he takes another tablet from A, divides into half, and consumes it. He preserves the remaining four halfs for the following day.

Clever, ain't it ? :)

2 egg shells and 100 floors

There are two identical egg shells. Now they are very strong but are identical and have a breaking height (meaning, there is certain height below which they do not break, beyond which they will break). You have a 100 story building. Now you want to know using these two eggs, what is the minimum floor from which they will break. Come up with an efficient algorithm/ approach for it ?

I found this question to be pretty interesting, as it points to a way of solving problems. Answer below..








Solution :-

One thing most would figure out is to rephrase the question about efficiency as, whats the minimum number of drops you need to make to find which floor the egg breaks from.

The problem is harder as you are only allowed to throw 2 eggs. Thus, the second throw operation is a linear operation. Thus, the problem is reduced to finding a solution which requires minimum number for 2nd linear throw.

Let's say that x is the optimal number of throws required. And, for time being let's say x=20. Then,

You would do the first throw from 20th floor and if egg breaks you would do a linear operation of throws from 1st to 20th floor to find which floor the egg breaks.
However, if the egg doesn't break then you will throw from 39th floor, as you are now one throw less. Following this logic
20
39
57
73
88
102, etc. 20 is not the optimal number of floors, thus not the right answer. Basically you should be able to cover all the 100 floors with the second linear operation, without exceeding the optimal number of throws. lets call it x, thus it becomes,
x + (x-1) + (x-2) + ... + 1 = 100
x(x+1)/2=100
which implies x=14 which is the optimal number of throws required. Check the following.

Step Count

first drop from 14th if it breaks, try from 1-13, else - if it broke the count is : 1+13 14
drop from 27 if it breaks try from 15-26, else - if it broke the total number of throws is still 2+12 = 14
drop from 39 ...................................., else - 3 + 11 = 14
drop from 50....................................., else - 4+ 10 = 14
drop from 60....................................., else - 5 + 9 = 14
drop from 69....................................., else - 6 + 8 = 14
drop from 77....................................., else - 7 + 7 = 14
drop from 84....................................., else - 8 + 6 = 14
drop from 90....................................., else - 9 + 5 = 14
drop from 95....................................., else - 10 + 4 = 14
drop from 99....................................., else - 11 + 3 = 14
drop from 100....................................

So, one (well known) way to solve the problems is to assume the solution and workout backwards.

Now the twist, Whats the optimal number of trails if the number of eggs allowed was 3 ???