CTK Exchange
CTK Wiki Math
Front Page
Movie shortcuts
Personal info
Awards
Terms of use
Privacy Policy

Interactive Activities

Cut The Knot!
MSET99 Talk
Games & Puzzles
Arithmetic/Algebra
Geometry
Probability
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
My Logo
Math Poll
Other Math sit's
Guest book
News sit's

Recommend this site

Manifesto: what CTK is about Search CTK Buying a book is a commitment to learning Table of content Products to download and subscription Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

CTK Exchange

Subject: "Error in 12 Coins, 3 Weighings problem?"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange Thoughts and Suggestions Topic #76
Reading Topic #76
H.Gabryjelski
guest
Dec-30-09, 05:57 PM (EST)
 
"Error in 12 Coins, 3 Weighings problem?"
 
   This is in reference to the generally good Description of the 12 Coin, 3 Weighings problem.

Given the following:
The website indicates a generic algorithm of X = 3^N - 3.

  • X is the number of possibilities.
  • N is the number of weighing allowed
  • The base number 3 represents the outcomes of the weighing (H, E, L) for a given coin.
  • The represents three disallowed results of all H, all E, and all L.

    Question #1:
    My question is on the correctness of this equation.

    The removal of a column of all-E is correct. Since the problem requires determination of whether the coin is heavy or light, and an all-E column fails to provide this information, it cannot be allowed.

    However, I am wondering about the removal of both the all-H and all-L options. My guess is that someone realized that if one column started with all L, and the other column started with all H, the final results would not indicate which of the two items was the counterfeit. As a result, the person over-generalized to reject both all-L and all-H in the top half of the column. However, because there is no inherent problem with an all-H column, I am wondering why the restriction was not simply against an all-H OR all-L column.

    Can you help me understand how allowing EITHER an all-H OR an all-L would be problematic?

    If no such problem exists, then the algorithm would be slightly modified to be:
    X = 3^N - 2, for N >= 2. (NOTE: this is closer, but still wrong... see below...)

    Let's consider the smallest two values:

    2. For two weighings, the site indicates only six possible outcomes. However, there seem to be eight valid outcomes. The six listed are HE, LE; LH, HL; and EL, EH. I ask now about HH, LL.

    HH would indicate the fake coin is heavy, L would indicate it is light. Thus, the problem is not inherent in the specific column result of HH or LL. What is the problem?

    HLE H
    EHL H
    123 4
    ELH L
    LHE L

    The problem is: how do you equally split HLEH on the scale for weighing? There are two H, one L, and one E. Thus, to allow the fourth item would require an additional "known good" ball/coin.

    So, what is really needed, rather than subtracting by a fixed amount, is to fix the possibilities to a multiple of three.

    X = (3^N - 1) - ((3^N-1) MODULO 3), for N >= 1

    Now, I realize that, because the 3^N is always a multiple of 3, and because we're subtracting a fixed number (1) that is less than 3, the result of ((3^N-1) MODULO 3) will always be 2. But, that simply hides the purpose or reasoning of the WHY of the equation, and keeps it looking like magic.

    The exclusion of the columns indicated happens to be a nice way to get a set of weighings that always works, but there's really no derivation provided.


    Question #2:
    Can you note the variation in the problem, where the determination of the counterfeit coin/ball is required, but the information as to whether it is heavier/lighter is not a required result? In 3 weighings, one can pick the counterfeit from 13 such coins/balls.

    However, the algorithm is not as clean.


  •   Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
    alexbadmin
    Charter Member
    2466 posts
    Jan-01-10, 06:11 PM (EST)
    Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
    1. "RE: Error in 12 Coins, 3 Weighings problem?"
    In response to message #0
     
       Have you considered the author's stipulation that no ball appears three times on the same side? If it is possible to satisfy this requirement then surely neither HHH or LLL is possible. So the correct question should be whether or not the stipulation is enforceable. As the specific distribution of the balls that follows the two arrays shows, the answer is in affirmative.


      Alert | IP Printer-friendly page | Reply | Reply With Quote | Top

    Conferences | Forums | Topics | Previous Topic | Next Topic

    You may be curious to have a look at the old CTK Exchange archive.
    Please do not post there.

    Copyright © 1996-2018 Alexander Bogomolny

    Search:
    Keywords:

    Google
    Web CTK