Ternary Notation: Revisiting 12 coins [Mathematical Recreation]

Thread Starter

Raymond Genovese

Joined Mar 5, 2016
1,658
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.

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

Last edited:

WBahn

Joined Mar 31, 2012
26,143
I think I have a solution. It took me the better part of two hours. I haven't tested it (or even sanity checked it) because I need to get some other things done. Maybe later.

Let's see how far I can make it.

The approach I am going to take is to assign the coins to three groups for each weight, call them L,C,R. The coins in Group L go in the left pan, the coins in Group R go in the right pan, and the coins in Group C don't get weighed.

The goal is to assign the group so that the fake is encoded into the outcomes for one of the pans. I'm going to use the basic concepts from Bloom filters and superimposed codes. The idea is you encode the items a number of different ways and then ask if the one you are looking for is included in each test. Based on the ones it is or is not included in, you can figure out which item was selected.

On each weighing, the left pan is either lighter, the same, or heavier than the other pan. Call these 0, 1, and 2 respectively (or L,S,H). That means that we can encode the weighing outcomes as a three-digit base-3 number with potentially 27 different outcomes. The goal is to partition the groups so that 24 of these are unique indicating which coin is different (12 possible values) and whether it is lighter or heavier (2 possible outcomes) for the combined 24. If successful, it will be interesting to examine the remaining three outcomes and see why they can't occur.

Next I'm going to explore a route that I don't think will work in the end, but it will hopefully expose enough of the structure that I'm looking for to get it on the next round.

If coin 1 is lighter, the I want the pan weighings to be L,S,H. That means that the pan assignments for coin 1 needs to be L,C,R. Since the assignments will be the same for the case when coin 1 is heavier, those weighings will be H,S,L.

So that gives me some insight into the structure. Whatever L and H are in one encoding, the encoding with them reversed must also be present. Also, the encodings SSS, LLL, and HHH may not be useful. If that's true, then those would be the three unused encodings.

So that means that the encodings need to be

SSL/SSH
SLS/SHS
SLL/SHH
SLH/SHL
LSS/HSS
LSL/HSH
LSH/HSL
LLS/HHS
LLH/HHL
LHS/HLS
LHL/HLH
LHH/HLL

Now I should just have to assign the coins to groups to make this happen.

First, it would appear that I will have three coins that will need to be in every weighing since I have three of the twelve pairs that don't have any S outcomes. So let's assign those first.

Coin 1: LLR: LLH/HHL

Actually, I think that shows how I group the coins. The only concern is whether I end up with the same number of coins in each pan on each weighing. Let's see

Coin 0 (CCL): SSL/SSH
Coin 1 (CLC): SLS/SHS
Coin 2 (CLL): SLL/SHH
Coin 3 (CLR): SLH/SHL
Coin 4 (LCC): LSS/HSS
Coin 5 (LCL): LSL/HSH
Coin 6 (LCR): LSH/HSL
Coin 7 (LLC): LLS/HHS
Coin 8 (LLR): LLH/HHL
Coin 9 (LRC): LHS/HLS
Coin 10 (LRL): LHL/HLH
Coin 11 (LRR): LHH/HLL
Weighing #1: (4,5,6,7,8,9,10,11) (none)

Obviously that doesn't work. But I can swap the outcomes to move the coins to the other pan on the same weighing. First, the total number of coins in all weighings must be even. They are, 24 total. That's reassuring.

Next I notice that there are three coins in the "center" pan for each weighing, so each one consist of eight coins in each pan.

For the present assignments, in the left pans for the three weighings I have {8,5,4} coins while on the right I have {0,3,4}. So I need to move a net of five coins from left to right and four of these have to come from sets that have an L in the first weighing. In choosing those four, there has to be a net of 1 in the second weighing and no net in the last weighing.

To get the net 1 in the second, I can pick {L,C,C,C} or {L,L,R,C} and for the net 0 in the last weighing I can pick {C,C,C,C}, {L,R,C,C} or {L,L,R,R} (or some permutation of each).

If I pick coins 4 though 7 I get {C,C,C,L} for the center and {C,L,R,C} for the third.

So this makes my groupings:

Coin 0 (CCL): SSL/SSH
Coin 1 (CLC): SLS/SHS
Coin 2 (CLL): SLL/SHH
Coin 3 (CLR): SLH/SHL
Coin 4 (RCC): HSS/LSS
Coin 5 (RCR): HSH/LSL
Coin 6 (RCL): HSL/LSH
Coin 7 (RRC): HHS/LLS
Coin 8 (LLR): LLH/HHL
Coin 9 (LRC): LHS/HLS
Coin 10 (LRL): LHL/HLH
Coin 11 (LRR): LHH/HLL

So the L/R groups for each weighing become:

Weighing #1: (8,9,10,11) / (4,5,6,7)
Weighing #2: (1,2,3,8) / (7,9,10,11)
Weighing #3: (0,2,6,10) / (3,5,8,11)

I could, of course, renumber these however would be convenient.
 

Thread Starter

Raymond Genovese

Joined Mar 5, 2016
1,658
I think I have a solution. It took me the better part of two hours. I haven't tested it (or even sanity checked it) because I need to get some other things done. Maybe later.

I really hope you can find the time to read that article, I would very much like to know what you think of it.:)
 

Thread Starter

Raymond Genovese

Joined Mar 5, 2016
1,658
On Linux, there are DOSBox and DOSEmu, both of which run GWBASIC just fine.

On Debian/Ubuntu/Mint:

sudo apt-get dosbox
sudo apt-get dosemu

There are probably Windows versions available -- I haven't checked.
I ran a copy of GWBASIC (and the program) on my XP with no problem but Win 7 scolded me and said No.
 

WBahn

Joined Mar 31, 2012
26,143
I really hope you can find the time to read that article, I would very much like to know what you think of it.:)
I looked at the "full text" version, which is pretty hard to navigate. No page numbers or indication of page breaks. No graphics, so I had to guess at what they might have been conveying. Plus, the article seemed to stop suddenly (my guess is it was continued somewhere later in the issue).

But I think I got the gist. If so, what they did was to express each coin index in base 3 and use that to determine which pan that coin went into for each weighing such that the outcomes of the three weighings can be directly interpreted as the index of the bad coin.

That's the direction I originally wanted to go, but in base 3 you can encode 27 values and I was very concerned that just encoding the first 12 was setting things up for disaster.

But they also mentioned using two's complement (which, in base 3, is more properly referred to as diminished-radix complement). That pairs each index with its additive inverse, which is exactly what I did in pairing up the outcomes. Because they started their indices at 1 instead of 0, they skipped the SSS encoding, which is it's own complement. They also skip the largest index and it's complement, which correspond to the LLL/HHH pair that I skipped. I don't know that this was actually necessary.

So I think I can see how to assign the coins to pans so that the weighings directly form the index of the bad coin. That makes it more elegant than my solution, which requires a table look-up. But I should be able to easily remap my coin numbers into theirs.
 

Thread Starter

Raymond Genovese

Joined Mar 5, 2016
1,658
I looked at the "full text" version, which is pretty hard to navigate. No page numbers or indication of page breaks. No graphics, so I had to guess at what they might have been conveying. Plus, the article seemed to stop suddenly (my guess is it was continued somewhere later in the issue).

But I think I got the gist. If so, what they did was to express each coin index in base 3 and use that to determine which pan that coin went into for each weighing such that the outcomes of the three weighings can be directly interpreted as the index of the bad coin.

That's the direction I originally wanted to go, but in base 3 you can encode 27 values and I was very concerned that just encoding the first 12 was setting things up for disaster.

But they also mentioned using two's complement (which, in base 3, is more properly referred to as diminished-radix complement). That pairs each index with its additive inverse, which is exactly what I did in pairing up the outcomes. Because they started their indices at 1 instead of 0, they skipped the SSS encoding, which is it's own complement. They also skip the largest index and it's complement, which correspond to the LLL/HHH pair that I skipped. I don't know that this was actually necessary.

So I think I can see how to assign the coins to pans so that the weighings directly form the index of the bad coin. That makes it more elegant than my solution, which requires a table look-up. But I should be able to easily remap my coin numbers into theirs.
I think that you are basically following the same path as the article and I am impressed. I knew nothing of this and am still trying to appreciate the ternary classification - at least in a way that could do anything.

He uses and needs both ternary and the two's complement ternary - he also classifies the coin numbers as cw or ccw corresponding to changes. All this preparation is what makes the solution in the short BASIC program possible and easy - and it is extendable beyond 12 coins. That part was very difficult for me to see and I think it is brilliant, at least to me.

Also, the first problem in the article - about how many different weights you need to to measure any amount up to xxx, I see now as something called Bachet's problem (PDF link).

I don't know if I should still feel good that I was able to solve this way back when by 'brute force' while knowing or appreciating absolutely nothing about these matters.

Finally, I extracted a pdf of only the article from Byte magazine. If it is not kosher to do so, I shall remove it and sorry.

Attachment: PDF of the Article, "A Ternary State of Affairs" by Robert T Kurosaka that was published in Byte magazine, Feb, 1987, p 319-328. A pdf of the entire issue is available at archive.com here.
 

Attachments

Top