Fourteen coins
Arjun Shastry
Ranch Hand
Posts: 1903
1
Arjun Shastry
Ranch Hand
Posts: 1903
1
Misha Ver
Ranch Hand
Posts: 470
Ryan McGuire
Ranch Hand
Posts: 1108
7
posted 7 years ago
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?
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?
Arjun Shastry
Ranch Hand
Posts: 1903
1
posted 7 years ago
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/MathematicalCirclesRussianExperienceWorld/dp/0821804308
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/MathematicalCirclesRussianExperienceWorld/dp/0821804308
MH
Misha Ver
Ranch Hand
Posts: 470
posted 7 years ago
These are two completely different puzzles The former has not solution, but the latter has.
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.
posted 7 years ago
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.
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.
Arjun Shastry
Ranch Hand
Posts: 1903
1
Mike Simmons
Ranch Hand
Posts: 3090
14
posted 7 years ago
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
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
Misha Ver
Ranch Hand
Posts: 470
Misha Ver
Ranch Hand
Posts: 470
posted 7 years ago
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.
This of course assumes that all bad coins weigh the same. And that all good coins weigh the same.
W. Joe Smith
Ranch Hand
Posts: 710
posted 7 years ago
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?
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."
Jim Yingst
Wanderer
Sheriff
Sheriff
Posts: 18671
posted 7 years ago
Yeah, I was considering scalebased solutions back when we had the original, misstated version of the problems. (It's still demonstrably impossible in three weighings, for that version of the problem.) However you've added the assumption that the weight of a real coin is known, without weighing. I'm not sure that's valid.
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.
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
Jim Yingst
Wanderer
Sheriff
Sheriff
Posts: 18671
posted 7 years ago
No, that was the original, misstated version of the problem. It's impossible in 3 weighings. Arjun posted the corrected version on November 25/26:
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, misstated 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/MathematicalCirclesRussianExperienceWorld/dp/0821804308
"I'm not back."  Bill Harding, Twister
W. Joe Smith
Ranch Hand
Posts: 710
posted 7 years ago
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!
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, misstated 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/MathematicalCirclesRussianExperienceWorld/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."
Jim Yingst
Wanderer
Sheriff
Sheriff
Posts: 18671
posted 7 years ago
Maybe it's a little late to return to this, but it occurred to me that, under Steve's assumptions, 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 3weighingswithabalance version of the problem much more rewarding.
Hm, I find the 3weighingswithabalance version of the problem much more rewarding.
"I'm not back."  Bill Harding, Twister
rutuja patil
Greenhorn
Posts: 23
posted 7 years ago
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...
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...
Ryan McGuire
Ranch Hand
Posts: 1108
7
posted 7 years ago
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.
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.
Jim Yingst
Wanderer
Sheriff
Sheriff
Posts: 18671
posted 7 years ago
I agree with Ryan of course. Also:
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.
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
Gravity is a harsh mistress. But this tiny ad is pretty easy to deal with:
the new thread boost feature: great for the advertiser and smooth for the coderanch user
https://coderanch.com/t/674455/ThreadBoostfeature
