Another coin weighing riddle

Given are 12 coins. One is a fake, and it can be either heavier or lighter than the authentic coin. Also given is a scale with two cups (no weights). How many weighings do you need to guaranteed find the fake?

Six. I'm probably wrong..show it to me.

Six to spot an unbalanced pair, and a seventh to locate on which side of the balance the imposter exists.

Quote: weaselman

Given are 12 coins. One is a fake, and it can be either heavier or lighter than the authentic coin. Also given is a scale with two cups (no weights). How many weighings do you need to guaranteed find the fake?

First weighing, place two and two, if balanced repeat. If not proceed.

Weigh second two and two, if balanced take the other four, if unbalanced take that four.


That is TWO weighings.



Now weigh any one and one. If balanced place aside, if unbalanced take the other two, one of which is fake.


That is three weighings.


Take one of the suspect coins and balance with any other coin. If it is unbalanced the coin from the suspect set is the fake coin, if not the other one ie.


FOUR WEIGHINGS.

The best I can do is 4. Something tells me there's still a shorter solution though...

I get three if you know in advance the fake is heavier (or lighter)...

Name the coins a,b,c,d,e,f,g,h,i,j,k,l.

Weigh abcd against efgh. If those values not equal, then 2 more weighings (going halvsies) will get it from the heavier of abcd and efgh. Otherwise, if they are equal, then you know it's one of ijkl and two more weighings will get it from that grouping.

--Dorothy

Three. I'll hold off on posting my answer for a spell.

Three is the right answer. No, you don't know if it is heavier.

Quote: waltomeal

Three. I'll hold off on posting my answer for a spell.

If the coins are a,b,c,d,e,f,g,h,i,j,k,l, then:

1) Weigh abhi against cdej and note if you get >, =, or <.
2) Then weigh achk against bfgi and note if you get >, =, or <.
3) Then weigh bceg against adfl and note if you get >, =, or <.

Keep track of the sequence of three symbols <,=,> that occurs from these three weighings ...

I figured it out by realizing I had an alphabet with three symbols, {<,=,>} and I could create a total of 27 words ... just enough to handle uniquely identifying 24 possibilities.

The missing words are =,=,=, and >,>,> and <,<,<.

Here are the words that should be weighed against each other ... and the key that maps the results of these three weighings to the coin that is heavy (+) or light(-).



Yes .... done is done is done ... about 45 minutes to get this ...

Thanks!!!

--Dorothy

Wow. Very persistent :) Seems like a right solution too :)
The one I know is a little shorter when put in words (but still three weightings total):

1. Separate coins into three groups of four, and compare two groups.
1.1 If they weigh the same, fake is in the remaining four. Pick any three of them, and compare with any three good ones.
1.1.1 If they weigh the same, fake is the last one still not weighed, you are done (there is still one weighting left, so you can tell if it is heavier or lighter too, if you want).
1.1.2 If the three suspects are lighter (heavier). Compare any two of them between themselves: if two coins weigh the same, then fake is the third suspect, otherwise its the one that's lighter(heavier). Done.

1.2 If one of the initial groups is heavier, take three coins off that cup, and replace them with three coins, taken from the other cup, which are in turn replaced with three coins from the third group.
1.2.1. If this balances the scale, then the fake is one of the three removed coins, and it is heavier than the original.
Compare any two of them, and pick the heavier one, or if they weigh the same, pick the third one. Done.
1.2.2. If this reverses the scale, then the fake is one of the three coins moved, and it is lighter. Do the same weighting as in 1.2.1., except pick the lighter one, not the heavier one.
1.2.3. If the balance does not change, then the fake is one of the two coins that stayed put. Compare either of them with any of the good ones - if the weigh the same, then fake is the other one left, otherwise it's the one being weighed.

Quote: weaselman

Wow. Very persistent :) Seems like a right solution too :)
The one I know is a little shorter when put in words (but still three weightings total)...

You know, that's fairly straightforward, but I don't like it because it is not generalizable. Here's what I mean.

I created 24 words out of 27 using strings of length 3 and the alphabet <, >, and =. Now, using strings of length 4 in this alphabet we get 81 possibilities. The ones that are not valid are still ====, >>>>, and <<<<. The others are valid (or so I think). Thus, since we have to decide heavier or lighter for each coine ...

You have 39 coins, one of which is a fake. How many weighings does it take to determine the fake, and if it is lighter or heavier? Answer (probably) is 4.

Or ... in general, (3^n-3)/2 coins takes n weighings.

--Dorothy

What if you took a suspect coin and asked "What would the other coins tell me if I asked whether you're the fake coin?" :P

Quote: DorothyGale

You know, that's fairly straightforward, but I don't like it because it is not generalizable. Here's what I mean.

Yes, that is a nice thing about your solution. However, to be truly generalizable, it also needs an algorithm of breaking N coins into groups, and interpreting the "words" in terms of which coin is actually a fake.

So far, I am afraid, it is no more generic than mine, but, I agree, it has a better potential :)

Quote: weaselman

Yes, that is a nice thing about your solution. However, to be truly generalizable, it also needs an algorithm of breaking N coins into groups, and interpreting the "words" in terms of which coin is actually a fake.

So far, I am afraid, it is no more generic than mine, but, I agree, it has a better potential :)

I have that algorithm, I used it to arrived at my three groupings of four-four. It is quite easy ... why don't you give it a try ...

--Dorothy