12 coins and a balance beam scale

[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 anyone 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.

 

[rootX]

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 anyone 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

 

[humanino]

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.

 

[isly ilwott]

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.

 

[Jimmy Snyder]

Spoiler

Notice the indentation, it counts the weighings
Number the coins 1 through 12.
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)
----If they don't balance, the different coin is 11.
--If they do not balance, the different coin is among 9 and 10.
----Weigh 1 against 9.
----If they balance, the different coin is 10.
----If they do not balance, the different coin is 9.
If they do not balance, then determine which set is lighter. Renumber the coins
so that
1,2,3,4 is the lighter set and 5,6,7,8 is the heavier set.
--Weigh 1,5,6 against 2,7,8
--If they balance, then the different coin is among 3 and 4 and is the lighter o
f the two.
----Weigh 3 against 4. The lighter coin is the different one.
--If they do not balance and 2,7,8 is heavy then either 1 is light, or 7 or 8 is
heavy.
----Weigh 7 against 8.
----If they balance the different coin is 1.
----If they do not balance the different coin is the heavier one.
--If they do not balance and 1,5,6, is heavy, then either 2 is light, or 5 or 6
is heavy.
----Weigh 5 against 6.
----If they balance, the different coin is 2.
----If they do not balance, then ...

Did I mention that I am headed for Cabo San Lucas next week? That's at the southern tip of the Baja Peninsula in Mexico. I'll be there for little over a week, but the rest of my family will be there for 2 weeks. That's going to cost more than 12 coins, I assure you, even with one counterfeit. When I was younger, I didn't think I would enjoy a beach vacation. I wanted to visit famous sites, museums, places of interest, etc. But lately, I have been taking vacations in Merida, Mexico and in Aruba and I love it. I sit on the beach and do absolutely nothing. Except unwind of course. This will be my first time in Cabo and that means that I will spend some time looking around visiting the town and nearby tourist attractions. I don't look forward to that, but my whole family will be there so I have to make sure they enjoy the vacation too. I will suggest to my kids that they take advantage of snorkeling, wind-surfing, or whatever other water sports are to be found there. They don't usually go in for that kind of thing, so I will have to use a lot of persuasion.

But even better is the vacation my wife and I planned for February. We will leave the kids with a baby-sitter and I will take two weeks off. We are headed for Aruba. It will be our fourth time there and we both have the same agenda. No agenda. There really is nothing to do in Aruba, and I'm the man to do it. I used to think I would like to retire there but I have changed my mind about that. My wife wants to travel and I will tag along. She went to Europe by herself earlier this year and she had a blast. Now she wants to spend a year there touring about after I retire.

But enough about me, what are your vacation plans? Are you like I used to be, taking busy vacations rushing about to see everything? If today is Tuesday, this must be Rome kind of thing. Or relax on the beach? Or do you hate to take vacations? Perhaps you can't afford them. Perhaps you are waiting for the revolution so you can plunder my hard earned money and take a vacation with that. And when you get my money and go to Mexico with it, how many quarters are you going to toss to the the truly downtrodden Mexicans? As if the politburo would give any of it to you. Take a good look at yourself. You never take matters into your own hands, you complain about people who do, and you expect that come the revolution, people will start to look after you. Yeah, right! You disgust me with your lazy ways, your misinterpretation of what causes wealth and your pretense that you have morality on your side. Or perhaps you take local vacations on a long weekend. Maybe your house is a vacation spot for relatives that come to you.

My relatives rarely show up at my door. When I was a child, my parents would prepare a big meal for Passover, and Thanksgiving and relatives would come from all over the east coast to join us. How pleasant a time that was. I never graduated from the children's table. There were just to many grownups to accommodate. Now that I have my own home, I want to do the same. I invite everyone, but rarely do enough people show up for me to set up a children's table. Do you visit your relatives for holidays? Or are you too good for them. Just because you made it big in the business world you think you can buy and sell your own relatives. You know the price of everything and the value of nothing. You're not satisfied to work us to an early grave for starvation wages. No, you stick it to us with rapacious prices for gasoline, foreclosing on our houses and shirking your own taxes. It's people like you that give capitalism a bad name. Your false morality disgusts me. Come the revolution we will feast on you for Thanksgiving. Or do they come to your place?

I've looked at vacations from both sides now. From coming and going and still somehow, it's vacations' illusions I recall. I really don't know vacations at all.

Oops, sorry. Sometimes I get going and I lose all sense of where I am or what I'm doing. I remember once I thought I would take a quick shower before going out on a date, and I was enjoying myself so much I stayed under the water until it was too late to go out. No great loss, she wasn't that good for me anyway. She was one of those spoiled rich beautiful women who will support you all your life, but will drain you of all of your self-respect. But that's way off topic there. I hope I didn't go over a thousand words. I'll just finish up and go.

... the different coin is the heavier one.

 

[isly ilwott]

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.

 

[isly ilwott]

Notice the indentation, it counts the weighings
Number the coins 1 through 12.
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)
----If they don't balance, the different coin is 11.
--If they do not balance, the different coin is among 9 and 10.
----Weigh 1 against 9.
----If they balance, the different coin is 10.
----If they do not balance, the different coin is 9.
If they do not balance, then determine which set is lighter. Renumber the coins
so that
1,2,3,4 is the lighter set and 5,6,7,8 is the heavier set.
--Weigh 1,5,6 against 2,7,8
--If they balance, then the different coin is among 3 and 4 and is the lighter o
f the two.
----Weigh 3 against 4. The lighter coin is the different one.
--If they do not balance and 2,7,8 is heavy then either 1 is light, or 7 or 8 is
heavy.
----Weigh 7 against 8.
----If they balance the different coin is 1.
----If they do not balance the different coin is the heavier one.
--If they do not balance and 1,5,6, is heavy, then either 2 is light, or 5 or 6
is heavy.
----Weigh 5 against 6.
----If they balance, the different coin is 2.
----If they do not balance, then ...

Did I mention that I am headed for Cabo San Lucas next week? That's at the southern tip of the Baja Peninsula in Mexico. I'll be there for little over a week, but the rest of my family will be there for 2 weeks. That's going to cost more than 12 coins, I assure you, even with one counterfeit. When I was younger, I didn't think I would enjoy a beach vacation. I wanted to visit famous sites, museums, places of interest, etc. But lately, I have been taking vacations in Merida, Mexico and in Aruba and I love it. I sit on the beach and do absolutely nothing. Except unwind of course. This will be my first time in Cabo and that means that I will spend some time looking around visiting the town and nearby tourist attractions. I don't look forward to that, but my whole family will be there so I have to make sure they enjoy the vacation too. I will suggest to my kids that they take advantage of snorkeling, wind-surfing, or whatever other water sports are to be found there. They don't usually go in for that kind of thing, so I will have to use a lot of persuasion.

But even better is the vacation my wife and I planned for February. We will leave the kids with a baby-sitter and I will take two weeks off. We are headed for Aruba. It will be our fourth time there and we both have the same agenda. No agenda. There really is nothing to do in Aruba, and I'm the man to do it. I used to think I would like to retire there but I have changed my mind about that. My wife wants to travel and I will tag along. She went to Europe by herself earlier this year and she had a blast. Now she wants to spend a year there touring about after I retire.

But enough about me, what are your vacation plans? Are you like I used to be, taking busy vacations rushing about to see everything? If today is Tuesday, this must be Rome kind of thing. Or relax on the beach? Or do you hate to take vacations? Perhaps you can't afford them. Perhaps you are waiting for the revolution so you can plunder my hard earned money and take a vacation with that. And when you get my money and go to Mexico with it, how many quarters are you going to toss to the the truly downtrodden Mexicans? As if the politburo would give any of it to you. Take a good look at yourself. You never take matters into your own hands, you complain about people who do, and you expect that come the revolution, people will start to look after you. Yeah, right! You disgust me with your lazy ways, your misinterpretation of what causes wealth and your pretense that you have morality on your side. Or perhaps you take local vacations on a long weekend. Maybe your house is a vacation spot for relatives that come to you.

My relatives rarely show up at my door. When I was a child, my parents would prepare a big meal for Passover, and Thanksgiving and relatives would come from all over the east coast to join us. How pleasant a time that was. I never graduated from the children's table. There were just to many grownups to accommodate. Now that I have my own home, I want to do the same. I invite everyone, but rarely do enough people show up for me to set up a children's table. Do you visit your relatives for holidays? Or are you too good for them. Just because you made it big in the business world you think you can buy and sell your own relatives. You know the price of everything and the value of nothing. You're not satisfied to work us to an early grave for starvation wages. No, you stick it to us with rapacious prices for gasoline, foreclosing on our houses and shirking your own taxes. It's people like you that give capitalism a bad name. Your false morality disgusts me. Come the revolution we will feast on you for Thanksgiving. Or do they come to your place?

I've looked at vacations from both sides now. From coming and going and still somehow, it's vacations illusions I recall. I really don't know vacations at all.

Oops, sorry. Sometimes I get going and I lose all sense of where I am or what I'm doing. I remember once I thought I would take a quick shower before going out on a date, and I was enjoying myself so much I stayed under the water until it was too late to go out. No great loss, she wasn't that good for me anyway. She was one of those spoiled rich beautiful women who will support you all your life, but will drain you of all of your self-respect. But that's way off topic there. I hope I didn't go over a thousand words. I'll just finish up and go.

... the different coin is the heavier one.

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.

 

[humanino]

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...).

 

[Jimmy Snyder]

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.

 

[isly ilwott]

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.

 

[humanino]

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[/color]
2) LLR[/color]
3) LLS[/color]
4) LRL[/color]
5) LRR[/color]
6) LRS[/color]
7) LSL[/color]
8) LSR[/color]
9) LSS[/color]
10) RLL[/color]
11) RLR[/color]
12) RLS[/color]
13) RRL[/color]
14) RRR[/color]
15) RRS[/color]
16) RSL[/color]
17) RSR[/color]
18) RSS[/color]
19) SLL[/color]
20) SLR[/color]
21) SLS[/color]
22) SRL[/color]
23) SRR[/color]
24) SRS[/color]
25) SSL[/color]
26) SSR[/color]
27) SSS[/color]


Now among the green good ones, I get the following table :

coin # | first | second | third
     1 |   L   |    L   | R[/color]
     2 |   L   |    R   | L[/color]
     3 |   L   |    R   | R[/color]
     4 |   L   |    R   | S[/color]
     5 |   R   |    R   | S[/color]
     6 |   R   |    S   | L[/color]
     7 |   R   |    S   | R[/color]
     8 |   R   |    S   | S[/color]
     9 |   S   |    L   | L[/color]
    10 |   S   |    L   | R[/color]
    11 |   S   |    L   | S[/color]
    12 |   S   |    S   | L[/color]

Now let's look at the structure a little bit and re-arrange rationally. There are 3 regular groups (2,3,4) in blue[/color], (6,7,8) in green[/color] and (9,10,11) in purple[/color] which all do the same for the first two measurements. There is an additional "exceptional" structure with elements (1,5,12) in red[/color] 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[/color], then the green one[/color], then the purple one[/color] and finally the exceptional red one[/color].

FINAL CODE TABLE :

 old # | first | second | third | new #
     2 |   L   |    L   |   L   |     1[/color]
     3 |   L   |    L   |   R   |     2[/color]
     4 |   L   |    L   |   S   |     3[/color]
     6 |   R   |    R   |   L   |     4[/color]
     7 |   R   |    R   |   R   |     5[/color]
     8 |   R   |    R   |   S   |     6[/color]
     9 |   S   |    S   |   L   |     7[/color]
    10 |   S   |    S   |   R   |     8[/color]
    11 |   S   |    S   |   S   |     9[/color]
     1 |   L   |    S   |   R   |     10[/color]
     5 |   R   |    L   |   S   |     11[/color]
    12 |   S   |    R   |   L   |     12[/color]

Previous table is what I got by trial and error. Later on in an optimization algorithmic programing lecture, I learned 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

INSTRUCTIONS

• Label 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

 

[humanino]

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 )

 

[isly ilwott]

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.

 

[humanino]

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.

 

[isly ilwott]

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.

 

[humanino]

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 ?

 

[isly ilwott]

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.

 

[humanino]

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.

 

[isly ilwott]

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.

While that is certainly true, the general solution calls for the scale pans to have 4 coins on each side for each weighing...since you conclude nothing regarding the specific odd coin until all three weighings are completed and you have your sample "string" to match with the code assigned to each coin.

In the specific solution, the number of coins on each pan is determined by observations regarding whether a coin is good, light if odd or heavy if odd.

 

[humanino]

In my explicit solution (to be posted)

Do you plan do to it soon, or are you waiting for more participants ?

 

[isly ilwott]

Do you plan do to it soon, or are you waiting for more participants ?

Is that "soon" as in geological terms or "soon" as in a within the hour?

I can guarantee its being posted prior to my filing income tax returns for 2007. I have until October 15th to do that.

 

[humanino]

Is that "soon" as in geological terms or "soon" as in a within the hour?

Soon as in "within the lifetime of the discussion". But that depends on the participants of course. I have no data on the distribution of lifetime of interest in such a discussion. I can not tell you what is optimally appropriate. By Oct 15th I will clearly have lost interest for a while in this discussion. But maybe I'll come accros it by chance. And maybe other people are interested as well.

 

[isly ilwott]

Soon as in "within the lifetime of the discussion". But that depends on the participants of course. I have no data on the distribution of lifetime of interest in such a discussion. I can not tell you what is optimally appropriate. By Oct 15th I will clearly have lost interest for a while in this discussion. But maybe I'll come accros it by chance. And maybe other people are interested as well.

I'll try to have it posted by the end of next week...unless someone requests a delay. Except for two posts from jimmysnyder and one from rootx, this has been a dialog between you and me.

 

[GCT]

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 anyone 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.

If I remember correctly the solution deals with prime numbers.

 

[humanino]

Outline your solution in less than one thousand words.

I could display a trivially simple solution. Unfortunately it involves 12 pictures, which is more than 1 thousand words.

 

[isly ilwott]

I could display a trivially simple solution. Unfortunately it involves 12 pictures, which is more than 1 thousand words.

You are welcome to present it. I plan to explain it in words only, then follow up with sketches.

 

[isly ilwott]

You are welcome to present it. I plan to explain it in words only, then follow up with sketches.

Actually, I don't think the sketches are necessary. Here's my solution.



First weighing

(1 2 3 4) on left (5 6 7 8) on right 9 10 11 12 on table

If balanced, then you know that the odd coin is 9 10 11 or 12, AND that 1 2 3 4 5 6 7 and 8 are all good (G)



Second weighing then would be:

(9 10) on left (11 G) on right

If balanced, then 12 is odd.

Third weighing would then be (12) on left (G) on right with obvious determination of whether 12 is heavy or light.

Down left>12 heavy,
down right> 12 light


If the second weighing does not balance

Down left> 9 or 10 heavy OR 11 light

Then third weighing would be (9) left (10) right

If balanced, then 11 is light

Down left> 9 heavy,
down right> 10 heavy

That’s the easy part (when the first weighing is balanced)



If the first weighing does not balance, then

Down left> 1 2 3 or 4 is heavy OR 5 6 7 or 8 is light, AND 9 10 11 and 12 are all good (G)

Now remove two coins from one pan and one coin from the other pan and replace them all with G’s. It doesn’t matter which side you choose to remove two coins from. I choose to remove two from the left and one from the right. (You should easily see that the solution is quite similar if you remove two from the right and one from the left.)

Now pick any unknown coin from each pan and swap it to the other.

The second weighing is then


(1 5 G G) on left (2 6 7 G) on right 3 4 8 G on table

If balanced then the odd coin is 3 4 or 8. Since 3 and 4 are both candidates to be heavy,

The third weighing would then be (3) on left (4) on right

If balanced, the odd coin is 8 (and has already been determined to be light)

If not balanced, the heavy coin went down.


If the second weighing does not balance then

Down left>1 is heavy OR 6 or 7 is light (remembering that if 5 is bad, it is light and that if 2 is bad it is heavy...these are the two coins I swapped from one pan to the other.)

The third weighing would then be (6) on left (7) on right

Balance > 1 is heavy
Down left> 7 is light
Down right > 6 is light

If the second weighing went down on right, the 2 is heavy OR 5 is light, in which case the third weighing would be either one of them against a G.


Similar manipulations apply if the first weighing went down on the right.

 

[dipinsingh]

see the detailed solution in attached file.

 

[jvwert]

Form 3 main groups, each containing 1 and 3 coin sub-groups. Place one main group on each pan of a two pan balance - the third main group on the table. Observe the condition of the balance. This is the first weighing.

Rotate the 3 coin sub-groups (from pan A to the table, pan B to pan A, and from the table to pan B. Observe the condition of the balance. (second weighing)
If there is a change, it will identify the group that contains the odd coin and its relative weight. In this case, clear the balance of the other coins; split this group into single coins, placing two on the balance pans. This will be the third weighing and will identify the odd coin. We already know its relative weight, so problem solved.

If there is no change, one of the single coins is the odd coin, but its relative weight is not know. In this case, rotate the single coins. This would be the third weighing and will identify the odd coin and its relative weight. Problem solved.