6
$\begingroup$

A stack of 12 coins that looks identical are to be tested for the unusual one which become slightly lighter on one face and slightly heavier on the other face. If it is weighed standing on its side, it is one gram like other normal coins. A certain weighing scale is available for use.

How many weighings will it take to find the odd coin?

$\endgroup$
8
  • 3
    $\begingroup$ how can a coin weigh differently on different faces? That doesn't make sense. $\endgroup$
    – MMAdams
    Commented Oct 17, 2016 at 19:45
  • 2
    $\begingroup$ @MMAdams Assume it's a magic coin. Or you're doing the whole experiment in the presence of a strong vertically-aligned magnetic field, and the odd coin is magnetized with one face north and the other south. $\endgroup$
    – Gareth McCaughan
    Commented Oct 17, 2016 at 19:47
  • 1
    $\begingroup$ Is the weighing scale a two-pan balance or a digital scale? $\endgroup$ Commented Oct 17, 2016 at 19:47
  • 1
    $\begingroup$ @MikeEarnest-digital or analog as long as it reads grams units $\endgroup$
    – TSLF
    Commented Oct 17, 2016 at 20:05
  • 3
    $\begingroup$ @MMAdams The coin might be ferromagnetic (they usually aren't) and be a weak magnet, then it would react to external magnetic fields. If you're at a high lattitude, so that the vertical compound of the Earth's magnetic field is significant, the coin may get a measurable additional vertical force added to or substracted from its actual weight, depending on the face. $\endgroup$
    – CiaPan
    Commented Oct 18, 2016 at 7:24

7 Answers 7

4
$\begingroup$

If I've understood correctly, the tool we have is not a balance scale as in the traditional 12-coins puzzle but a weighing scale that tells you (say) how many grammes the coins you put on it weigh in total. The question doesn't make clear whether we're supposed to know the "standard" weight of the coins. I'll address both the version of the question where we do know this, and the version where we don't.

If we do know the nominal weight of the coins

Given that only one coin is odd, and that we know how many coins we're weighing on any given occasion, what the scale tells us is exactly the following: Is the odd coin on the scale or not, and if so is it heavy or light?

Therefore

each such weighing gives us at most three different results, and after the first (if any) whose result isn't "odd coin not on scale" the heavy-or-light information tells us nothing new. I think a counting argument then indicates that we must take at least four weighings.

Now,

label the coins A..L and keep them a consistent way up throughout. First weigh ABCDEF. If the odd coin is not among their number, we now have GHIJKL to assess in three weighings. Now weigh GHIJ. If the odd coin isn't one of these then it's either K or L; weigh them separately. Done in four weighings. On the other hand, if weighing GHIJ indicates that the odd coin is one of them, it also tells us whether it's heavy or light. Weigh GH, and then either G or I depending on the result. Done, again, in four weighings.

On the other hand,

if the odd coin is one of ABCDEF then we can do to them what we did above to GHIJKL (we don't even need to use our knowledge of whether the odd coin is heavy or light). Done, again, in four weighings.

If we don't know the nominal weight of the coins

Still keeping all coins a consistent way up unless stated otherwise, first weigh ABCD and EFGH (two weighings). If they come out the same then the odd coin is one of IJKL and we now know the nominal weight of a coin. Weigh IJK. If it comes out right then L is the odd coin and one more weighing will tell us which way it's wrong. If not then we know, say, that one of IJK is too heavy. Now weigh I plus J-upside-down. If this is heavy then I is odd; if light then J; if neither then K. Done in four weighings.

On the other hand,

if ABCD and EFGH gave different results then call them $x$ and $y$ where, let's say, $x>y$. Then write $\delta=x-y$; we know that either normal coins weigh $y/4$ and one of ABCD weighs $y/4+\delta$, or else normal coins weigh $x/4$ and one of EFGH weighs $x/4-delta$. Turn EFGH the other way up, so now the odd coin definitely weighs $\delta$ "too much", and weigh ABCEFG. If the odd coin is in ABC, this will weigh $6y/4+\delta$; if in EFG, it will weigh $6x/4+\delta$; in either case we can now weigh A plus B-upside-down or E plus F-upside-down as in the solution to the nominal-weight-known problem given above. Done, again, in four weighings.

Finally,

if the odd coin is D or H, then ABCEFG will have weighed either $6x/4$ or $6y/4$ depending on which, so now we're actually done after only three weighings.

So

even if we don't know the nominal weight of the coins, we can identify the odd coin and which way up it goes with at most four weighings.


[What follows was written when I thought the question was about a two-arm balance scale of the traditional sort, rather than a weighing machine that weighs one set of things and tells you the total weight. If I've understood OP's clarifications right, this was not the intended question.]

Well,

any solution to the "standard" 12 coins puzzle (e.g., MA DO LIKE ME TO FIND FAKE COIN) will find the odd coin here in three weighings (just keep them all showing, say, heads throughout) and since that also tells you whether the different coin is heavy or light, it will tell you in this case whether the different coin is heavy-when-heads or light-when-heads.

And of course

you can't do it with fewer than three weighings because there aren't enough different possible outcomes from those weighings to distinguish the 24 different possibilities.

$\endgroup$
9
  • $\begingroup$ How would you now if the odd count was in ABCDEF in a single weighing? $\endgroup$
    – paparazzo
    Commented Oct 17, 2016 at 23:46
  • $\begingroup$ So the place where I say we can do that is where we know what the coins are supposed to weigh. So weigh ABCDEF and see whether they weigh the "right" amount (in which case the odd coin isn't one of those) or too much (in which case it is, and it's heavy), or too little (in which case it is, and it's light). $\endgroup$
    – Gareth McCaughan
    Commented Oct 18, 2016 at 0:27
  • $\begingroup$ From the problem statement you do NOT know what a normal coin weighs $\endgroup$
    – paparazzo
    Commented Oct 18, 2016 at 0:41
  • $\begingroup$ As I said, the problem statement seems to me not to make it clear whether you do. But if you don't, you need the second version of the procedure, which I gave below the first one. $\endgroup$
    – Gareth McCaughan
    Commented Oct 18, 2016 at 11:53
  • 1
    $\begingroup$ "If it is weighed" $\endgroup$
    – paparazzo
    Commented Oct 18, 2016 at 11:56
2
$\begingroup$

If the offending coin is on the scale, you know the reading will be either heavier or lighter than 12x grams. So, you can do it it in:

4 or less readings
weigh 6 coins (heavier/lighter?) no? Then
weigh 3 of the remaining coins (heavier/lighter?) no? Then
weigh 2 of the remaining coins (heavier/lighter?) no? - 3 measurements = last coin is the offender.
Or weigh 2 of the remaining coins (heavier/lighter?) yes? - weigh one of these last two.

In each of the first three cases, if the answer is yes, then

instead of weighing the remaining, you weigh that number of the set you just measured.

$\endgroup$
3
  • $\begingroup$ If you don't know what X is then you don't know if it is heavier or lighter $\endgroup$
    – paparazzo
    Commented Oct 18, 2016 at 0:00
  • $\begingroup$ @Paparazzi, in his previous questions, X was assumed to be known. I think the same way as you based on the wording, but ignoring on this one. $\endgroup$
    – John
    Commented Oct 18, 2016 at 0:04
  • $\begingroup$ @Paparazzi-how do you know the weight of standing fake coin is equal to X if you don't know the weight of real coin? Comparison require at least both information. Because coins vary in weight ,X is assigned as known variable . $\endgroup$
    – TSLF
    Commented Oct 22, 2016 at 13:32
2
$\begingroup$

Illustration of the measuring process.
Illustration of process

It can be found in:

Three readings. The essence of this solution is to: first, find the set of coins that has the anomalous coin, second, find if being face up results in the set being heavier or lighter, and third, narrow to a final measurement involving 1 coin up, 1 coin down, and 1 coin vertical (or off the scale).

Assigning X = 1,

we can weigh 9 of the coins (1-9) all head's up.

If it equals

9, we know the anomalous coin is in the remaining unweighed set of 3. Weigh the set of 3 (head's up). A heavier reading tells you the current orientation (head's up) is the heavier side (semantics), and likewise for a lighter reading. Finally, leave one coin head's up, one coin head's down, and one vertical (vertical is guaranteed to equal 1). If 3 head's up is heavy, then in this new orientation if the weight is still heavy, you know it's the coin that's head's up; and if the combined weight is light then you know it's the coin that's head's down, and equal to 3, you know it's the coin that's vertical. Vice-versa if three head's up was light instead.

If it does not equal

9, follow the same process, but do so in larger batches, namely in 3 for this example. The vertical coin is not necessary but set in the weighing to illustrate the weight would be the same.

$\endgroup$
5
  • $\begingroup$ If I'm reading this correctly, that's a possible max-5 readings when you have a couple of answers that can always do it in 4 by just splitting the number of coins in half instead of 9. Now, statistically, over a number of runs, this may result in a fewer number of measurements, but that wasn't in your question. $\endgroup$
    – John
    Commented Oct 18, 2016 at 14:49
  • 1
    $\begingroup$ @John This is three weighings. The first weighing is 12...9. If the result is 9, perform the top two. If it is not 9, perform the bottom two. $\endgroup$ Commented Oct 18, 2016 at 16:20
  • $\begingroup$ @MikeEarnest, or TSLF, so, for the one labeled "3rd", is that coin's 10 and 11 being weighed horizontally, with the 11 coin being on the scale vertically? If so, what does the "2nd" weighing really accomplish? You already know it's not equal to 3 (if the other 9 = 9x). I guess my next question is, why post an answer to your question if you're not accepting it as the answer? $\endgroup$
    – John
    Commented Oct 18, 2016 at 19:16
  • 1
    $\begingroup$ @John After 1st weighing, you know 10+11+12 is not 3, but you don't know if it's bigger or less than 3. The 2nd weighing tells you this fact, allowing you to deduce if the fake is heavy or light (when heads up). The heavy/lightness of the fake is then used with the last weighing to conclude which of 10,11,12 is fake. $\endgroup$ Commented Oct 18, 2016 at 19:27
  • 1
    $\begingroup$ @MikeEarnest, thank you. And the vertical coins don't actually even need to be on the scale. I wasn't getting that the color schemes reflected heads up and down. This makes sense. Thanks. $\endgroup$
    – John
    Commented Oct 18, 2016 at 19:37
1
$\begingroup$

Here's a way to find the fake with

5 uses of the scale.

Divide the coins into three equal groups, and weigh each of these groups. Whichever group weighs different must contain the fake. You will also now know what the value of $X$ is.

Next, use binary search on the four possible fakes. Weigh two of these four; if the weight is $2X$, the fake is in the other two, if not, it is one of the ones weighed. Either way, you are left with two potential fakes. Weigh one to see if it weighs $X$.

Also, it can't be done in

3 weighings. There are $2^3=8$ ways to weigh a coin with such a procedure (three weighings, on or off scale for each), but 12 coins total, so two coins must have been weighed the same way. If the fake is one of them, then they cannot be distinguished.

$\endgroup$
1
  • $\begingroup$ I count 5 weighings. $\endgroup$
    – paparazzo
    Commented Oct 17, 2016 at 23:58
1
$\begingroup$

ANSWER WAS WRITTEN WHEN TYPE OF SCALE WAS NOT CLARIFIED AND AN EQUAL ARM SCALE WAS ASSUMED.

Here is an answer with

4 weighings

By using 12 coins (A-L)

1) ABCD vs EFGH if they balance one of IJKL is the odd coin goto 2a else goto 2b

2a) I vs J balanced
3a) K vs L K is light
4a) K vs J K is still light and you know the coin and the side

2b) ABCD vs IJKL which will tell you which group has the odd coin and which face is up (1 group will weigh light against both groups, heavy against both groups, or will be omitted the 2nd weighing and you will know if it was heavy or light
3b) AB vs CD Assume ABCD has the odd coin weighing light you now know it is AB with light side up
4b) A vs C if A is light this is your odd coin if it is not B is and you already know its orientation

$\endgroup$
3
  • $\begingroup$ Flawed - you assume the odd coin is weighing light. It could be heavy. The is actually not purpose to weigh AB vs CD as you know it will not balance. $\endgroup$
    – paparazzo
    Commented Oct 17, 2016 at 23:52
  • $\begingroup$ @paparazzi since you mention AB vs CD Im assuming you meant step 3b? In steps 1 and 2b one group will weigh either light or heavy against both other groups so you know if the coin you are looking for is light or heavy. I could have specified light or heavy each time but i figured people would get that assumption. Since the answer is already invalid due to the other type of scale now being specified im not going to go back to clarify $\endgroup$
    – gtwebb
    Commented Oct 18, 2016 at 0:16
  • $\begingroup$ OK then I think I follow $\endgroup$
    – paparazzo
    Commented Oct 18, 2016 at 0:59
0
$\begingroup$

It will take 4 or 5 weightings.
1- weight 6 of the coins
2- turn them over and weight them again.
You can now know if the coin is in those 6 or the other 6 and also can extrapolate the weight of 1 coin.
3- weight 3 of the possible remaining coins and calculate if the odd coin is there by checking if the result = 3X or not
4- weight 2 of the remaining possible coins.(if lucky, ends here with 4)
5- weight 1 of the remaining possible coins.

$\endgroup$
0
$\begingroup$

It is possible only with 3 tests.

! Most people seem to think that the thing to do is weigh six coins against six coins, but if you think about it, this would yield you no information concerning the whereabouts of the only safe coin.
So that the following plan can be formulated: let us number the coins from 1 to 12. For the first weighing let us put on the left pan coins 1,2,3,4 and on the right pan coins 5,6,7,8.
There are two possibilities. Either they balance, or they don't. If they balance, then the good coin is in the group 9,10,11,12. So for our second weighing we would put 1,2 in the left pan and 9,10 on the right. If these balance then the good coin is either 11 or 12. Weigh coin 1 against 11. If they balance, the good coin is number 12. If they do not balance, then 11 is the good coin.
If 1,2 vs 9,10 do not balance, then the good coin is either 9 or 10. Again, weigh 1 against 9. If they balance, the good coin is number 10, otherwise it is number 9.
What if the first weighing 1,2,3,4 vs 5,6,7,8 does not balance? Then any one of these coins could be the safe coin. Now, in order to proceed, we must keep track of which side is heavy for each of the following weighings.
Suppose that 5,6,7,8 is the heavy side. We now weigh 1,5,6 against 2,7,8. If they balance, then the good coin is either 3 or 4. Weigh 4 against 9, a known bad coin. If they balance then the good coin is 3, otherwise it is 4.
Now, if 1,5,6 vs 2,7,8 does not balance, and 2,7,8 is the heavy side, then either 7 or 8 is a good, heavy coin, or 1 is a good, light coin. For the third weighing, weigh 7 against 8. Whichever side is heavy is the good coin. If they balance, then 1 is the good coin. Should the weighing of 1,5, 6 vs 2,7,8 show 1,5,6 to be the heavy side, then either 5 or 6 is a good heavy coin or 2 is a light good coin. Weigh 5 against 6. The heavier one is the good coin. If they balance, then 2 is a good light coin.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.