# 12 coins and a balance beam scale

by isly ilwott
Tags: balance, beam, coins, scale
 P: 72 You are given 12 coins that are identical except that they are numbered and you are told that one coin is odd-weighted, being either slightly lighter or slightly heavier than any one of the remaining eleven. You are given a worktable and a balance beam scale. You may use the scale three times only. You must tell at the end of three weighings; which coin is odd-weighted and whether it is heavy or light. Outline your solution in less than one thousand words.
P: 1,294
 Quote by isly ilwott You are given 12 coins that are identical except that they are numbered and you are told that one coin is odd-weighted, being either slightly lighter or slightly heavier than any one of the remaining eleven. You are given a worktable and a balance beam scale. You may use the scale three times only. You must tell at the end of three weighings; which coin is odd-weighted and whether it is heavy or light. Outline your solution in less than one thousand words.
I solved it in 4 steps.

And I know, whether the coin is heavier or lighter in 2 steps
 P: 2,828 I believe I made it in less than 300 words. Spoiler Write down all possible strings of length 3 of 3 letters, say L, R and S. Those refer to "left", "right" and "side" according to where the coin will be assigned for the measurement. Remove the 3 constant identical strings, "LLL", "RRR" and "SSS". You have 27-3=24 strings. Now among the remaining strings, all of them are made up of at least two different letters, consider the first letter different from all the previous ones, and define a "parity" allowing you to remove half of the strings. Say for instance, if the string begins by "L", keep only those strings whose next different letter is "R", remove all those for which it is "S". If the string begins with "R", remove all those whose next first different letter is "L". If the string begins with "S", remove all the strings whose first different letter is "R". This choice is arbitrary, and reflects the fact that you don't know whether you are looking for a heavier of a lighter coin. Once you're finished, you end up with 12 different strings. Assign each of them to a coin. Proceed to your 3 measurements, with each coin assigned to the left, the right, or the side according to its string. For each measurement, write down "L", "R" or "S" according to whether the scale indicates "left heavier", "right heavier" or "none heavier" (that is balance). Once again this is arbitrary. Once you are done with your 3 measurements, search among all coins if one string matches with the measurement string. If so, this is the faulty coin, and it is heavier. Otherwise, replace "L" by "R" and "R" by "L" in your measurement string. Exactly one coin will match, and it is lighter.
P: 72
12 coins and a balance beam scale

 Quote by rootX I solved it in 4 steps. And I know, whether the coin is heavier or lighter in 2 steps
I would dearly love to let you get away with this. However, as you have not resolved the question to the satisfaction of the judges who have in fact been shown that the puzzle is valid and the feat can be done and as I have personally worked it out (in three weeks time) I shall have to refuse your answer as being worthy of the cyber-prize to be awarded to the first successful submitter of a clearly stated solution that includes the outlining of the weighings and the logic involved in confirming the findings of each weighing.

After having worked this puzzle in my college years, I read a similar puzzle in Scientific American wherein there were only 9 coins, you could use the scale 4 times and you didn't have to determine whether the odd-weighted coin was heavy or light. I could not resist a letter to the editors telling them of the simplicity of their puzzle.

You are to be commended for even trying to work this one.

If there is no solution posted here within 3 weeks of the OP, I will post a hint regarding the first weighing. If there is no solution posted after a sufficient period following that hint, I will post the second weighing, after which the realization of the third weighing is what some would refer to as a piece of cake.
P: 72
 Quote by humanino Write down all possible strings of length 3 of 3 letters, say L, R and S. Those refer to "left", "right" and "side" according to where the coin will be assigned for the measurement. Remove the 3 constant identical strings, "LLL", "RRR" and "SSS". You have 27-3=24 strings. Now among the remaining strings, all of them are made up of at least two different letters, consider the first letter different from all the previous ones, and define a "parity" allowing you to remove half of the strings. Say for instance, if the string begins by "L", keep only those strings whose next different letter is "R", remove all those for which it is "S". If the string begins with "R", remove all those whose next first different letter is "L". If the string begins with "S", remove all the strings whose first different letter is "R". This choice is arbitrary, and reflects the fact that you don't know whether you are looking for a heavier of a lighter coin. Once you're finished, you end up with 12 different strings. Assign each of them to a coin. Proceed to your 3 measurements, with each coin assigned to the left, the right, or the side according to its string. For each measurement, write down "L", "R" or "S" according to whether the scale indicates "left heavier", "right heavier" or "none heavier" (that is balance). Once again this is arbitrary. Once you are done with your 3 measurements, search among all coins if one string matches with the measurement string. If so, this is the faulty coin, and it is heavier. Otherwise, replace "L" by "R" and "R" by "L" in your measurement string. Exactly one coin will match, and it is lighter.
I haven't counted the words as your "solution" does not describe the set-up of each weighing. You would need to do more explaining of your logic to satisfy the judges.

Try this: Set up a scenario involving the scale and a number of coins, then state your conclusions from observing the position of the scale. Then set up a second weighing by describing the coins to be placed on each pan (of the scale) and what you conclude following the steady state position of the scale after that weighing. Then proceed to the third weighing in the same manner...describe how you set up the weighing and what you conclude following the weighing.
P: 72
Very interesting...and insightful.

However, no cigar!

Weigh 1,2,3,4 against 5,6,7,8.
If they balance, then the different coin is among 9,10,11,12
--Weigh 1,2 against 9,10.
--If they balance, then the different coin is among 11,12
----Weigh 1 against 11
----If they balance, the different coin is 12 (but we don't know whether it is h
eavy or light)

...that's three weighings and you still haven't determined relative weight of the bad coin.

The rest of your "solution" is a bit unclear. I suggest you outline each weighing by number.

You are entirely correct about the proper vacation...go to one place and stay there for the duration. Cabo is recommended to all that can stand the beach life...and have more than 12 coins to spare.
P: 2,828
 Quote by isly ilwott I haven't counted the words as your "solution" does not describe the set-up of each weighing. You would need to do more explaining of your logic to satisfy the judges.
Your failure to recognize that this old, well-known and published procedure, besides solving your puzzle plus the immediate generalizations of it, is elegant, simple, and fully satisfying remains in my view your own problem. Frankly, I have built an explicit solution to this problem years before knowing the general solution given above. Constructing an explicit solution is straightforward and much less interesting than knowing the general solution.

If I were really bored and had nothing to do, I would display the explicit solution which comes out of the procedure, but unless I break a leg and end up stuck on a bed or something (not even sure that would be enough), for me to do so you would have to give me a good reason (besides getting your approval as "solving the problem" which I do not see as much worthy...).
P: 2,179
 Quote by isly ilwott I haven't counted the words as your "solution" does not describe the set-up of each weighing.
After you assign each coin a three letter 'word', you create a new word by 3 weighings in the following manner. In the first weighing, you put each coin whose first letter is L on one side and each coin whose first letter is R on the other. If the L side is heavy, L is the first letter of the new word. If the R side is heavy, then R is the first letter of the new word. If they balance, the S is the first letter of the new word. For the second weighing, put each coin whose middle letter is L on one side and each coin whose middle letter is R on the other and so build the second letter of the new word. Then put each coin whose last letter is L on one side and each coin whose last letter is R on the other. When you have built the new word, compare it to the words on the coins. If it matches a coin, then that coin is heavy. If no coin matches the new word, exchange L for R in the new word. It will certainly match one of the words on the coins and that coin will be light.
P: 72
 Quote by humanino Your failure to recognize that this old, well-known and published procedure, besides solving your puzzle plus the immediate generalizations of it, is elegant, simple, and fully satisfying remains in my view your own problem. Frankly, I have built an explicit solution to this problem years before knowing the general solution given above. Constructing an explicit solution is straightforward and much less interesting than knowing the general solution. If I were really bored and had nothing to do, I would display the explicit solution which comes out of the procedure, but unless I break a leg and end up stuck on a bed or something (not even sure that would be enough), for me to do so you would have to give me a good reason (besides getting your approval as "solving the problem" which I do not see as much worthy...).
The judges have analyzed your general solution and find it quite correct, though difficult to follow. You have won the overall prize, consisting of a cyber high-five and a wide smile. Congratulations! (That is, of course, less than meaningless if you googled the solution.)

For those of you who would arrange subsequent weighings patterned according to the outcome of the previous weighings, please continue to formulate your "if A then B" solution. It is substantially easier to fathom yet more lengthy when put to words.
 P: 2,828 OK, I described the problem and the solution I gave earlier to somebody else, and I must admit it does not seem so clear. So I will work out the solution explicitly below. I hope it clarifies. Let us first write down all 27 possible strings of "L", "R" and "S" and select the 12 "good ones" according to the above criteria. I'll color the good ones in green and the bad ones in red 1) LLL 2) LLR 3) LLS 4) LRL 5) LRR 6) LRS 7) LSL 8) LSR 9) LSS 10) RLL 11) RLR 12) RLS 13) RRL 14) RRR 15) RRS 16) RSL 17) RSR 18) RSS 19) SLL 20) SLR 21) SLS 22) SRL 23) SRR 24) SRS 25) SSL 26) SSR 27) SSS Now among the green good ones, I get the following table : coin # | first | second | third 1 | L | L | R 2 | L | R | L 3 | L | R | R 4 | L | R | S 5 | R | R | S 6 | R | S | L 7 | R | S | R 8 | R | S | S 9 | S | L | L 10 | S | L | R 11 | S | L | S 12 | S | S | L Now let's look at the structure a little bit and re-arrange rationally. There are 3 regular groups (2,3,4) in blue, (6,7,8) in green and (9,10,11) in purple which all do the same for the first two measurements. There is an additional "exceptional" structure with elements (1,5,12) in red which alternate in a circular permutation. Once those structures have been noticed, I decide (arbitrarily) to switch the second set of measurements : all coins on L will go on S, all those on R will go on L, and all on S will go on R. I also re-arrange the coin numbering according to the 3 groups. I re-number blue group first, then the green one, then the purple one and finally the exceptional red one. FINAL CODE TABLE :  old # | first | second | third | new # 2 | L | L | L | 1 3 | L | L | R | 2 4 | L | L | S | 3 6 | R | R | L | 4 7 | R | R | R | 5 8 | R | R | S | 6 9 | S | S | L | 7 10 | S | S | R | 8 11 | S | S | S | 9 1 | L | S | R | 10 5 | R | L | S | 11 12 | S | R | L | 12 Previous table is what I got by trial and error. Later on in an optimization algorithmic programing lecture, I learnt about this method (and others, allowing to solve optimization under constraints such as "given a backpack with finite volume and load capacity, how do you optimize the objects you put in given a large set of them with different volumes, weights, and values" for instance. Anyway...). Final table below is just the procedure set you get from all this, in terms of the new coin numbering scheme PROCEDURE measurement | left | right | side 1 | 1,2,3,10 | 4,5,6,11 | 7,8,9,12 2 | 1,2,3,11 | 4,5,6,12 | 7,8,9,10 3 | 1,4,7,12 | 2,5,8,10 | 3,6,9,11 INSTRUCTIONSLabel all coins 1 to 12 Perform 3 weighting according to the procedure table At each measurement, write "L" is left is heavier, "R" if right is heavier, "S" otherwise You have a 3-letter word. If it matches a coin from the final code table, this coin is heavier Otherwise, replace "L" by "R" and "R" by "L" in your 3-letter word from measurement. It will match a coin from the final code table, and this coin is lighter
P: 2,828
 Quote by isly ilwott The judges have analyzed your general solution and find it quite correct, though difficult to follow. You have won the overall prize, consisting of a cyber high-five and a wide smile. Congratulations! (That is, of course, less than meaningless if you googled the solution.)
I don't think the explicit solution matched the 1000 words. Sorry, I really thought the general procedure was clear enough. I think this is a nice problem. Finding the explicit solution originally took me like 3 days (thinking about it now and then). I did not google the general solution, it was taught to me (forced in my head by somebody else )
P: 72
 Quote by humanino I don't think the explicit solution matched the 1000 words. Sorry, I really thought the general procedure was clear enough. I think this is a nice problem. Finding the explicit solution originally took me like 3 days (thinking about it now and then). I did not google the general solution, it was taught to me (forced in my head by somebody else )
When I tried your general solution, it worked unfailingly through 5 tests wherein I chose the bad coin and its relative weight, thus determining the outcome of each weighing. It appears quite random when compared with the explicit solution. It is interesting that the general solution forces the swapping of coins from one tray to the other in subsequent weighings, a required move that was not that simply discovered in working the problem with the "if A then B" logic that seems quite more simply understood.
P: 2,828
 Quote by isly ilwott It is interesting that the general solution forces the swapping of coins from one tray to the other in subsequent weighings, a required move
The swapping is not required at all. I chose to do it because I thought it leads to a simpler (more beautiful, or clearer) structure in the end. The solution is unique only up to a re-shuffling of measurements. Left/right are mere conventions, just as it is a convention to write down "heavier" or "lighter" until we know whether the coin was actually heavier or lighter.
P: 72
 Quote by humanino The swapping is not required at all. I chose to do it because I thought it leads to a simpler (more beautiful, or clearer) structure in the end. The solution is unique only up to a re-shuffling of measurements. Left/right are mere conventions, just as it is a convention to write down "heavier" or "lighter" until we know whether the coin was actually heavier or lighter.
In your general solution, the swapping is forced by the instructions attached to each coin regarding its required position on the left or right of the scale (or the side). There are four coins assigned to each scale pan in all three weighings.

In my explicit solution (to be posted), the swapping is required to limit the number of weighings to three and still zero in on the errant coin. The third weighing is always one coin against another.
P: 2,828
 Quote by isly ilwott In your general solution, the swapping is forced by the instructions attached to each coin regarding its required position on the left or right of the scale (or the side). There are four coins assigned to each scale pan in all three weighings.
Oh there was a confusion. I thought you were mentioning the swapping I did just before the "final code table" in the explicit solution. This swapping, where I renamed L -> S, R -> L, and S -> R for the second measurement only was not mandatory at all.

I am not sure what you call "swapping" in the general solution above. You mean the renaming L->R and R->L in case the coin was lighter ?
P: 72
 Quote by humanino Oh there was a confusion. I thought you were mentioning the swapping I did just before the "final code table" in the explicit solution. This swapping, where I renamed L -> S, R -> L, and S -> R for the second measurement only was not mandatory at all. I am not sure what you call "swapping" in the general solution above. You mean the renaming L->R and R->L in case the coin was lighter ?
No. I mean that coins must be swapped from one pan to the other in subsequent weighings. In your general solution, this is automatic due to the prescribed positions of each coin in the three trials. In my explicit solution, one chooses by logic which side to put each coin on...but the swapping is required. However, in my explicit solution, some knowledge is gain about each coin in each weighing and some coins need not be placed on the scale again. The general solution offers no specific information about each coin until all weighings are completed.
P: 2,828
 Quote by isly ilwott some coins need not be placed on the scale again. The general solution offers no specific information about each coin until all weighings are completed.
That's wrong. The general solution displays in a unified manner a single series of 3 measurements. By no means does it prevent you to think when you do those measurements. If for instance the first measurement shows "balance" the faulty coin can only be among the 4 on the side. All the other ones are obviously fine.

 Related Discussions Special & General Relativity 9 Introductory Physics Homework 1 Introductory Physics Homework 4 General Math 6