[Guest]

A slight variation of the puzzle posted in "Weighing in a harder way".

You have a simple scale and a number of coins weighing the same except for 1 coin which does not weigh the same as the rest.

In a total of 4 weighings you must determine which coin is the odd coin.

Now, if you know in advance that this coin is, say, heavier than the rest, the total number of coins including the heavier coin which would allow you - with 100% certainty - to determine which is the heavier coin would be 81 coins (feel free to challenge this - but this claim should be fairly solid).

However, if you do not know in advance if the odd coin is heavier or lighter the total number of coins would have to be lower for the puzzle to be solvable in 4 weighings. But how much lower?

In other words:

You have X coins all weighing the same except for 1, which is either heavier or lighter than the rest. If you are given 4 weighings on a simple scale to determine which coin is the odd coin, what is the maximum possible value of X?

/Uhre

[Guest]

Possibly 27. You have 3 sets of 9 each. A, B, and C.

If A>B or B>A, weigh the heavier group against C. If it is heavier than C, then the coin is heavier, and whatever pile you weighed contains it. If they are equal, then the coin is lighter and whatever pile you didn't weigh in the second weighing contains it. Then break the groups into 3, and find the lighter/heavier one. Then into groups of 1 and you will get your answer. I don't know if it can be more but this is what I came up with.

[Guest]

Don't have much time, but

I'd say 27. You will split it into 3 groups of 9. The first 2 weighs will tell you if the balls are heavier or lighter. Here's how it works; Let's say you have A,B,C. Let's say the fake coin is in C;

Scenario 1:

A - B = Same

B - C = C, heavier = coin is heavier - you can establish the rule that a heavier load will contain your coin.

Scenario 2:

A - C = C, heavier

B - C = C, heavier = coin is heavier - same as above.

2 weighs so far.

For the third, divide 9 into 3 groups of 3. Then the 3 into 1 each.

That's what I think so far. But there may be more to it so I might be wrong. Will spend more time on it after finishing up my work.

EDIT: Ah, Avalance just beat me to it. Lol.

Edited April 1, 2009 by scsw

[Guest]

Well, a bit early for hints perhaps, but since the puzzle I made a variation on was about 27 coins, I think it's safe to reveal that I believe that the maximum number of coins is in fact higher than this - hence my need to make this variation.

/Uhre

[Guest]

I got it in 30. Divide into 3 groups of 9 and 1 group of 3. Weigh two of the 9's together like in my last one. If they are unequal follow my last post. But if they are equal, measure one of them against the last pile of 9, if they are again equal. Take only the pile of 3 and know that it has either a lighter or heavier coin in it. Measure two of them against eachother, if they're equal then the left-over is the lighter/heavier one. If they are not equal, measure the heavier one against the left-over one and you can figure out which coin is lighter/heavier. I don't think anything above 30 is possible though. Unless I'm wrong again.

[bonanova]

Four weighings gives a possibility of 3⁴ = 81 outcomes.

So you can't have more than 81 possibilities.

Not knowing whether the coin is heavier or lighter introduces a factor 2.

Now you're left with 40.5 - ehhh - 40 possibilities.

That is the theoretical upper limit for the number of coins.

Now the weighing strategies available reduce it somewhat.

First, there's likely a factor of 3 needed, eliminating 40 and setting the limit at 39.

But the three groups would then be of 13 coins, making the next round intractable.

I'm thinking then 36 - 3 groups of 12 and some creative groupings after that should do it.

No time now ... see if that can be done.

[Guest]

I got it in 30. Divide into 3 groups of 9 and 1 group of 3. Weigh two of the 9's together like in my last one. If they are unequal follow my last post. But if they are equal, measure one of them against the last pile of 9, if they are again equal. Take only the pile of 3 and know that it has either a lighter or heavier coin in it. Measure two of them against eachother, if they're equal then the left-over is the lighter/heavier one. If they are not equal, measure the heavier one against the left-over one and you can figure out which coin is lighter/heavier. I don't think anything above 30 is possible though. Unless I'm wrong again.

This is definately a valid solution - except that it is not using the maximum possible amount of coins.

/Uhre

[Guest]

Four weighings gives a possibility of 3⁴ = 81 outcomes.

So you can't have more than 81 possibilities.

Not knowing whether the coin is heavier or lighter introduces a factor 2.

Now you're left with 40.5 - ehhh - 40 possibilities.

That is the theoretical upper limit for the number of coins.

Now the weighing strategies available reduce it somewhat.

First, there's likely a factor of 3 needed, eliminating 40 and setting the limit at 39.

But the three groups would then be of 13 coins, making the next round intractable.

I'm thinking then 36 - 3 groups of 12 and some creative groupings after that should do it.

No time now ... see if that can be done.

Excellent reasoning. I can't wait to see the proof of your claim

/Uhre

[bushindo]

I got it in 30. Divide into 3 groups of 9 and 1 group of 3. Weigh two of the 9's together like in my last one. If they are unequal follow my last post. But if they are equal, measure one of them against the last pile of 9, if they are again equal. Take only the pile of 3 and know that it has either a lighter or heavier coin in it. Measure two of them against eachother, if they're equal then the left-over is the lighter/heavier one. If they are not equal, measure the heavier one against the left-over one and you can figure out which coin is lighter/heavier. I don't think anything above 30 is possible though. Unless I'm wrong again.

We can improve what Avalanche5x did a bit further. We can improve the total amount by 1 since we have some extra information about the normal stones.

Following's Avalanche5x's reasoning, if after two weighting we determine that the 3 groups of 9 coins (27) are the same, then we reduced the problem to determining how many extra coins can we identify, given that we have 2 weighings and that the other 27 are normal. I think 4 is the maximum under this constraint. Divide the 4 into 2 groups of size 3 and 1. Take the 3 and weight against 3 of the normal coin. If the scale is balanced, then the last coin is the defective one, and an extra weighting will determine whether it is heavier or lighter.

If the scale if not balanced, then the group of 3 contains the defective coin. Remove 1 coin each from each side of the scale (let the coin we removed from defective side be called R), swap 1 defective coin (call this coin S )with a coin from the normal. One coin from the defective side will still be in its original position (call this O). We then measure the two groups of 2 together. Three scenarios can happen

1) The scale balances. The defective coin must be R. We can determine its relative weight from the third weighing.

2) The scale tips to the same side as the third weighing. O is the defective coin. Relative weight determined from third weighing.

3) The scale tips to the opposite direction as third weighing. S is the defective coin. Relative weight determined from third weighing.

[Guest]

We can improve what Avalanche5x did a bit further. We can improve the total amount by 1 since we have some extra information about the normal stones.

Following's Avalanche5x's reasoning, if after two weighting we determine that the 3 groups of 9 coins (27) are the same, then we reduced the problem to determining how many extra coins can we identify, given that we have 2 weighings and that the other 27 are normal. I think 4 is the maximum under this constraint. Divide the 4 into 2 groups of size 3 and 1. Take the 3 and weight against 3 of the normal coin. If the scale is balanced, then the last coin is the defective one, and an extra weighting will determine whether it is heavier or lighter.

If the scale if not balanced, then the group of 3 contains the defective coin. Remove 1 coin each from each side of the scale (let the coin we removed from defective side be called R), swap 1 defective coin (call this coin S )with a coin from the normal. One coin from the defective side will still be in its original position (call this O). We then measure the two groups of 2 together. Three scenarios can happen

1) The scale balances. The defective coin must be R. We can determine its relative weight from the third weighing.

2) The scale tips to the same side as the third weighing. O is the defective coin. Relative weight determined from third weighing.

3) The scale tips to the opposite direction as third weighing. S is the defective coin. Relative weight determined from third weighing.

Yes, this is a nice little optimization of Avalanche5x's approach. Well done, Bushindo. Still my claim is that the limit can be pushed even further.

/Uhre

[bonanova]

Excellent reasoning. I can't wait to see the proof of your claim

/Uhre

"Brother, can you spare a dime?"

I can do 36 coins straightforwardly, except ...

I need 4 extra good coins to use in the 2nd weighing.

[CaptainEd]

Most of the weighing depends on having learned whether a coin is not-light or not-heavy.

For example, if you weigh 1234 against 5678 and the left pan goes up-----then 1234 includes 1 light, and 5678 contains one heavy Here, these are symbolized "-(1234)", meaning they are potentially light (ie. Not-heavy), and "+(5678)", meaning they are potentially heavy (ie. Not-light)

If we know that a coin is - or is +, we'll call it "known". It isn't really known yet, as it might be a good coin, but at least, if it's bad, we know whether it's light or heavy.

In what follows, the task "weigh 3 known" means that you have 3 coins, and each one is "known"

unknown known max weighings

......2.....3...1 *for unknown, need an additional good coin

......4.....9...2

.....12....27...3

.....38....81...4

In general, if we symbolize "weigh known" as "Wk" and "weigh unknown" as "Wu",

Wk(i) = 3^i

Wu(i) = Wu(i-1) + Wk(i-1) - 1 (the -1 reduces the odd Wk to the largest even number below it)

Here are the first several scenarios:

Weigh 3 known in 1 weighing

known -a -b +c, weigh (-a vs -b): cases (=,<,>): c,a,b

Weigh 4 in 2 weighings

unknown abcd, weigh (a vs. b): cases (=,<,>): cd, -a+b, -b+a; weigh the known pair in one more

Weigh 9 known in 2 weighings

known -(abcde) +(fghi), weigh (-a+e+f vs -b+g+h). Cases (=,<,>) -c-d-i, -a+g+h,-b+e+f; weigh 3 known in one more

This demonstrates the power of having "known" tendencies: if -a+e+f is lighter than -b+g+h, it can only be because "a" is light or "ef" are heavy; if "b" were light or "gh" heavy, the scale would have tipped the other way.

The two principles of weighing knowns are:

1) if all same leaning, you're back to the classic problem of finding the light coin--you can do 3^n in n weighings

2) if they're mixed, you mix the lights and heavies in one or both pans, so that you get information regardless of which pan raises.

Weigh 12 in 3 weighings

unknown abcdefghijkl, weigh (abcd vs efgh). Cases (=,<,>) ijkl, -abcd+efgh, -efgh+abcd; weigh 4 unknown or 8 known in 2 more

Weigh 27 known in 3 weighings

known -(1 to 15)+(16 to 27), weigh -(10,11,12)+(16 to 21) vs. -(13,14,15)+(22 to 27);

cases (=,<,>) 1 to 9, -(10,11,12)+(22 to 27), -(13,14,15)+(16 to 21); weigh 9 known in 2 more

Weigh 38 unknown in 4 weighings

unknown 1…38, weigh 13(A) against 13(B) leave 12© aside. Cases (=,<,>) C, -A+B, -B+A. Weigh 12 unknown or 26 known in 3 more

Edited April 2, 2009 by CaptainEd

[CaptainEd]

Weigh 9 known in 2 weighings

known -(abcdi) +(efgh), weigh (-a+e+f vs -b+g+h). Cases (=,<,>) -c-d-i, -a+g+h,-b+e+f; weigh 3 known in one more

[Guest]

"Brother, can you spare a dime?"

I can do 36 coins straightforwardly, except ...

I need 4 extra good coins to use in the 2nd weighing.

Well, as the OP is laid out I'd say that no loans are allowed. However, I'd love to see how you would put the investment to use, if you care to show it

/Uhre

[Guest]

Most of the weighing depends on having learned whether a coin is not-light or not-heavy.

For example, if you weigh 1234 against 5678 and the left pan goes up-----then 1234 includes 1 light, and 5678 contains one heavy Here, these are symbolized "-(1234)", meaning they are potentially light (ie. Not-heavy), and "+(5678)", meaning they are potentially heavy (ie. Not-light)

If we know that a coin is - or is +, we'll call it "known". It isn't really known yet, as it might be a good coin, but at least, if it's bad, we know whether it's light or heavy.

In what follows, the task "weigh 3 known" means that you have 3 coins, and each one is "known"

unknown known max weighings

......2.....3...1 *for unknown, need an additional good coin

......4.....9...2

.....12....27...3

.....38....81...4

In general, if we symbolize "weigh known" as "Wk" and "weigh unknown" as "Wu",

Wk(i) = 3^i

Wu(i) = Wu(i-1) + Wk(i-1) - 1 (the -1 reduces the odd Wk to the largest even number below it)

Here are the first several scenarios:

Weigh 3 known in 1 weighing

known -a -b +c, weigh (-a vs -b): cases (=,<,>): c,a,b

Weigh 4 in 2 weighings

unknown abcd, weigh (a vs. b): cases (=,<,>): cd, -a+b, -b+a; weigh the known pair in one more

Weigh 9 known in 2 weighings

known -(abcde) +(fghi), weigh (-a+e+f vs -b+g+h). Cases (=,<,>) -c-d-i, -a+g+h,-b+e+f; weigh 3 known in one more

This demonstrates the power of having "known" tendencies: if -a+e+f is lighter than -b+g+h, it can only be because "a" is light or "ef" are heavy; if "b" were light or "gh" heavy, the scale would have tipped the other way.

The two principles of weighing knowns are:

1) if all same leaning, you're back to the classic problem of finding the light coin--you can do 3^n in n weighings

2) if they're mixed, you mix the lights and heavies in one or both pans, so that you get information regardless of which pan raises.

Weigh 12 in 3 weighings

unknown abcdefghijkl, weigh (abcd vs efgh). Cases (=,<,>) ijkl, -abcd+efgh, -efgh+abcd; weigh 4 unknown or 8 known in 2 more

Weigh 27 known in 3 weighings

known -(1 to 15)+(16 to 27), weigh -(10,11,12)+(16 to 21) vs. -(13,14,15)+(22 to 27);

cases (=,<,>) 1 to 9, -(10,11,12)+(22 to 27), -(13,14,15)+(16 to 21); weigh 9 known in 2 more

Weigh 38 unknown in 4 weighings

unknown 1…38, weigh 13(A) against 13(B) leave 12© aside. Cases (=,<,>) C, -A+B, -B+A. Weigh 12 unknown or 26 known in 3 more

An excellent proposal, CaptainEd.

This is a fine example of divide and conquer put to good use. Weighing 27 known (and therefore also 26) in 3 weighings is easily proven, and weighing 12 unknown (ie. the odd is either lighter or heavier) in 3 weighings has been proven over and over in the "12 balls" / "12 coins" puzzle.

Now, I can't help but notice that your solution involves an odd total number of coins - odd as in not-a-factor-of-3. So - if the problem can be solved with 38 coins - how about 39 coins?

Edited April 3, 2009 by uhre

[CaptainEd]

Please disregard my previous posts--that proof was sloppy, anecdotal, wrong, and CHEAP!

We can sift through all 41 suspect coins in 4 weighings, if we can borrow a known good coin.

Once again, we need to discuss both the ultimate problem (all unknown coins, with perhaps one known good loaner) and the easier problem (all coins have fallen on one side or the other of a weighing).

I'll use a more accurate term, "restricted", to describe a coin that has been in a weighing that did not come out equal. If a weighing does not come out equal, then assume the left pan is light (the same argument holds if the left pan is heavy). Now, identify each of the coins in the left pan as "-", meaning that none of them can be heavy, and one of them MIGHT be light. Similarly, identify each of the coins in the right pan as "+", meaning that none of them can be light, and one of them MIGHT be heavy. Let's call all "+" and "-" coins "restricted".

First proof, both recursive and constructive:

Theorem: We can find the bad coin in 3^n restricted coins in n weighings.

for n=1 there are two cases, which we'll treat as one:

++-

+++

In either case, put one of the matching pair in Left pan (L), put the other in Right pan ®, set the third coin Aside (A)

If the comparison comes out...

=: A is bad

<: R is bad

>: L is bad

So we've found the bad coin in 1 weighing

for n>1: there are two cases:

1) All - (or all +)

2) 0 < #H < (3^n)/2 (in other words, there are more + than -, or the other way around, pick

the kind there's less of. In this discussion, "+" items are fewer.)

case 1) put 3^(n-1) coins in each pan (L and R), leave 3^(n-1) aside (A). The weighing will result in...

=: A contains 3^(n-1) restricted coins, one is bad, can solve in (n-1) steps

<: L is lighter, contains 3^(n-1) restricted coins, one is bad, can solve in (n-1) steps

>: R is lighter, ditto

case 2) spread "+" evenly between the two pans (L and R), put the odd "+", if any, in the Aside area; fill pans up to 3^(n-1) with "-"s, put the rest in Aside area. The weighing will result in...

=: A contains 3^(n-1) restricted coins, can solve in (n-1) steps

<: combine the "-"s from the Left pan and the "+"s from the Right pan, these are 3^(n-1) restricted coins, can solve in (n-1) steps (These are the only coins that could have resulted in the Left pan rising)

>: combine the "-"s from the Right pan and the "+"s from the Left pan, there are 3^(n-1) restricted coins, can solve in (n-1) steps (These are the only coins that could have resulted in the Left pan falling)

We've treated 3* 3^(n-1) coins = 3^n coins in n weighings.

So, by induction on n, if it can be solved for 3^(n-1) coins in (n-1) steps, it can be solved for 3^n coins in n steps.

Now, the proof and bounds for UNrestricted coins.

Theorem: We can find the bad coin in (1+3^n)/2 unrestricted coins in n weighings, if we borrow one additional coin known to be Good.

Once again, by induction on n.

For n=1: given 2 unrestricted coins AND an additional coin known to be Good, put one unrestricted coin in the Right pan and the known good coin in the Left pan, set the other unrestricted coin Aside. The weighing will result in:

=: Aside coin is bad

<: Since the Good coin is in the Left pan, the Right pan contains a bad (truly heavy) coin

>: Since the Good coin is in the Left pan, the Right pan contains a bad (truly light) coin.

So we've found the bad coin in one weighing. (Notice, if the bad coin was Aside, we don't actually know whether it was Heavy or Light, and we don't care)

For n>1:

Put (1+3^(n-1))/2 coins in the Left pan, one of them being the known Good coin; put (1+3^(n-1))/2 coins in the Right pan, and set (1+3^(n-1))/2 coins Aside. The weighing will result in ...

=: The Aside group contains a bad coin; it can be found in n-1 weighings (and we no longer need the borrowed Good coin, as any of the coins in the Left or Right pan are now known Good)

<: The 3^(n-1) coins in the Left and Right pans are now restricted; the coins in the Left pan (except for the Good coin) are now "-", the coins in the Right pan are now "+".

Because they are now all restricted, they can be solved in n-1 weighings

>: Same argument as <, but with + and - reversed.

Including the one known Good coin, we have treated 3* (1+3^(n-1))/2 = 1 + (1+3^n)/2 coins. Removing the Good coin, we have treated (1+3^n)/2 unrestricted coins in one weighing plus (n-1) weighings.

So, the true table of weighing capabilities is:

------ ------------ ----------
1 2 3
2 5 9
3 14 27
4 41 81

etc.

n	unrestricted	restricted

So we really can get all 41 Bonanova calculated. Remember, we do need to borrow that one known good coin for the first round of weighings...

Edited April 3, 2009 by CaptainEd

[CaptainEd]

Yet another typo, sigh! In the proof for restricted coins, the n>1 case, the 2) clause should read

2) 0 < #+ < (3^n)/2 (in other words, assume the number of "+" is less than half the number of coins. Same argument applies if the number of "-" is less than half)

[Guest]

Please disregard my previous posts--that proof was sloppy, anecdotal, wrong, and CHEAP!

I don't know about the sloppyness of your previous post. I thought it was quite good. However, it was definately not wrong. In fact it was more correct with regards to the OP than your latest post.

This new claim, however, is very interesting. I feel that there has to be a flaw in it, but I can't see it yet (if it exists). And maybe there isn't any. After all the introduction of a known quality coin is a strong addition.

I'm looking at your proof now - but it's heavy stuff

I'm still interested in seeing a solution for the OP as well of course.

Edited April 3, 2009 by uhre

[CaptainEd]

40.

Put 26 in the two pans, set 14 aside. If the pans balance, you can sift the (unrestricted) 14 in 3 weighings (use any other coin as the spare Good coin needed).

If the pans don't balance, you now have identified 13 coins as "-" and 13 as "+", so you have 26 restricted coins, which can be sifted in 3 weighings.

Edited April 3, 2009 by CaptainEd

[Guest]

40.

Put 26 in the two pans, set 14 aside. If the pans balance, you can sift the (unrestricted) 14 in 3 weighings (use any other coin as the spare Good coin needed).

If the pans don't balance, you now have identified 13 coins as "-" and 13 as "+", so you have 26 restricted coins, which can be sifted in 3 weighings.

14 coins of which we know nothing in 3 weighings? Please show me

[CaptainEd]

The unrestricted proof by induction shows the same principle:

put 5 coins aside, 5 in the right pan, 4 plus a good coin in the left pan. (Because we started with 40 coins, we discovered many good coins in that first weighing).

If the pans balance, you have 5 unrestricted coins, which you can sift in 2 weighings (I'll show you below).

If the pans don't balance, then you have identified the 4 unknown coins in the Left pan as "-" and the 5 coins in the Right pan as "+", (or the other way around, depending on which way the pans fell) so you have 9 restricted coins, which you can solve in 2 weighings.

Since you're going to prod me about the 5 coins in 2 weighings, grab one of the large bag of good coins you've been ammassing.

Put one good coin and one suspect coin in the Left pan, 2 suspect coins in the Right pan, and set the other 2 suspect coins Aside.

If the pans balance, you have the two Aside coins, which you can sift using 1 weighing (I'll show how below).

If the pans don't balance, then you have identified the unknown coin from the Left pan and the two coins from the Right pan--they are -++ or +--, depending on which way the pans fell. You can distinguish among 3 restricted coins in one weighing.

In case there's doubt about solving two unrestricted coins in one weighing, use one of the many good coins as follows:

Put the Good coin in Left pan, one suspect coin in Right pan, set one suspect coin aside.

If the pans balance, the coin left Aside is bad,

If the pans don't balance, the coin opposite the Good coin is bad.

[Guest]

The unrestricted proof by induction shows the same principle:

put 5 coins aside, 5 in the right pan, 4 plus a good coin in the left pan. (Because we started with 40 coins, we discovered many good coins in that first weighing).

If the pans balance, you have 5 unrestricted coins, which you can sift in 2 weighings (I'll show you below).

If the pans don't balance, then you have identified the 4 unknown coins in the Left pan as "-" and the 5 coins in the Right pan as "+", (or the other way around, depending on which way the pans fell) so you have 9 restricted coins, which you can solve in 2 weighings.

Since you're going to prod me about the 5 coins in 2 weighings, grab one of the large bag of good coins you've been ammassing.

Put one good coin and one suspect coin in the Left pan, 2 suspect coins in the Right pan, and set the other 2 suspect coins Aside.

If the pans balance, you have the two Aside coins, which you can sift using 1 weighing (I'll show how below).

If the pans don't balance, then you have identified the unknown coin from the Left pan and the two coins from the Right pan--they are -++ or +--, depending on which way the pans fell. You can distinguish among 3 restricted coins in one weighing.

In case there's doubt about solving two unrestricted coins in one weighing, use one of the many good coins as follows:

Put the Good coin in Left pan, one suspect coin in Right pan, set one suspect coin aside.

If the pans balance, the coin left Aside is bad,

If the pans don't balance, the coin opposite the Good coin is bad.

Sorry for the delayed reply. I bow to you, CaptainEd. Truely awesome analysis.

I had to go through all your info again, as I was still not convinced of the whole (un)restricted idea, but it seems to be airtight. The solution I came up with was for 1 coin less than yours, but I was also assuming that it had to be known in the end whether the odd coin was lighter or heavier. Seeing your proof made me realise that I did not state this in the OP (and therefore it's not a requirement of course). This means that I should be able to reach the same amount as well.

[CaptainEd]

Sorry for the delayed reply. I bow to you, CaptainEd. Truely awesome analysis.

I had to go through all your info again, as I was still not convinced of the whole (un)restricted idea, but it seems to be airtight. The solution I came up with was for 1 coin less than yours, but I was also assuming that it had to be known in the end whether the odd coin was lighter or heavier. Seeing your proof made me realise that I did not state this in the OP (and therefore it's not a requirement of course). This means that I should be able to reach the same amount as well.

Yes, that one coin difference is needed to make the further decision of whether the bad coin is light or heavy.

Thank you, and thank you for the puzzle. It was fun to understand the whole area and clarify my thoughts. For one thing, I learned about how general the restricted case is. While we all know that, if the bad coin is known to be light, we can find it in n weighings from 3^n coins, I hadn't realized the more general result (which I now proved) that it doesn't matter whether the bad coin is light or heavy, as long as we know which ones could only be light, and which ones could only be heavy.

[bonanova]

Well, as the OP is laid out I'd say that no loans are allowed.

However, I'd love to see how you would put the investment to use, if you care to show it

/Uhre

Well the Captain has blown away the 36 coin case, but FWIW ... here's my

Call the coins a_1-12, b_1-12, c_1-12

First weighing: a_1-12 vs b_1-12

1. Left up: one of a_1-12 light or one of b_1-12 heavy: weigh 16 good vs a_1-8, b_1-8
   
   • Left up: one of b_1-8 heavy: weigh b_1-3 vs b_5-7
     
     • Left up: one of b_5-7 heavy: weigh b₅ vs b₆
       
     • Equal b₄ or b₈ heavy: weigh good vs b₄
       
     • Left down: one of b_1-3 heavy: weigh b₁ vs b₂
       

[*] Equal: one of a_9-12 light or one of b_9-12 heavy: weigh 6 good vs a_9-11, b_9-11

• Left up: one of b_9-12 is heavy: weigh b₉ vs b₁₀
  
• Equal: a₁₂ is light or b₁₂ is heavy: weigh good vs a₁₂
  
• Left down: one of a_9-11 is light: weigh a₉ vs a₁₀
  
  
• Left down: one of a_1-8 light: weigh a_1-3 vs a_5-7
  
  • Left up: one of a_1-3 light: weigh a₁ vs a₂
    
  • Equal a₄ or a₈ light: weigh good vs a₄
    
  • Left down: one of a_5-7 light: weigh a₅ vs a₆
    
    
    
    
  • Equal: one of c_1-12 bad: weigh c_1-4 vs c_5-8
    
    • Left up: c_1-4 light or c_5-8 heavy. weigh 6 good vs c_1-3, c_5-7
      
      • Left up: one of c_1-3 light: weigh c₁ vs c₂
        
      • Equal: c₄ light or c₈ heavy. weigh good vs c4
        
      • Left down: one of c_5-7 heavy: weigh c₅ vs c₆
        

      [*] Equal: one of c_9-12 is bad. weigh 3 good vs c_9-11

      [*]Left down: one of a_1-12 heavy or one of b_1-12 light: weigh 16 good vs a_1-8, b_1-8

      [*] proceed as in Left up case:

      But only 12 good i.e. c_1-12 are available.

      Need 4 additional good coins.

      [*] Left up: one of c_9-11 is heavy. weigh c₉ vs c₁₀

      [*] Equal: c₁₂ is known heavy or light. weigh good vs c₁₂

      [*] Left down: one of c_9-11 is light. weigh c₉ vs c₁₀

    [*] Left down: c_1-4 heavy or c_5-8 light. weigh 6 good vs c_1-3, c_5-7

    [*] Left up: one of c_1-3 heavy: weigh c₁ vs c₂

    [*] Equal: c₄ heavy or c₈ light. weigh good vs c4

    [*] Left down: one of c_5-7 light: weigh c₅ vs c₆

[Guest]

Well, the captain blew away my solution for 39 (40) coins as well. His approach is both much more elegant than my exhaustive approach, and furthermore his solution scales to any number of weighings - mine definately does not.

The outcome of a weighing can be either left side down (1), right side down (2), or balanced (X)

There are 81 total outcomes.

1111

1112

111X

1121

112X

1122

...

...

XXX1

XXX2

XXXX

I was eliminating XXXX since 4 times balanced would not tell me anything about a coin being heavier or lighter.

Because it is not known whether the odd coin is lighter or heavier, in any weighing combination there will be an opposite outcome when switching left side downs with right side downs - ie:

1111 = 2222 (left side down on all 4 means: odd coin in left bowl is heavier or odd coin in right bowl is lighter)

12X2 = 21X1

... etc.

These duplicates must be eliminated.

Aligning these outcomes shows something like:

1111 2222

1112 2221

111X 222X

1121 2212

...

...

XXX1 XXX2

When removing duplicates I'm shifting through the columns to ensure a balanced outcome of combinations, which will result in a balanced number of coins for each bowl/discard in each weighing.

That leaves me with 40 combinations:

1111

2221

111x

2212

...

...

xxx2

Removing 1111 brings the total down to 39, the closest factor of 3 - which I was expecting to need.

I'm now labelling 39 coins relating each to a combination.

A: 2221

B: 111X

C: 2212

...

...

#: XXX2

This now tells me how each coin shall be distributed among the bowl/discard for each weighing, and at the same time it shows me how to read the result of the weighings.

Weigh2: B... AC... ......#
Weigh3: BC... A... B.....#
Weigh4: A... C......# .......

|__________| |__________| __________
Bowl 1 Bowl 2 Discard

Weigh1:     B...            AC...         ......#

This works for 39 coins with one of them being either heavier or lighter. If I do not care to find out whether the odd coin is in fact lighter or heavier, I can add one more coin which will be the 'winner' if the scale always balances (combination XXXX).

I would even be able to add either of the combinations 1111 or 2222 for the 41th coin, but since that would bring imbalance to the number of coins in the bowls, I would have to borrow an extra 'known good coin'.

Edited April 4, 2009 by uhre