# find the counterfeit by minimum number of weighings

• Sep 8th 2010, 01:59 AM
tsang
find the counterfeit by minimum number of weighings

You have 10 stacks of coins, each consisting of 10 \$1 coins. One entire stack is counterfeit, but you don't know which one. You do know the weight of a genuine \$1 coin and you are also told that each counterfeit coin weighs 1 gram more than it should. You may weigh the coins on a pointer scale (ie not a set of scales with two dishes). What is the smallest number of weighings needed to determine which stack is counterfeit?

My current answer is 4 times. I will seperate 10 stacks become 4, 4, 2.
Then weigh 4, and 4, but not 2. If two 4 stacks are equal, then counterfeit is in 2.
If not, the heavier 4 will be the one contains counterfeit.
Then, seperate this heavier one become 2 and 2. Only weigh one of them, if yes, this one contains counterfeit, if not, the other one contains.
Then weigh only 1 of 2 for the one contains counterfeit, that will find the counterfeit.

So totally I weighed 4 times, will it be possible even less than 4? Thanks a lot.
• Sep 8th 2010, 04:15 AM
Wilmer
Doesn't a pointer scale indicate the weight on the scale?
The way you're trying to solve indicates the use of a set of scales with two dishes;
but problem states that's not allowed!

Anyway, IF a regular weigh scale is allowed, ONLY one weighing is required.
Like, if regular coins weigh 10 (then the counterfeit = 11), if you put one from
each stack on the scale, the scale will indicate 101 (9 *10 + 11).
• Sep 8th 2010, 04:24 AM
tsang
Quote:

Originally Posted by Wilmer
Doesn't a pointer scale indicate the weight on the scale?
The way you're trying to solve indicates the use of a set of scales with two dishes;
but problem states that's not allowed!

Anyway, IF a regular weigh scale is allowed, ONLY one weighing is required.
Like, if regular coins weigh 10 (then the counterfeit = 11), if you put one from
each stack on the scale, the scale will indicate 101 (9 *10 + 11).

The question actually means just simply find the one STACK which is counterfeit. You are right that is the scale which only can show one figure, which means cannot weigh two things at once to compare them.
Besides, the stack should not be seperated. In other words, the question has no difference if I change it become "there are 10 coins, one of them weighs heavier, find that one by one regular scale, find the minimum number of ways to weigh them and find the counterfeit". I posted the question as "Stack" is because this was original question.

• Sep 8th 2010, 05:42 AM
Wilmer
Ok; then your problem should be worded this way:
You have 10 stacks of coins, each consisting of 10 \$1 coins.
One entire stack is counterfeit, but you don't know which one.
You do know that the weight of a genuine \$1 coin is 10 grams. ***
And you are also told that each counterfeit coin weighs 11 grams.
You may weigh the coins on a pointer scale (ie a scale that shows the actual weight).
What is the smallest number of weighings needed to determine which stack is counterfeit?
*** I used 10, but could be any weight you choose; does not matter since counterfeit is 1 more.

Answer: ONLY one weighing is necessary.
Number the stacks 1 to 10.
Take 1 from stack1, 2 from stack2, ......,8 from stack8, 9 from stack9 (none from stack10).
So you have 45 coins on scale (1+2+...+8+9 = 45).
If weight = 450 then counterfeit = stack10
If weight = 451 then counterfeit = stack1
If weight = 452 then counterfeit = stack2
.....
If weight = 458 then counterfeit = stack8
If weight = 459 then counterfeit = stack9

Got that?
• Sep 8th 2010, 05:48 AM
tsang
Quote:

Originally Posted by Wilmer
Ok; then your problem should be worded this way:
You have 10 stacks of coins, each consisting of 10 \$1 coins.
One entire stack is counterfeit, but you don't know which one.
You do know that the weight of a genuine \$1 coin is 10 grams. ***
And you are also told that each counterfeit coin weighs 11 grams.
You may weigh the coins on a pointer scale (ie a scale that shows the actual weight).
What is the smallest number of weighings needed to determine which stack is counterfeit?
*** I used 10, but could be any weight you choose; does not matter since counterfeit is 1 more.

Answer: ONLY one weighing is necessary.
Number the stacks 1 to 10.
Take 1 from stack1, 2 from stack2, ......,8 from stack8, 9 from stack9 (none from stack10).
So you have 45 coins on scale (1+2+...+8+9 = 45).
If weight = 450 then counterfeit = stack10
If weight = 451 then counterfeit = stack1
If weight = 452 then counterfeit = stack2
.....
If weight = 458 then counterfeit = stack8
If weight = 459 then counterfeit = stack9

Got that?

I think you are a genius.....
• Sep 8th 2010, 05:54 AM
Unknown008
If I understand well...

I would have gone through the 'middle' number, that is weight 5 stacks. (1st)
Then, I divide into 3 and 2 stacks (the group containing the counterfeit coins) weighing the 3 stacks. (2nd)
If it is heavier than expected, then I'll divide into 2, then 1 if necessary (3rd and/or 4th)

If it is lighter, I proceed with the two remaining stacks, dividing them into 1 stack. (3rd)

So I get a maximum of 4 weightings as well, with a minimum of 3 weightings if you are lucky.

I don't think there is less than that and I think we should consider all possibilities, which make 4 weightings the minimum to be 100% sure which is the counterfeit stack of coins.

EDIT: Nope, see above post.
• Sep 8th 2010, 07:41 AM
Wilmer
Quote:

Originally Posted by tsang
I think you are a genius.....

Not really...I was aware of this "old puzzle"; only thing I can take credit
for is not taking any from stack#10; published solutions put the whole
stack on the scale, so that 460 = stack#10.