Welcome to NRICH.

 
The counterfeit coin problem
By Marcos Charalambides on Monday, August 26, 2002 - 07:47 pm:

I read somewhere that with n weighings you can pick out a bad coin (ie. one that is either heavier or lighter than the others - you don't know which) from (3n - 1)/2 coins...

(It's easy to see it works for n = 1, 2)
When n = 3, you can make an algorithm for 13 coins...

Well I was wondering:
(1) How can you prove that this is so, ie. with n weighings you can have up to (3n - 1)/2 coins... If someone knows I don't really want the whole proof just some hints to get me started...
(2) Has anyone published an algorithm for finding a bad coin in 40 with 4 weighings?

Thanks to anyone who replies :)

By Ian Short on Thursday, August 29, 2002 - 10:26 am:

Hi, I recently wrote an article on this with a fairly simple proof. There is quite a famous paper written about this problem (forgotten what it's called, I've got it somewhere) dealing with a very general case.

There are various factors to consider such as:

% Do you have to determine whether it is heavier or lighter (or just of a different weight)?

% Must you state precisely which coins you are going to weigh in advance, or can you chop and choose depending on previous results as you go?

If you are looking at finding whether it is heavier or lighter (as it seems you are) then
you can achieve (3n-1)/2 coins with an algorithm stated in advance provided you have a spare correct test coin (otherwise (3n-3)/2).
Try that with 13 coins.

The method is more or less this:

On each weighing, a coin is either in pan A, pan B or in neither (neither=0). So assign to each coin an n-tuple... something like (A,A,0,B,0,B) indicating which pan it is in at each weighing. Notice that if a coin was not weighed at all- (0,0,0,0,0) -then we'd know nothing about it and also that (A,0,B) is indistinguishable from (B,0,A). So there are 3n n-tuples; minus one for (0,0,0,0,0,0) and divide by 2 as we can pair tuples up with their indistinguishable `opposites'. The result of the n weighings is also an n-tuple and with it corresponds precisely one of the (3n-1)/2 coins.

That explanation was vague and incomplete but the ideas are in there. There are other methods that are more general and cover more cases (lots of counterfeit coins).

If I haven't been precise enough then tell me; this way provides an intuitive algortithm for all n cases including 4.

Ian

By Marcos Charalambides on Friday, August 30, 2002 - 08:03 am:

Ian,
Thanks for replying...

I like this idea a lot :) but there's one thing I don't really get and it's been bugging me (it may be something simple I'm not seeing, of course)...

"The result of the n weighings is also an n-tuple and with it corresponds precisely one of the (3n-1)/2 coins"

I don't really see how you can show that (at least) one of the (3n - 1)/2 coins' n-tuple corresponds to the result's.

By Ian Short on Friday, August 30, 2002 - 07:15 pm:

Hi, I'll explain what I had in mind by an example with 3 weighings. That's 13 coins with 3 tuples:

(A,0,0)
(0,A,0)
(0,0,A)
(A,A,O)
(A,B,0)
.......
(A,A,A)

or their equivalent partners. Now the result is something like "pan A heavier, pan B heavier and pans level". This corresponds to the coin with 3-tuple (A,B,0) (((or (B,A,0) ))) and it corresponds to no other. i.e. by the result being an n-tuple I meant let the first component of the 'result' be A if A is heavier and B if B is heavier and so on.

Once I have tidied up the article (I was working on it with someone else) I could show you it if you're interested, or maybe I'll put it somewhere on nrich. The person I'm writing it with currently specialises in maths education so it is (hopefully) fairly readable!

I meant to look up the detailed article on the problem, sorry- forgot to, it's in Cambridge and I'm in London. I'll do it when I go back- it's clever but boring to read, not at all illuminating proof.

By the way, just to clarify further concerning your last sentence; the idea is that PRECISELY one of the n-tuples corresponds to the result (not 'at least one'). Tell me if this is not coming across.

Ian

By Ian Short on Saturday, August 31, 2002 - 06:20 pm:

Hey Marcos,

Probably a good way to think about it is the 4 case. So you select different combinations of coins in 4 weighings and get a 4 tuple as a result; something like (H,H,L,E) ((i.e. pan A heavier,pan A heavier, pan B heavier, even)). This must mean that either the fake coin was too heavy and had 4-tuple (A,A,B,0) or was too light and had 4-tuple (B,B,A,0). Try considering this 4 case and the different possiblities.

Okay, that wasn't too helpful :) All the best,

Ian

By Marcos Charalambides on Sunday, September 01, 2002 - 02:50 pm:

Well...
I think I do understand what you're getting at although as I already said I need to think things through to understand it properly (I still don't really :))
Basically your idea rests on the fact that each possible combination of H/L/E ie. each n-tuple has one and only one coin's n-tuple corresponding to it (if I've understood correctly :))... But I don't really see how you can show (or see) that one of the n-tuples must actually be a solution...

Thanks,

By Ian Short on Sunday, September 01, 2002 - 03:39 pm:

To stick with the 4-case (if you understand this then the rest similar), then I give a particular coin the 4-tuple (B,0,A,0) if on the 2nd and 4th weighings it is not weighed and on the 1st and 3rd weighings, it's in pans B and A respectively.

Obviously there are 34 possible 4-tuples (ways in which we can place the coin). They are:

(A,A,A,A)
(A,A,A,B)
(A,A,B,A)
.........
(0,0,0,0)

Now the result can also be considered as a 4-tuple. Suppose it is (H,L,0,L), with H meaning pan A heavier etcetera. Try and consider which 4-tuple coins could possibly have this result. Well, on the 3rd weighing it must have been left out. Furthermore, if it was in A on the 1st weighing then it must have been in B on the 2nd and 4th, i.e. (a,b,0,b). This 4-tuple is present- we have enough coins to cover ALL 4-tuples so it must be.

Ian