Fog Creek Software
Discussion Board




Another Weighing Problem

there are M boxes each having 10 balls of 10 gms each. but there are some N defeective boxes ( 0<=N<M) where each ball is 9gms. u have a scale to weigh them. how will u find the defective boxes with just one weighing chance.

saai ananth S.S.
Friday, June 17, 2005

Label the boxes 1 to M.

i have a solution not for 10 balls in each box but if there are
atleast 10^(M-1) balls in the last box 10^(M-2) in the last but one.i.e the i th box should have atleast 10^(i-1). but my solution will work even if N the number of defective boxes is not given i.e given M boxes with aribitary defective ones (defective meaning all balls of 9 gms) the following solution can identify the defective boxes


the solution is


1. take 10^(i-1) balls each from box labeled i and weigh them all. let their weight be X

2. subtract X from summation i = 1 to M of 10^i

3. the result will have just 1 and 0...if the units place digit of the result represents box 1, tens place digit represents box 2 and so  on....the boxes that are defective are the ones that correspond to the place of the digit that is 1 in the result..


for example lets us consider 4 boxes labelled 1, 2,3,4 and suppose box 2 and 3 are defect

taking 10^(i-1) balls from each box labelled i we take
1 ball from box 1, 10 balls from box 2 and so on and
their weight will add up to (10 + 90 + 900 + 10000) = 11000

and subtract it from 11110 which summation i = 1 to 4 of 10^i

i.e (11110 - 11000) = 00110
5 4 3 2 1
0 0 1 1 0
here the tens and hundreds digits of the result are 1 so boxes 2 and 3 are defective

Abyss
Friday, June 17, 2005

even for the M boxes with just 10 balls where N is defective by picking 1 ball from box 1 , 2 from box 2, i form box i and weighing them and subtracting the weight from the weight of the same number of balls if none were defectivnue  we get a value which is a unique sum for a given N numbers.

I am just not able to think a solution out of the top of my head for the problem find N numbers between 1 and M whose sum is unique .

Abyss
Friday, June 17, 2005

Any hint if i am heading in the right direction ??? Or any one else that can give the solution

Abyss
Friday, June 17, 2005

I think the statement "boxes each having 10 balls of 10 g" is not satisfied by the solution of Abyss, since we have only 10 balls for weighting in each BOX.
I can solve it through a similar approach by selection 1,2,4,8,16,32...... balls from the respective boxes and than substracting it from (2^m -1) the remainder  will be unquely decomposed interms of factor 1,2,3,8.... which will give you the box number.........

I m particularly intreasted in the solution where whe repect the constraint "boxes each having 10 balls of 10 g"....



 

Deepak pant(STM)
Friday, June 17, 2005

You are, Abyss, Saai's problem does not have solution.

We can use from 0 to 10 balls from each box in the weighting (even 1 to 10 as N can be zero). This means if there are more than 11 boxes we are guaranteed to have boxes, represented by equal number of balls. If only one of these boxes has defective balls - it is impossible to tell which one is which in a single reading.

DK
Friday, June 17, 2005

Deepak

Yes my solution deos not satisfy the constraint.

I have made an assumption that there are atleast 10^(i-1) balls in box labelled i.

But my solution is generic in the sense you do not have to know the number of boxes(N) that are defective.

In other my solution is for the problem statement below

Given M boxes with infinite balls in each of them find the defective boxes(by defective box we mean all balls in that box weigh 9 gms each and by non defective all balls weigh 1 0gms)

I am not able to think of a solution for 10 balls in each of the M boxes given N of them are defective.

Abyss
Friday, June 17, 2005

a note i thought might be useful for any problems of the same type

Given M boxes with infinite balls in each of them find the defective boxes(by defective box we mean all balls in that box weigh 9 gms each and by non defective all balls weigh 1 0gms)

for the above problem and deepak and me arrived at a solution by just expressing the powers in different base ( 2 and 10).

since the problem finally boils down to identifying a 1 or 0 in the difference in wieghts for each box labelled i (by difference here i mean the the difference if it were non defective as to if it  were defective box) we can express any sequence of 1 or 0 uniquely using any base (radix)

Abyss
Wednesday, June 22, 2005

*  Recent Topics

*  Fog Creek Home