Arjun Shastry wrote:This puzzle I got in in Russian Math book.

There are 14 coins. Seven of them are counterfeit and are lighter than genuine ones.All counterfeit coins are of equal weight.

In only three weighings, you have to find which seven coins are counterfeit(lighter).

Assumptions: My balance is the classic double pan balance. With any one weighing, I will get one of only three possible readings: the left side is heavier, the right side is heavier or they are of equal weight. More specifically, I can NOT tell by how much one side is heavier than the other. Also, I don't know going into this by what percentage of a correct the counterfeits are light. i.e. I don't know that the counterfeits are exactly 80% of the correct weight.

If those assumptions hold, I don't see how the problem can possibly be done.

I'll weigh one set of coins against another and get one of three outcomes. Given that result, I'll do another weighing, again giving me one of three results. Simiarly, the last weighing will give me one of three. This means that I can have at most 3x3x3 = 27 different results. Seven coins can be selected out of a group of 14 in 14!/(7! 7!) = 3432 ways. I don't see how three weighings that can yield only three possible results each can possibly lead to the 3432 different conclusions.

...or am I missing something in the problem statement?

**Fourten coins were represented in a court as evidence.The judge knows that exactly 7 of these are counterfeit and weigh less than genuine coins.A lawyer claims to know which coins are counterfeit and which are genuine and she is rquired to prove it.**

How can she accomplish this using only three weighings?

How can she accomplish this using only three weighings?

Taken from this book- http://www.amazon.com/Mathematical-Circles-Russian-Experience-World/dp/0821804308

MH

Arjun Shastry wrote:There are 14 coins. Seven of them are counterfeit and are lighter than genuine ones.All counterfeit coins are of equal weight.

In only three weighings, you have to find which seven coins are counterfeit(lighter).

Arjun Shastry wrote:I also think whether it has any solution.This is the exact problem statement-(I made mistake by saying all lighter coins weigh same)

Fourten coins were represented in a court as evidence.The judge knows that exactly 7 of these are counterfeit and weigh less than genuine coins.A lawyer claims to know which coins are counterfeit and which are genuine and she is required to prove it.

How can she accomplish this using only three weighing?

These are two completely different puzzles The former has not solution, but the latter has.

Misha Ver wrote:These are two completely different puzzles The former has not solution, but the latter has.

Aha... so the problem really is: You know which seven coins are counterfeit to start with, and you have to demonstrate that using only three weighings. Obviously you could take a counterfeit coin and a good coin, put them on the scales, and point to the counterfeit one. But you'd have to repeat that seven times to complete the trivial solution.

Rather than talking about real vs. counterfeit, I find it easier to think about heavy vs light. I will use the following notation:

h: a heavy coin that has not yet been proven to be heavy

l: a light coin that has not yet been proven to be light

H: a coin that has been proven to be heavy

L: a coin that has been proven to be light

So if I write something like

(hl) | (HL)

I mean the left side of the balance has two coins, one heavy and one light, neither proven to the judge. And the right side has two coins, one heavy and one light, both proven to the judge.

----

Weighing 1: Lawyer places one heavy against one light:

(h) | (l)

The left side goes down. The judge accepts that the left coin is heavy, and the right is light. So these coins become:

(H) | (L)

----

Weighing 2: Lawyer places two new heavies next to the known light, and two new lights next to the known heavy:

(Hll) | (Lhh)

The right side goes down. The judge knows that since there was already a heavy on the left and a light on the right, for the right side to go down is only possible if the new coins are all light on the left, and heavy on the right. So this becomes.

(HLL) | (LHH)

----

Weighing 3: Lawyer rearranges the proven coins, and adds all remaining coins thus:

(HHHllll) | (LLLhhhh)

Right side goes down. Judge knows that, given the known coins, this is only possible if all the unproven coins on the right were heavy, and all the unproven coins on the left were light. So this becomes:

(HHHLLLL) | (LLLHHHH)

----

QED

This of course assumes that all bad coins weigh the same. And that all good coins weigh the same.

Steve Fahlbusch wrote:It is only assumed that we weigh coins against each other on a balance scale. What if we simply have a spring scale. Since the lawyer would have to place the weight of a genuine coin into evidence, the weigh 1 counterfit - show that it is less than the official published weight of a genuine code. Then weigh all 7 counterfit coins. If it is seven times the one, we have proven that we know which are the seven good / bad coins.

This of course assumes that all bad coins weigh the same. And that all good coins weigh the same.

1st weighing: Get standard coin weight

2nd weighing: Get counterfeit coin weight

This would take far more than 2 weighings. 3 weighings if you already knew which ones were counterfeit, but I thought the assumption was you didn't know which ones were counterfeit, so you were weighing them to find out?

SCJA

When I die, I want people to look at me and say "Yeah, he might have been crazy, but that was one zarkin frood that knew where his towel was."

Steve Fahlbusch wrote:This of course assumes that all bad coins weigh the same. And that all good coins weigh the same.

Yea, I think all solutions will require this assumption. Otherwise it's extremely hard to prove

*anything*unless you use a lot more than three weighings.

"I'm not back." - Bill Harding, *Twister*

Sheriff

W. Joe Smith wrote:I thought the assumption was you didn't know which ones were counterfeit, so you were weighing them to find out?

No, that was the original, mis-stated version of the problem. It's impossible in 3 weighings. Arjun posted the corrected version on November 25/26:

Arjun Shastry wrote:I also think whether it has any solution.This is the exact problem statement-(I made mistake by saying all lighter coins weigh same)

Fourten coins were represented in a court as evidence.The judge knows that exactly 7 of these are counterfeit and weigh less than genuine coins.A lawyer claims to know which coins are counterfeit and which are genuine and she is rquired to prove it.

How can she accomplish this using only three weighings?

Taken from this book- http://www.amazon.com/Mathematical-Circles-Russian-Experience-World/dp/0821804308

"I'm not back." - Bill Harding, *Twister*

Jim Yingst wrote:

W. Joe Smith wrote:I thought the assumption was you didn't know which ones were counterfeit, so you were weighing them to find out?

No, that was the original, mis-stated version of the problem. It's impossible in 3 weighings. Arjun posted the corrected version on November 25/26:

Arjun Shastry wrote:I also think whether it has any solution.This is the exact problem statement-(I made mistake by saying all lighter coins weigh same)

Fourten coins were represented in a court as evidence.The judge knows that exactly 7 of these are counterfeit and weigh less than genuine coins.A lawyer claims to know which coins are counterfeit and which are genuine and she is rquired to prove it.

How can she accomplish this using only three weighings?

Taken from this book- http://www.amazon.com/Mathematical-Circles-Russian-Experience-World/dp/0821804308

Ah, my mistake. I misread, thought it said they knew there were 7 counterfeit coins. Missed the part about know which ones were counterfeit.

Time to go work on my reading comprehension!

SCJA

When I die, I want people to look at me and say "Yeah, he might have been crazy, but that was one zarkin frood that knew where his towel was."

Sheriff

*one*weighing is sufficient to identify the counterfeits. Just weigh the seven genuine coins, and we see that the weight is exactly what we'd expect for seven genuine coins. Thus, the remaining seven coins must be counterfeit. So hey - why waste a second weighing when one is sufficient?

Hm, I find the 3-weighings-with-a-balance version of the problem much more rewarding.

"I'm not back." - Bill Harding, *Twister*

and you said-"Thus, the remaining seven coins must be counterfeit", no, they might be counterfeit, they might contain some genuine coins, you can not say'must' without weighing remaining seven coins...

rutuja patil wrote:Jim, what if they don't know the exact weight... then will they need two weighings?

and you said-"Thus, the remaining seven coins must be counterfeit", no, they might be counterfeit, they might contain some genuine coins, you can not say'must' without weighing remaining seven coins...

It's part of the problem statement that we know there are exactly 7 real coins and 7 counterfeits. If we can identify the 7 genuine coins in one weighing, then the other 7 MUST be the counterfeits.

Sheriff

rutuja patil wrote:Jim, what if they don't know the exact weight... then will they need two weighings?

No, three. See the solution posted by Mike. Misha also claims there is another solution with three weighings - I expect that's true. There are probably multiple solutions with three weighings. But if you don't know the weight of a real coin or a counterfeit coin in advance, you can't get a better solution than three weighings - even if the weighings are done with a spring scale rather than a balance.

"I'm not back." - Bill Harding, *Twister*

It is sorta covered in the JavaRanch Style Guide. |