File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Programming Diversions and the fly likes Fourteen coins Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of OCA/OCP Java SE 7 Programmer I & II Study Guide this week in the OCPJP forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Fourteen coins" Watch "Fourteen coins" New topic
Author

Fourteen coins

Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1874
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).



MH
Greg Charles
Sheriff

Joined: Oct 01, 2001
Posts: 2854
    
  11

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

Joined: Mar 13, 2003
Posts: 1874
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.

Misha Ver
Ranch Hand

Joined: Mar 03, 2008
Posts: 470
Arjun, it has been lost in translation. There are no solution for the puzzle as you described.
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1012
    
    3
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

Joined: Mar 13, 2003
Posts: 1874
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
Misha Ver
Ranch Hand

Joined: Mar 03, 2008
Posts: 470
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.

Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18708
    
    8

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

Joined: Mar 13, 2003
Posts: 1874
Problem says it has to be done in three weighings. Problem is marked as difficult.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10


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
Steve Fahlbusch
Bartender

Joined: Sep 18, 2000
Posts: 575
    
    7

It can be done in 2 weighings
Misha Ver
Ranch Hand

Joined: Mar 03, 2008
Posts: 470
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.

Steve Fahlbusch
Bartender

Joined: Sep 18, 2000
Posts: 575
    
    7

Given the problem statement, it can be done in 2
Misha Ver
Ranch Hand

Joined: Mar 03, 2008
Posts: 470
Steve Fahlbusch wrote:Given the problem statement, it can be done in 2


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

Joined: Sep 18, 2000
Posts: 575
    
    7

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.
W. Joe Smith
Ranch Hand

Joined: Feb 10, 2009
Posts: 710
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

Joined: Jan 30, 2000
Posts: 18671
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.

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

Joined: Jan 30, 2000
Posts: 18671
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
W. Joe Smith
Ranch Hand

Joined: Feb 10, 2009
Posts: 710
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!
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
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.
Steve Fahlbusch
Bartender

Joined: Sep 18, 2000
Posts: 575
    
    7

Jim,

I was waiting for this.

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

-- have yourself a great weekend

-steve
rutuja patil
Greenhorn

Joined: Dec 17, 2009
Posts: 23
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...
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1012
    
    3
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

Joined: Jan 30, 2000
Posts: 18671
I agree with Ryan of course. Also:
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.
Vinod Tiwari
Ranch Hand

Joined: Feb 06, 2008
Posts: 459
    
    1
I also get it as 3...


Vinod Tiwari | Twitter
 
Consider Paul's rocket mass heater.
 
subject: Fourteen coins