Ternary Notation: Revisiting 12 coins [Mathematical Recreation]

Discussion in 'Math' started by Raymond Genovese, Jan 12, 2018 at 12:51 PM.

  1. Raymond Genovese

    Thread Starter Member

    Mar 5, 2016
    430
    275
    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
     
    Last edited: Jan 12, 2018 at 4:06 PM
  2. WBahn

    Moderator

    Mar 31, 2012
    21,073
    6,061
    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.
     
  3. Raymond Genovese

    Thread Starter Member

    Mar 5, 2016
    430
    275

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

    Moderator

    Mar 31, 2012
    21,073
    6,061
    I'll try to take a look. Your link appears to have an error -- perhaps this is what you meant?

    https://archive.org/details/byte-magazine-1987-02

    The PDF is over 150 MB, so I won't be downloading that any time soon.
     
  5. joeyd999

    AAC Fanatic!

    Jun 6, 2011
    3,364
    4,477
    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.
     
  6. Raymond Genovese

    Thread Starter Member

    Mar 5, 2016
    430
    275
    Yes, that is the issue. I have no idea how to otherwise get at the article - this morning, I just printed out the six article pages.
     
  7. Raymond Genovese

    Thread Starter Member

    Mar 5, 2016
    430
    275
    I ran a copy of GWBASIC (and the program) on my XP with no problem but Win 7 scolded me and said No.
     
  8. WBahn

    Moderator

    Mar 31, 2012
    21,073
    6,061
    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.
     
  9. Raymond Genovese

    Thread Starter Member

    Mar 5, 2016
    430
    275
    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.
     
Loading...