One night when I was hanging out with my high school friends, I came across a copy of the Old Farmer’s Almanac. In it was a puzzle…
You have 12 coins and a balance scale. One of the coins is counterfeit. You can use the balance scale exactly three times, placing however many coins you want in the pans. After those three weighing, you have to determine which coin is counterfeit and whether it is heavy or light.
There are no tricks. Eleven coins weigh the same and one coin is different, either heavier or lighter. You use the balance scale in a normal fashion.
This problem is likely all over the internet, so please don’t just go look it up as you will be robbing yourself of the challenge and my accounting in this post.
So I spent a few hours with my friends on the problem to no avail. The next day it was still in mind and I spent more time on it and was able to solve it – I was quite pleased with myself and with the elegance of the solution.
The spoiler under the button below is not the solution but rather something that I learned from solving the problem that stuck with me. It is in a spoiler because it is very big hint.
Advance the clock to when I was a Post-Doc…I’m reading old Byte magazines in the library, and I come across an article titled “A Ternary State of Affairs”. Feb. 1987, p319, by Robert T. Kurosaka, linked here – I highly recommend that you take a look.
In the article was a BASIC program to solve the 12 coins problem! I copied the article to take home and went about my business.
Later, I typed in the listing (corresponding to listing 2a in the article and I have attached it to the post. If you have GWBASIC and a computer that will run it, the program still works.
At the time, I was impressed with the program and I read the article, but I was not impressed with the explanation and, frankly, I did not understand this ternary interpretation. More specifically, I did not understand why the notation/explanation was necessary.
Advance the clock many years forward, to this morning, when I ran the program again and read the article again. Now, I have a very different view. I feel much more comfortable with the ternary notation and how it is being explained – I guess what I am saying is that I almost understand it and am much more appreciative.
What I had thought was an unnecessary objectification for something that I did, intuitively, was actually very brilliant. This morning when I read it, the point that: if 7 weighings are allowed, you can find the one counterfeit out of 1092 coins, was not missed! I was not going to be able to do that mentally.
Not sure there is a profound moral or even point to my anecdote other than, this is a pretty cool problem and a pretty cool solution.
edited to correct article link
You have 12 coins and a balance scale. One of the coins is counterfeit. You can use the balance scale exactly three times, placing however many coins you want in the pans. After those three weighing, you have to determine which coin is counterfeit and whether it is heavy or light.
There are no tricks. Eleven coins weigh the same and one coin is different, either heavier or lighter. You use the balance scale in a normal fashion.
This problem is likely all over the internet, so please don’t just go look it up as you will be robbing yourself of the challenge and my accounting in this post.
So I spent a few hours with my friends on the problem to no avail. The next day it was still in mind and I spent more time on it and was able to solve it – I was quite pleased with myself and with the elegance of the solution.
The spoiler under the button below is not the solution but rather something that I learned from solving the problem that stuck with me. It is in a spoiler because it is very big hint.
For me, the key was finally realizing that you know much more about each coin after each weighing than you might, at first, realize. So, if you weigh coins 1,2,3,4 against 5,6,7,8 and the balance scale reads no difference, then you know that coins 1, 2,3,4,5,6,7,8 are true and the counterfeit is one of 9.10,11,12. Once I grasped that concept, I was able to quickly figure out how to do it with each possible outcome.
Advance the clock to when I was a Post-Doc…I’m reading old Byte magazines in the library, and I come across an article titled “A Ternary State of Affairs”. Feb. 1987, p319, by Robert T. Kurosaka, linked here – I highly recommend that you take a look.
In the article was a BASIC program to solve the 12 coins problem! I copied the article to take home and went about my business.
Later, I typed in the listing (corresponding to listing 2a in the article and I have attached it to the post. If you have GWBASIC and a computer that will run it, the program still works.
At the time, I was impressed with the program and I read the article, but I was not impressed with the explanation and, frankly, I did not understand this ternary interpretation. More specifically, I did not understand why the notation/explanation was necessary.
Advance the clock many years forward, to this morning, when I ran the program again and read the article again. Now, I have a very different view. I feel much more comfortable with the ternary notation and how it is being explained – I guess what I am saying is that I almost understand it and am much more appreciative.
What I had thought was an unnecessary objectification for something that I did, intuitively, was actually very brilliant. This morning when I read it, the point that: if 7 weighings are allowed, you can find the one counterfeit out of 1092 coins, was not missed! I was not going to be able to do that mentally.
Not sure there is a profound moral or even point to my anecdote other than, this is a pretty cool problem and a pretty cool solution.
edited to correct article link
Attachments
-
1.9 KB Views: 3
Last edited: