12 coins and a balance beam scale

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

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.

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.

I haven't counted the words as your "solution" does not describe the set-up of each weighing.

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

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 )

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.

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 ?