[bushindo]

Suppose that you have 10 piles of coins. Each pile has exactly 10 coins. Eight piles consist of normal coins, which weight 100g each, and the remaining two piles consist of fake coins, each of which is heavier than 100 g. All the fake coins have identical (and unknown) weight.

You are given a digital scale, which can take any number of coins and return the total weight. Please identify the 2 piles with fake coins in only 2 weighings.

EDIT: I apologize for the double post. I have no idea why this puzzle shows up twice as two topics. If any mod sees this, please delete this duplicate topic.

Edited December 18, 2010 by bushindo

[wolfgang]

give the piles numbers, 1 to 10

then take the piles No. 1,4,6 and 8

taking from pile No. 1..only one coin,from No. 4 ...4 coins,from pile No. 6...6 coins and from pile No. 8...8 coins.

if we find a (1X)difference,so the pile No. 1 is fake,

4X....No.4

5X...No. 1 and 4

6X..No.6

7X...No. 1 and 6

8X...No.8

9X...No. 1 and 8

10X ...No. 4 and 6

12X...No. 4 and 8

14X....No. 6 and 8

If the total wieght is 190gm,so(No. 1,4,6 and 8) are normal.

then we will make the second weight with the piles No.2,5.9 and 10,take:

2 coins from No. 2,,,5 coins from No. 5,,,9coins from No. 9 and 10 coins from pile No. 10.

If the difference is 2X.....No.2

5X...No. 5

7X...No. 2 and 5

9X...No. 9

11X...No. 2 and 9

10X....No. 10

12X...No. 2 and 10

14X...No. 5 and 9

15X...No. 5 and 10

19X...No. 9 and 10

But if the total weight was 260gm,so they are normal,and the fake piles will be No. 3 and 7.

Edited December 18, 2010 by wolfgang

[bushindo]

give the piles numbers, 1 to 10

then take the piles No. 1,4,6 and 8

taking from pile No. 1..only one coin,from No. 4 ...4 coins,from pile No. 6...6 coins and from pile No. 8...8 coins.

if we find a (1X)difference,so the pile No. 1 is fake,

4X....No.4

5X...No. 1 and 4

6X..No.6

7X...No. 1 and 6

8X...No.8

9X...No. 1 and 8

10X ...No. 4 and 6

12X...No. 4 and 8

14X....No. 6 and 8

If the total wieght is 190gm,so(No. 1,4,6 and 8) are normal.

then we will make the second weight with the piles No.2,5.9 and 10,take:

2 coins from No. 2,,,5 coins from No. 5,,,9coins from No. 9 and 10 coins from pile No. 10.

If the difference is 2X.....No.2

5X...No. 5

7X...No. 2 and 5

9X...No. 9

11X...No. 2 and 9

10X....No. 10

12X...No. 2 and 10

14X...No. 5 and 9

15X...No. 5 and 10

19X...No. 9 and 10

But if the total weight was 260gm,so they are normal,and the fake piles will be No. 3 and 7.

Some comment

This solution assumes that we know exactly what X is so that we can distinguish 5X from 2X from 1X and so on. But in reality this isn't true. After the first weighing we get a number for the difference, but we don't know whether this number is 1X or 4X or whichever.

[Guest]

give the piles numbers, 1 to 10

then take the piles No. 1,4,6 and 8

taking from pile No. 1..only one coin,from No. 4 ...4 coins,from pile No. 6...6 coins and from pile No. 8...8 coins.

if we find a (1X)difference,so the pile No. 1 is fake,

4X....No.4

5X...No. 1 and 4

6X..No.6

7X...No. 1 and 6

8X...No.8

9X...No. 1 and 8

10X ...No. 4 and 6

12X...No. 4 and 8

14X....No. 6 and 8

If the total wieght is 190gm,so(No. 1,4,6 and 8) are normal.

then we will make the second weight with the piles No.2,5.9 and 10,take:

2 coins from No. 2,,,5 coins from No. 5,,,9coins from No. 9 and 10 coins from pile No. 10.

If the difference is 2X.....No.2

5X...No. 5

7X...No. 2 and 5

9X...No. 9

11X...No. 2 and 9

10X....No. 10

12X...No. 2 and 10

14X...No. 5 and 9

15X...No. 5 and 10

19X...No. 9 and 10

But if the total weight was 260gm,so they are normal,and the fake piles will be No. 3 and 7.

How will you handle a situation if one single pile (say pile number 6) is found out from the 1st iteration and no pile is found from the 2nd iteration. In that case you would need a 3rd iteration to decide the fake piles among 6th, 3rd and 7th pile?

[Guest]

Weigh 1 from the first pile, 2 from the second pile, 3 from the third, etc up to 10 from the tenth.

Then

Weigh 1 from the tenth pile, 2 from the ninth pile, 3 from the 8th, etc down to 10 from the first pile.

Knowing that 8 of the piles have coins weighing 100 grams, you should be able to determine which piles have the heavier coins by doing a bit of algebra.

[Guest]

1st iteration: Weigh piles numbered 1, 3, 5, 7 and 9

Weight,

1 coin from pile # 1,

3 coins from pile # 3,

5 coin from pile # 5,

7 coin from pile # 7,

9 coin from pile # 9.

A difference of, 1X means pile # 1 is fake,

3X.... No.3

4X.... No.1 and 3

5X... No.5

6X… No.1 and 5

7X... No.7

8X... No.1 and 7 / No.3 and 5

9X... No.9

10X... No.1 and 9 / No.3 and 7

12X... No.5 and 7 / No.3 and 9

14X... No.5 and 9

16X… No.7 and 9

2nd iterations will depend on one of the 4 criteria as mentioned below:

1) If 2 piles of coins were found then no need of 2nd iteration (example: difference of 4X, 6X, 14X and 16X)

2) If 2 sets of 2 piles of coins (example: 8X...No.1 and 7 / No.3 and 5) were found then 2nd iteration would be like:

Take only one pile from each set like,

1 coin from pile # 1 (pile 1 represents set 1)

3 coins from pile # 3 (pile 3 represents set 2)

A difference of, 1X means pile # 1 is fake… in other words, the piles No.1 and 7 (1st set of 1st iteration)

A difference of, 3X means pile # 3 is fake… in other words, the piles No.3 and 5 (2nd set of 1st iteration)

3) If only one single pile of coin is found from 1st iteration, then 2nd iteration will determine the other fake pile of coins as:

Weigh piles numbered 2, 4, 6, 8 and 10

Weight,

1 coin from pile # 2,

3 coins from pile # 4,

5 coins from pile # 6,

7 coins from pile # 8,

9 coins from pile # 10

A difference of, 1X means pile # 2 is fake,

3X.... No.4

4X.... No.2 and 4

5X... No.6

6X… No.2 and 6

7X... No.8

8X... No.2 and 8 / No.4 and 6

9X... No.10

10X... No.2 and 10 / No.4 and 8

12X... No.6 and 8 / No.4 and 10

14X... No.6 and 10

16X… No.8 and 10

4) If there is no fake pile of coins from the 1st iteration, then 2nd iteration will be as follows:

Weigh piles numbered 2, 4, 6 and 8 (don’t weigh pile #10)

Weight, 1 coin from pile # 2,

4 coins from pile # 4,

6 coins from pile # 6,

8 coins from pile # 8,

A difference of, 1X means pile # 2 is fake,

4X.... No. 4

5X… No.2 and 4

6X... No.6

7X… No.1 and 6

8X... No.8

9X... No.1 and 8

10X... No.4 and 6

12X... No.4 and 8

14X... No.6 and 8

So, this iteration will result in 2 piles of fake coins. Else, if one pile of fake coins is found from 2nd iteration, then pile # 10 will be the 2nd pile of fake coins.

[bushindo]

1st iteration: Weigh piles numbered 1, 3, 5, 7 and 9

Weight,

1 coin from pile # 1,

3 coins from pile # 3,

5 coin from pile # 5,

7 coin from pile # 7,

9 coin from pile # 9.

A difference of, 1X means pile # 1 is fake,

3X.... No.3

4X.... No.1 and 3

5X... No.5

6X… No.1 and 5

7X... No.7

8X... No.1 and 7 / No.3 and 5

9X... No.9

10X... No.1 and 9 / No.3 and 7

12X... No.5 and 7 / No.3 and 9

14X... No.5 and 9

16X… No.7 and 9

2nd iterations will depend on one of the 4 criteria as mentioned below:

1) If 2 piles of coins were found then no need of 2nd iteration (example: difference of 4X, 6X, 14X and 16X)

2) If 2 sets of 2 piles of coins (example: 8X...No.1 and 7 / No.3 and 5) were found then 2nd iteration would be like:

Take only one pile from each set like,

1 coin from pile # 1 (pile 1 represents set 1)

3 coins from pile # 3 (pile 3 represents set 2)

A difference of, 1X means pile # 1 is fake… in other words, the piles No.1 and 7 (1st set of 1st iteration)

A difference of, 3X means pile # 3 is fake… in other words, the piles No.3 and 5 (2nd set of 1st iteration)

3) If only one single pile of coin is found from 1st iteration, then 2nd iteration will determine the other fake pile of coins as:

Weigh piles numbered 2, 4, 6, 8 and 10

Weight,

1 coin from pile # 2,

3 coins from pile # 4,

5 coins from pile # 6,

7 coins from pile # 8,

9 coins from pile # 10

A difference of, 1X means pile # 2 is fake,

3X.... No.4

4X.... No.2 and 4

5X... No.6

6X… No.2 and 6

7X... No.8

8X... No.2 and 8 / No.4 and 6

9X... No.10

10X... No.2 and 10 / No.4 and 8

12X... No.6 and 8 / No.4 and 10

14X... No.6 and 10

16X… No.8 and 10

4) If there is no fake pile of coins from the 1st iteration, then 2nd iteration will be as follows:

Weigh piles numbered 2, 4, 6 and 8 (don’t weigh pile #10)

Weight, 1 coin from pile # 2,

4 coins from pile # 4,

6 coins from pile # 6,

8 coins from pile # 8,

A difference of, 1X means pile # 2 is fake,

4X.... No. 4

5X… No.2 and 4

6X... No.6

7X… No.1 and 6

8X... No.8

9X... No.1 and 8

10X... No.4 and 6

12X... No.4 and 8

14X... No.6 and 8

So, this iteration will result in 2 piles of fake coins. Else, if one pile of fake coins is found from 2nd iteration, then pile # 10 will be the 2nd pile of fake coins.

Welcome to the den. This solution assumes that we know exactly what X is, so that we can distinguish between X, 2X, 3X, and so on. That is not true. We know that the odd coins are heavier than the normal coins, but we don't know how much heavier. Also, please put your solution in spoiler tags next time.

Also, apparently I mistyped the number of coin piles in this puzzle. There should be 9 piles (not 10 piles) of coins total, each pile with 10 coins. 7 piles are normal coins, and 2 piles are fake coins. The remaining parameters are the same. Sorry about that. That correction should make the puzzle a lot easier now.

[araver]

Also, apparently I mistyped the number of coin piles in this puzzle. There should be 9 piles (not 10 piles) of coins total, each pile with 10 coins. 7 piles are normal coins, and 2 piles are fake coins. The remaining parameters are the same. Sorry about that. That correction should make the puzzle a lot easier now.

Well for 9 piles, I have a solution that only requires 9 coins in each pile.

I did not find an ah-ha solution. My solution was to find two weighings which deterministically separate all the cases.

First, assume that each fake coin (which is heavier than 100g) has 100+X g. (where X>0).

X is unknown and we might not assume it is even an integer. However X should be a rational number and not very small as any attempt to measure it would only go as far as the precision of the scale goes. An ideal scale (which shows the weigh up to any digits necessary) is needed for the problem to be solved if X is arbitrary small or an irrational number.

Assuming an ideal scale in the following. There are 36 possible fake-pile arrangements.

First natural weighing is to take n coins from pile n, n=1..9.

The sum shown by the scale is S1=9*10/2*100+i*X+j*X where i and j are fake piles' numbers. Since X is also unknown you cannot know for sure what i and j are but you can deduce from S1 what (i+j)*X is. This is a multiple of X between 3*X and 17*X. There are 36 fake-pile arrangements cases which yield 15 possible multiples of X.

The next weighing would give you another sum S2. Let's say function f dictates the number of coins taken from each pile in this weighing. So 0<=f(i)<=9. Again, by subtracting 100*nr of coins taken, you again have a multiple of X which depends on f(i) and f(j).

The key to uniquely determine one of the 36 cases is to find a function f such that it separates the 36 possible cases into different multiples of X. More precisely if M1 = (i+j)*X and M2= (f(i)+f(j))*X, one should have 36 possible values for the ratio M2 / M1 (remember X>0 so M2/M1 only depends on f, i and j). Since M1 and M2 are known after the weighings, one can uniquely determine the case and afterwards the value of X.

One of the functions I found is:

n	1	2	3	4	5	6	7	8	9

f(n)	8	1	2	1	4	0	7	4	8

I found f by adaptively trying to separate different sums from weighing 1 in weighing 2 and checking the number of unique rations via a spreadsheet. This is why I said it's not an ah-ha solution, more of a constructive-sum-of-blind-shots-in-the-dark solution. For this function, the following table lists the 36 unique ratios M2/M1.

Pi	Pj	M1/X	M2/X	M2/M1

1	2	3	9	3

1	3	4	10	2,5

1	4	5	9	1,8

1	5	6	12	2

1	6	7	8	1,142857143

1	7	8	15	1,875

1	8	9	12	1,333333333

1	9	10	16	1,6

2	3	5	3	0,6

2	4	6	2	0,333333333

2	5	7	5	0,714285714

2	6	8	1	0,125

2	7	9	8	0,888888889

2	8	10	5	0,5

2	9	11	9	0,818181818

3	4	7	3	0,428571429

3	5	8	6	0,75

3	6	9	2	0,222222222

3	7	10	9	0,9

3	8	11	6	0,545454545

3	9	12	10	0,833333333

4	5	9	5	0,555555556

4	6	10	1	0,1

4	7	11	8	0,727272727

4	8	12	5	0,416666667

4	9	13	9	0,692307692

5	6	11	4	0,363636364

5	7	12	11	0,916666667

5	8	13	8	0,615384615

5	9	14	12	0,857142857

6	7	13	7	0,538461538

6	8	14	4	0,285714286

6	9	15	8	0,533333333

7	8	15	11	0,733333333

7	9	16	15	0,9375

8	9	17	12	0,705882353

I'm going to try the 10-pile 10-coins each variation of the puzzle and see if such an approach can lead to a solution (as I do not see any mathematical proof why it would not).

[araver]

And for the 10-piles, 2 fake, 10 coins in each pile variant:

There are 45 cases this time.

First weighing, same function (n coins from pile n, n=1..10)

1	2	3	4	5	6	7	8	9	10

1	2	3	4	5	6	7	8	9	10

Function for the second weighing

n	1	2	3	4	5	6	7	8	9	10

f(n)	8	9	2	1	4	0	7	4	8	10

For this function, the following table lists the 45 unique ratios M2/M1.

Pi	Pj	M1/X	M2/X	M2/M1

1	2	3	17	5,666666667

1	3	4	10	2,5

1	4	5	9	1,8

1	5	6	12	2

1	6	7	8	1,142857143

1	7	8	15	1,875

1	8	9	12	1,333333333

1	9	10	16	1,6

1	10	11	18	1,636363636

2	3	5	11	2,2

2	4	6	10	1,666666667

2	5	7	13	1,857142857

2	6	8	9	1,125

2	7	9	16	1,777777778

2	8	10	13	1,3

2	9	11	17	1,545454545

2	10	12	19	1,583333333

3	4	7	3	0,428571429

3	5	8	6	0,75

3	6	9	2	0,222222222

3	7	10	9	0,9

3	8	11	6	0,545454545

3	9	12	10	0,833333333

3	10	13	12	0,923076923

4	5	9	5	0,555555556

4	6	10	1	0,1

4	7	11	8	0,727272727

4	8	12	5	0,416666667

4	9	13	9	0,692307692

4	10	14	11	0,785714286

5	6	11	4	0,363636364

5	7	12	11	0,916666667

5	8	13	8	0,615384615

5	9	14	12	0,857142857

5	10	15	14	0,933333333

6	7	13	7	0,538461538

6	8	14	4	0,285714286

6	9	15	8	0,533333333

6	10	16	10	0,625

7	8	15	11	0,733333333

7	9	16	15	0,9375

7	10	17	17	1

8	9	17	12	0,705882353

8	10	18	14	0,777777778

9	10	19	18	0,947368421

[bushindo]

And for the 10-piles, 2 fake, 10 coins in each pile variant:

There are 45 cases this time.

First weighing, same function (n coins from pile n, n=1..10)

1	2	3	4	5	6	7	8	9	10

1	2	3	4	5	6	7	8	9	10

Function for the second weighing

n	1	2	3	4	5	6	7	8	9	10

f(n)	8	9	2	1	4	0	7	4	8	10

For this function, the following table lists the 45 unique ratios M2/M1.

Pi	Pj	M1/X	M2/X	M2/M1

1	2	3	17	5,666666667

1	3	4	10	2,5

1	4	5	9	1,8

1	5	6	12	2

1	6	7	8	1,142857143

1	7	8	15	1,875

1	8	9	12	1,333333333

1	9	10	16	1,6

1	10	11	18	1,636363636

2	3	5	11	2,2

2	4	6	10	1,666666667

2	5	7	13	1,857142857

2	6	8	9	1,125

2	7	9	16	1,777777778

2	8	10	13	1,3

2	9	11	17	1,545454545

2	10	12	19	1,583333333

3	4	7	3	0,428571429

3	5	8	6	0,75

3	6	9	2	0,222222222

3	7	10	9	0,9

3	8	11	6	0,545454545

3	9	12	10	0,833333333

3	10	13	12	0,923076923

4	5	9	5	0,555555556

4	6	10	1	0,1

4	7	11	8	0,727272727

4	8	12	5	0,416666667

4	9	13	9	0,692307692

4	10	14	11	0,785714286

5	6	11	4	0,363636364

5	7	12	11	0,916666667

5	8	13	8	0,615384615

5	9	14	12	0,857142857

5	10	15	14	0,933333333

6	7	13	7	0,538461538

6	8	14	4	0,285714286

6	9	15	8	0,533333333

6	10	16	10	0,625

7	8	15	11	0,733333333

7	9	16	15	0,9375

7	10	17	17	1

8	9	17	12	0,705882353

8	10	18	14	0,777777778

9	10	19	18	0,947368421

Nice solution. Clear and insightful as always.

[Guest]

First weighing:

Take Coins 1 2 3 4 5 6 7 8 9

Pile No 1 2 3 4 5 6 7 8 9

Second weighing:

Take Coins 8 6 4 2 1 3 5 10 7

Pile No 1 2 3 4 5 6 7 8 9

This will give you different ratio of extra weight in both weighing for all 36 combinations.

Similar should work for 10 piles also --- just saw Araver have already given the solution....

[Guest]

And for the 10-piles, 2 fake, 10 coins in each pile variant:

There are 45 cases this time.

First weighing, same function (n coins from pile n, n=1..10)

1	2	3	4	5	6	7	8	9	10

1	2	3	4	5	6	7	8	9	10

Function for the second weighing

n	1	2	3	4	5	6	7	8	9	10

f(n)	8	9	2	1	4	0	7	4	8	10

But why such arbit weights? What's the logic?

[Guest]

since there are 10 piles with 10 coins each, and each coin should ideally weight 100 gms...

weight all the coins together...

this would give you a weight of 10 Kg + some x*100 gms and hence you know the X that you were looking for...

once you know the X, rest is simple...