- Post Reply Bookmark Topic Watch Topic
- New Topic

programming forums
Java
Mobile
Certification
Databases
Caching
Books
Engineering
Micro Controllers
OS
Languages
Paradigms
IDEs
Build Tools
Frameworks
Application Servers
Open Source
This Site
Careers
Other
all forums

this forum made possible by our volunteer staff, including ...

Marshals:

- Campbell Ritchie
- Liutauras Vilda
- Jeanne Boyarsky
- Devaka Cooray
- Paul Clapham

Sheriffs:

- Tim Cooke
- Knute Snortum
- Bear Bibeault

Saloon Keepers:

- Ron McLeod
- Tim Moores
- Stephan van Hulst
- Piet Souris
- Ganesh Patekar

Bartenders:

- Frits Walraven
- Carey Brown
- Tim Holloway

posted 9 years ago

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).

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).

MH

posted 9 years ago

Interesting. It's a variation on the popular 12 coins problem, where only one is counterfeit, but you don't know if it's lighter or heavier. That one can also be solved in three weighings on a balance type scale where you weigh one set against another to see which is heavier.

Arjun Shastry

Ranch Hand

Posts: 1907

1

posted 9 years ago

yes. There is nine coins problem also.Coin may be lighter or heavier.In two weighings, we need to find counterfeit coin.

But 14 coins problems really seems to be tough.I am trying it for long time.

But 14 coins problems really seems to be tough.I am trying it for long time.

MH

posted 9 years ago

Arjun, it has been lost in translation. There are no solution for the puzzle as you described.

posted 9 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: 1907

1

posted 9 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/Mathematical-Circles-Russian-Experience-World/dp/0821804308

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

Misha Ver

Ranch Hand

Posts: 470

posted 9 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 9 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: 1907

1

posted 9 years ago

Problem says it has to be done in three weighings. Problem is marked as difficult.

MH

posted 9 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

posted 9 years ago

It can be done in 2 weighings

Misha Ver

Ranch Hand

Posts: 470

posted 9 years ago

At least three. There is another solution. The first step could be to prove that HHHHHHH > LLLLLLL, and the remaining two to prove that each of HHHHHHH have the same weight.

Steve Fahlbusch wrote:It can be done in 2 weighings

At least three. There is another solution. The first step could be to prove that HHHHHHH > LLLLLLL, and the remaining two to prove that each of HHHHHHH have the same weight.

posted 9 years ago

Given the problem statement, it can be done in 2

Misha Ver

Ranch Hand

Posts: 470

posted 9 years ago

I don't see solution in 2 weightings. Could you explain?

Steve Fahlbusch wrote:Given the problem statement, it can be done in 2

I don't see solution in 2 weightings. Could you explain?

posted 9 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.

posted 9 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."

posted 9 years ago

Yeah, I was considering scale-based 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

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

Jim Yingst

Wanderer

Posts: 18671

posted 9 years ago

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:

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*

W. Joe Smith

Ranch Hand

Posts: 710

posted 9 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, 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!

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

Posts: 18671

posted 9 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 3-weighings-with-a-balance version of the problem much more rewarding.

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

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

posted 9 years ago

Jim,

I was waiting for this.

I do agree with you - the balance beam is much more engaging.

-- have yourself a great weekend

-steve

I was waiting for this.

I do agree with you - the balance beam is much more engaging.

-- have yourself a great weekend

-steve

posted 9 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: 1168

11

posted 9 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

Posts: 18671

posted 9 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*

Consider Paul's rocket mass heater. |

- Post Reply Bookmark Topic Watch Topic
- New Topic

Boost this thread!