Weighing Piles of Coins
Source: Asked to me by Ankush Agarwal (Sophomore, CSE, IITB)
Problem: There are two kinds of coins, genuine and counterfeit. A genuine coin weighs X grams and a counterfeit coin weighs X+delta grams, where X is a positive integer and delta is a non-zero real number strictly between -5 and +5. You are presented with 13 piles of 4 coins each. All of the coins are genuine, except for one pile, in which all 4 coins are counterfeit. You are given a precise scale (say, a digital scale capable of displaying any real number). You are to determine three things: X, delta, and which pile contains the counterfeit coins. But you're only allowed to use the scale twice!
Prize: Treat at H8 canteen to the first person who solves it!!
Problem: There are two kinds of coins, genuine and counterfeit. A genuine coin weighs X grams and a counterfeit coin weighs X+delta grams, where X is a positive integer and delta is a non-zero real number strictly between -5 and +5. You are presented with 13 piles of 4 coins each. All of the coins are genuine, except for one pile, in which all 4 coins are counterfeit. You are given a precise scale (say, a digital scale capable of displaying any real number). You are to determine three things: X, delta, and which pile contains the counterfeit coins. But you're only allowed to use the scale twice!
Prize: Treat at H8 canteen to the first person who solves it!!
Unable to narrow down the solution to one pile unless i am allowed to break the coins!
ReplyDeleteWe are having 13 piles lets call them P1 ,P2 ... now take (2,2) (0,2) (2,0) (1,3) (3,1) (1,4) (4,1) (2,3) (3,2) (2,4) (4,2) (3,4) (4,3) coins from P1,P2,... (Note:(x,y) from Pj means x for the 1st measurement from Pj and y for the 2nd measurement from Pj.)It is clear that you are using 31 coins for each measurement , now it is also clear that you can use atmost 4 counterfeit coins in atmost 1 of the two measurements so there will be a measurement where the no. of counterfeit coins is 3 or less . Let the measured weight during the first attempt be m1 and the secon be m2 we then find p1,q1(nearest to m1) and p2,q2(nearest to m2) such that p1<=m1<=q1 , p2<=m2<=q2 such that p1,p2,q1,q2 are multiples of 31 for atleas one of the cases(WLG say the 1st measurement used less than 3 counterfeit coins) we will definetly have m1-p1 < 15 and q1-m1 > 15 (or the exact opp case) now we can conclude that X is p1/31 and now we find m1-p1 and m2-p1 say d1 and d2 depending on the ratio of d1 and d2 we can exactly identify which pile contais the counterfeit and also delta .
ReplyDelete@HarshaNandan.. \m/
ReplyDeleteAwesome solution.. I just have a small doubt.
@Ankush.. satisfied?
Just to reiterate,
We are having 13 piles lets call them P1 ,P2 ...P13 and now take (2,2) (0,2) (2,0) (1,3) (3,1) (1,4) (4,1) (2,3) (3,2) (2,4) (4,2) (3,4) (4,3) coins from P1,P2,... P13. (Note:(x,y) from Pj means x for the 1st measurement from Pj and y for the 2nd measurement from Pj.) It is clear that you are using 31 coins for each measurement. It is also clear that we can use maximum 4 counterfeit coins in not more than 1 of the two measurements so there will be a measurement where the no. of counterfeit coins is 3 or less. Let the measured weight during the first attempt be m1 and the second be m2.
m1 = 31*X + xi*delta
m2 = 31*X + yi*delta
if ith pile is counterfeit.
So, by floor and ceilings of m1 and m2, we get p1, q1 (multiples of 31 nearest to m1) and p2, q2 (multiples of 31 nearest to m2).
Since q1-p1=31, at least one of q1-m1 or m1-p1 has to be <= 15
Similarly, Since q2-p2=31, at least one of q2-m2 or m2-p2 has to be <= 15
Assuming the first is correct, we will have one value of X and Assuming the second is correct, we will have other value of X. Note that in some cases, both would be correct. But not all. Any suggestions? Am I missing something?
On discussion.. We and Harsha could see that the solution posted by Harsha is wrong :(
ReplyDeleteAny other suggestions?
Let us take the first measurement as mentioned in my previous post if the measured value is say W1 and W1+K = 31*t or W1-K = 31*t for some integer t and 0 <= K < 11 then we can say that t is our actual weight we will then take the 2nd measurement and as we have distinct ratios we are done.Suppose we don't get such a number in the first measurement then we are sure that the faulty coin is not from {(2,2),(0,2),(2,0),(1,3),(1,4),(2,3),(2,4)} as if so then max error would have been 10 in 1st measurement and this is clearly not the case so the faulty coin is from {(3,1),(4,1),(3,2),(4,2),(3,4),(4,3)} so what we do now is for the 2nd measurement we take the above mentioned no. of coins from the above piles and 4 coins from the piles which we are sure that the faulty coin is not from , thee total number of coins is 41 so we can find all the 3 unknowns.
ReplyDeleteHaven't read the other soln. so this could be same.
ReplyDeleteWeighing 1:
Pick
4 from P1, P6, P11
3 from P2, P7, P12
2 from P3, P8, P13
1 from P4, P9
0 from P5, P10 & weigh.
Total coins 29.
Let weight be w.
w - 29X will be y*delta;
y being the no. of coins chosen.
Map the entire table & we see that y*d (d = delta) is uniquely determined.
This gives X as well.
However, knowing y*d doesn't tell us either y or d.
eg: y*d could be 4 = 1*4, 2*2, 4*1
So we pick
4 from P1, P3, P4
3 from P6, P8, P9
2 from P11, P13
Knowing X gives 9X and we can triangulate y*d.
Similarly from y*d = +-2, +-4, +-6, +-8, +-3, +-12.
@Shantanu..
ReplyDeletew - 29X will be y*delta; y being the no. of coins chosen.
y*d (d = delta) is not uniquely determined.
y*delta is <= 20 and >= -20
So, a diff of 40. So, X can have two values.
Eg: If w is 300, y*d is either 10 or -19
Weighing 1:
ReplyDeletePick
4 from P1,P2,P3,P4
3 from P5,P6,P7,P8
2 from P9,
1 from P10,P11,P12,P13
So we are using a total of 34 coins.
Using 34 enables us to obtain y*d uniquely.
There cannot be confusion between the pairs(20,-14),(19,-15)(18,-16)(17,-17) because at max, only 1 of these pairs can be a valid value for y*d.
So we can uniquely identify x.
Let us discuss the worst case scenario when y*d is 4.
In this case d can be 1,2,4.
We can get different products for y2*d by selecting
0 from P1
1 from P2 and P10
2 from P3 and P11
3 from P4, P9 and P12
4 from P13
All other y*d have a maximum of 2 possiblities for d. For these cases we have to distinguish 8 sets for which we need 8 different products of y2*d, we have 10 totals for by selecting 0,1,2,3,4 from these sets, with two zeros and one other repeated product. So dropping one 0 and one of the repeated products we can always have 8 different products for y2*d.
Hope that I have not overlooked anything in my hurry to reach a solution :)
@telnet..
ReplyDeleteagain not possible to get a unique value..
Say the value u get is 358
y*d = 18 or y*d = -16? :( So i don't see x being uniquely identified.
You cannot get a value of y*d =18
ReplyDeleteIf y*d = 18 possible pairs of y & d are (1,18),(2,9),(3,6)
But y<=4 and d<=5
34 and 37 are numbers where there cannot be any confusion in any of the pairs.
You owe me a treat next time I come to the hostel :)
ReplyDelete@telnet : Isn't d a real?!
ReplyDelete@telnet..
ReplyDeletesorry rahega.. lekin d is not necessarily an integer.. d can be any real number :(
Are you sure that this can be solved using real number values for delta?
ReplyDeleteBcos a value of y*d = 4
could be 1*4 2*2 3*1.33 4*1
The first weighing does not help you narrow down the search space.
Will give this another try though.
This comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteSeems right to me at first glance.. Awesome Max.. Any problems anyone?
ReplyDeleteWill have a closer look at your solution in some time. Great solution I think!
Not so sure about the proposed solution. It works in all cases, except for one specific situation.
ReplyDeleteWhen the delta is +/- 34/7, I believe a degeneracy occurs, making it impossible to tell the 4,3 pile from the 3,4 pile. In either case, attempts to solve the problem in this situation result in an ambiguity as to whether delta is positive or negative, the value of X (which could be one of two adjacent integer values), and which of these two piles contains the counterfeit coin.
Perhaps there's another way to solve it that relieves this ambiguity.
I've worked out a small variation to Neeraj's solution, which gets around the problem I brought up earlier. If we make the following two changes to the groupings, I've determined that it will work for all values of delta up to +/- 6.5, and there may be a way to get even wider ranges to work.
ReplyDeleteModify the groupings as follows:
4,3
3,4
2,4
4,2
3,3 : Change this to 4,4.
1,4
4,1
2,3
3,2
1,3
3,1
0,4 : Change this to 0,0|1. (see below)
4,0
The key change here is the change of 0,4 to 0,0 or 0,1, depending on the result found in W1. First of all, changing the 3,3 to 4,4 ups the number of coins in W1 to 35. (This change may or may not be necessary, but I solved it with this change in place to maximize the number of coins being weighed, and it worked. I'll try it again later with 34 coins instead of 35 coins, to see what that gives.)
Using the coin in the second weighing of the 0,4 pile is conditional. If W1 modulo 35 equals zero, then the counterfeit coin must be in the 0,4 pile. (It was the only coin that wasn't weighed in W1, and given the ranges involved, W1 modulo 35 can only be 0 in the event that all coins on the scale are genuine.) In that case, weight one coin from this pile all by itself, and that will indicate the delta, where X is simply W1/35.
In the case where W1 modulo 35 is not equal to zero, the counterfeit pile must be in one of the piles on the scale. By eliminating the 0,4 pile from the second weighing, the number of coins being weighed in W2 is 31, and this makes the solution to the problem more unique.
Basically, W1 and W2 both must differ from 35*X and 31*X respectively by values that have distinct ratios with one another. These ratios can only be one of the following values: 0, 1/4, 1/3, 2/4, 2/3, 3/4, 4/4, 4/3, 3/2, 4/2, 3/1, and 4/1. Though there is a question of whether X is one of two adjacent values, in any of these cases, only one particular value will result in a ration from the following set. That value determines X, and it determines the ratio as well. From the ratio, it's possible to solve for delta and determine which pile is the counterfeit one. (Each of the values above corresponds to one particular pile.)
The key to this approach is using two different numbers of coins for the two weighings, which prevents certain degeneracies from occurring.
take following no of coins form the 13 bags starting from 1st bag to 13th bag
ReplyDeletefirst weigh = 1_1_2_1_3_1_4_2_3_2_4_3_4
sec weigh = 1_2_1_3_1_4_1_3_2_4_2_4_3
sum = 2_3_3_4_4_5_5_5_5_6_6_7_7
31X + mD = W1 eq1
31X + nD = W2 eq2
if w1=w2 then its from 1st sack
else
if w1> D then X>> (m+n)D coz m+n = [2,7]
divide w1+w2 by 62 to find value of X
then
try dividing the above remainder by 2,3,4,5,6,7
the one which completely divides it is the value of m+n
now we have m+n , D and , X
now put value of D and X in the eq 1 and 2 to get value of m and n
once we get the value of m and n we can easily know which sack it was by looking at the value of m and n.
same is the case when w1>w2.
Naman,
ReplyDeleteyour solution will not always work because D need not be integral.
Mike's solution appears to be fine for fractional values of D as well.
This is getting messy. :(
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeletePratik, you're right, it is getting messy, but there is actually a very elegant solution to this problem.
ReplyDeleteNo, Mike's solution is not correct, not even for integral values of Delta. You can't determine Delta from ratios of the remainders modulo 35 and 31. Suppose Delta is -4 and you weigh 4 counterfeit coins in the first round and 3 in the second round. The remainders would both be 19. The ratio of the remainders would be 1:1 (or 4:4), but that doesn't mean that the number of counterfeits weighed in the first and second rounds is the same, so you can't determine the counterfeit pile.
This comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteWorking on the previous suggestions (mainly from Neeraj's):
ReplyDeleteR1 = first weighing
R2 = second weighing
V1 = a.delta = R1 mod 29
V2 = b.delta = R2 mod 29
a = num of faulty coins in R1
b = num of faulty coins in R2
Decision table for positive delta:
Column 1: Pile number
Column 2: Coins from this pile in R1
Column 3: In R2
Column 4: (V1)/(V2) (If the faulty coin was in this pile)
1| 3| 0| NaN --> b.delta = 0|
2| 2| 1| 2|
3| 1| 2| 1/2|
4| 0| 3| 0|
5| 3| 1| 3|
6| 2| 2| 1|
7| 1| 3| 1/3|
8| 4| 1| 4|
9| 3| 2| 3/2|
10| 2| 3| 2/3|
11| 1| 4| 1/4|
12| 4| 3| 4/3|
13| 3| 4| 3/4|
If the ratio does not match to any of the above values then use this ratio instead:
(29-V1) / (29-V2)
And use the same decision table.
This should work for nonzero real delta from -5 to 5 and any positive integer X.
This comment has been removed by the author.
ReplyDeleteNeerajkoul, please read your comment and repost if necessary. It seems that some (significant?) part of your post is lost because your {less,greater}-than signs are being interpreted as part of HTML tags.
ReplyDeleteI think I can vaguely guess what you are trying to say, but it's tough. For example, I find this part to be incomprehensible and I'm not sure how much is missing:
If 0= 4
4 4
4 3
4 2
4 1
4 0
Five groups . weigh the second grouping from these balls. ( Means only 10 balls)
Thanks.
This comment has been removed by the author.
ReplyDeleteHad deleted my earlier posts because they were wrong solutions, rather they tried to solve a problem which wasn't there at all.. I hadn't read the problem clearly..
ReplyDeleteThere was something mentioned about delta being strictly between -5 and 5( as in not including 5 and -5 ).. And all through i had assumed it to be between -5 and 5
( as in inclusive of 5 and -5 )...
4 4
4 3
3 4
4 2
2 4
4 1
1 4
3 2
2 3
4 0
0 4
3 1
1 3
===
35 35
-5 < delta < 5 ( delta is "strictly between" ,as goes by the problem definition )
Weigh first grp = W1
Let W1 = 35X+Y,
If Y=0, then 0 4 is the culprit. weigh one ball from the group and get the delta, as weight is X.
If 0 < Y < 15, then we know that delta is +ve and weight is X, get the second weighing and suppose it is W2.. Try fitting the variables, as in the no of balls from the
group, in the weight eqns to know of the group and the delta.
If Y = 15, then it is the case of 4 balls, with +ve delta of 15/4 and weight X. No need of second weighing. ( 3*5 is 15 but delta can't be 5 , and also not 35+ 4*-5,
as delta can't be -5 )
If Y = 20, then it is the case of 4 balls, with -ve delta of - 15/4 and weight (X+1). No need of second weighing. ( Same expln as above case )
If 20 < Y < 35, then it is the case of -ve delta. weight is X+1 and now get the second weighing and suppose it is W2.. Try fitting the variables, as in the no of balls
from the group, in the weight eqns to know of the group and the delta.
Case of 15 < Y < 20 ( The monstrous case )
======================================
This just implies that it is the case of 4 ball groups which is counterfeit
3.75 < delta < 5
or
-5 < delta < -3.75
We know Weight can be X or X+1 depending on the delta. Weight has to be >= 4
4 4
4 3
4 2
4 1
4 0
Five groups . weigh the second grouping from these balls. ( Means only 10 balls)
suppose it is 10A+B
If B = 0, then group 4 0 is the culprit
A = X weight is X and delta is +ve and is Y/4
A = X+1, weight is X+1 and delta is -ve and is -Y/4
Why so?. Can't B = +/- 10*SomeInt, Can be 10 or -10 , not +/- 20 ( because delta < 5 and > -5 ). And 10, a big No
because +/- 10 = +/- 2.5 * 4 ( and +/- 2.5 is not in the delta rangesmentioned above )
+/- 10 = +/- 3.33 *3 ( and +/- 3.33 is not in the delta ranges mentioned above )
+/- 10 = +/- 5 * 2 ( refer to "strictly between 5 and -5" for delta in the prob definition )
A = X,
0< B < 3.75, then it is 4 2 which is the culprit and delta is -ve and is -Y/4 and weight is X+1
3.75 < B < 5, then it is the case of 4 1 group, +ve delta of Y/4 and weight X
5 < B < 7.5, 4 1 grp, -ve delta of - Y/4, wt X +1
7.5 < B < 10, 4 2 grp, +ve delta of Y/4 and wt X
If it is 4 3 or 4 4 group we will have A = X+1 or A = X-1, because +/- 3.75 * (3, 4) > 10 ( or < -10 )
A = X +1,
0 < B < 5, then 4 3 is the culprit, +ve delta of Y /4, and weight X
5 < B < 10, 4 4, +ve delta of Y /4, and weight X
A = X -1,
0< B < 5, then 4 4, -ve delta of - Y /4, and weight X+1
5 < B < 10, then 4 3, -ve delta of - Y /4, and weight X+1
Hope this explanation suffices.. Have tried to be as simple in approach as possible..
This comment has been removed by the author.
ReplyDeleteCase of 15 < Y < 20 ( The monstrous case )
ReplyDelete======================================
This just implies that it is the case of 4 ball groups which is counterfeit
3.75 < delta < 5
or
-5 < delta < -3.75
We know Weight can be X or X+1 depending on the delta. Weight has to be >= 4
4 4
4 3
4 2
4 1
4 0
Five groups . weigh the second grouping from these balls. ( Means only 10 balls)
suppose it is 10A+B
If B = 0, then group 4 0 is the culprit
A = X weight is X and delta is +ve and is Y/4
A = X+1, weight is X+1 and delta is -ve and is -Y/4
Why so?. Can't B = +/- 10*SomeInt, Can be 10 or -10 , not +/- 20 ( because delta < 5 and > -5 ). And 10, a big No
because +/- 10 = +/- 2.5 * 4 ( and +/- 2.5 is not in the delta rangesmentioned above )
+/- 10 = +/- 3.33 *3 ( and +/- 3.33 is not in the delta ranges mentioned above )
+/- 10 = +/- 5 * 2 ( refer to "strictly between 5 and -5" for delta in the prob definition )
A = X,
0 < B < 3.75, then it is 4 2 which is the culprit and delta is -ve and is -Y/4 and weight is X+1
3.75 < B < 5, then it is the case of 4 1 group, +ve delta of Y/4 and weight X
5 < B < 7.5, 4 1 grp, -ve delta of - Y/4, wt X +1
7.5 < B < 10, 4 2 grp, +ve delta of Y/4 and wt X
If it is 4 3 or 4 4 group we will have A = X+1 or A = X-1, because +/- 3.75 * (3, 4) > 10 ( or < -10 )
A = X +1,
0 < B < 5, then 4 3 is the culprit, +ve delta of Y /4, and weight X
5 < B < 10, 4 4, +ve delta of Y /4, and weight X
A = X -1,
0< B < 5, then 4 4, -ve delta of - Y /4, and weight X+1
5 < B < 10, then 4 3, -ve delta of - Y /4, and weight X+1
Hope this explanation suffices.. Have tried to be as simple as possible in my approach ..
This comment has been removed by the author.
ReplyDeleteWell i think was not clear enough in my explanation.. One of my friends still stood to ask questions about the soln..
ReplyDeleteWell here goes a bit more of the explanation..
Case of Y = 15 , that means No of balls is 4 ( as explained earlier) and that delta is +ve and of value 15/4.. I had wrongly written no second weighing is required.. We do need for getting the group..
In this case
g1 -> 4 4,
g2 -> 4 3,
g3 -> 4 2 ,
g4 -> 4 1 or
g5 -> 4 0 is the group..
Now take 4 balls from g1, 3 from g2, ...., and 0 from g5..Now take the second weighing.. Let it be W2.. Now we know X ( X of 35X+Y)and Y (15/4) both.. We just need to solve W2 = 10X+(15*4)*n for n to get to know of the group
Similar explanation goes for case of Y being 20.. ( Just that here weight is X+1 and delta is -ve and of value -15/4 )
For the case of say 0<Y<15 (delta is +ve) or 20<Y<35 ( delta is -ve)
Now refer to the grouping we did
4 3
3 4
4 4
4 2, etc..
These groupings are unique.. 4 3 is not repeated either in ratio or value.. ( We would have landed in a problem if we had taken say two or more groupings in ratio, e.g, 2 4 and 1 2 ( as 2/4 = 1/2 ), or 3 3 and 4 4 ( 3/3 = 4/ 4) ( Will explain later as to why )..
Now that we have got W1 and w2, and we know X..
So let's suppose W1 = 35X+d1
W2 = 35X + d2
if W1 = W2, then 4 4 is the culprit group..
else take group 2 ( 4 3) and solve as follows ..Take the value d1/4 and see
if W2 = 35X + 3*(d1/4) ( X is known from W1 itself).. If it equals, then 4 3 is the culprit group.. If it is not equal, then proceed to the next group , as in 3 4 and check..).. We won't have problems at a unique grouping because none of the groups are in the same ratio.. To explain it better, let's suppose that we had taken 2 4 and 1 2 as two of the groupings..Now suppose we got delta of 4 in the first weighing and 8 in the second weighing, then we will be at fix as 2*2 = 4 *1 = 4
and 2*4 = 4 *2 = 8..
take following coins from piles
ReplyDelete0 1 1 2 2 3 4 4 3 4 3 4 4
- - - - - - - - - - - - -
4 4 3 4 3 4 4 3 2 2 1 1 0
(this is called farey sequence along with inverses..if any one care to know :P)
p1 and p2 be sum first and 2nd collection resp.
p1= 35x+ delta*a1
p2= 35x+ delta*a2
EASY case : if p1=p2 then counterfeit pile is 7th (with 4/4) and a1=a2=4. in next step take any coin from other piles and get value of x and delta.
else
calculate sum w=p1+p2=70x+ delta(a1+a2).
now since |delta|<5 and (a1+a2)<= 7
hence |delta(a1+a2)| < 35
Hence nearest integer (w/70) = x
now find y1=p1-35x=delta*a1 and y2=p2-35x=delta*a2
So y1/y2 = a1/a2 Since a1/a2 is different for all the 13 piles hence from this you know which pile the counterfeit coin belongs