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 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.
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.
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 accomodate. 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.
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.
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.
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...).
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.
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.
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 : Code (Text): coin # | first | second | third [color=red] 1 | L | L | R[/color] [color=blue] 2 | L | R | L[/color] [color=blue] 3 | L | R | R[/color] [color=blue] 4 | L | R | S[/color] [color=red] 5 | R | R | S[/color] [color=green] 6 | R | S | L[/color] [color=green] 7 | R | S | R[/color] [color=green] 8 | R | S | S[/color] [color=purple] 9 | S | L | L[/color] [color=purple] 10 | S | L | R[/color] [color=purple] 11 | S | L | S[/color] [color=red] 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, (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 : Code (Text): old # | first | second | third | new # [color=blue] 2 | L | L | L | 1[/color] [color=blue] 3 | L | L | R | 2[/color] [color=blue] 4 | L | L | S | 3[/color] [color=green] 6 | R | R | L | 4[/color] [color=green] 7 | R | R | R | 5[/color] [color=green] 8 | R | R | S | 6[/color] [color=purple] 9 | S | S | L | 7[/color] [color=purple] 10 | S | S | R | 8[/color] [color=purple] 11 | S | S | S | 9[/color] [color=red] 1 | L | S | R | 10[/color] [color=red] 5 | R | L | S | 11[/color] [color=red] 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 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 Code (Text): 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
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.
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.
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.
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.