wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Coin weight  w.  UNKNOWN NUMBER of faked coins
        
(Message started by: wonderful on Mar 20^th, 2008, 7:57pm)

Title: Coin weight w. UNKNOWN NUMBER of faked coins
Post by wonderful on Mar 20^th, 2008, 7:57pm

There are 24 coins with unknown number of faked coins. Design a scaling scheme to find out how many are faked coins using a minimal number of scalings.

Title: Re: Coin weight w. UNKNOWN NUMBER of faked coins
Post by Hippo on Mar 21^st, 2008, 1:18am

What are the allowed basic operations?
What does the "fake" mean?

Title: Re: Coin weight w. UNKNOWN NUMBER of f
Post by towr on Mar 21^st, 2008, 1:35am

Are all the fake coins equal, and are the real coins in the majority?

Title: Re: Coin weight w. UNKNOWN NUMBER of f
Post by Grimbal on Mar 21^st, 2008, 5:46am

Yeah, what if there are 23 fake coins, all of the same weight, and just one real coin?

Or if they all have the same weight, how can you tell if they are all real or all fake?

Title: Re: Coin weight w. UNKNOWN NUMBER of faked coins
Post by wonderful on Mar 21^st, 2008, 4:01pm

I also think the quesion can be stated clearer.

There are 24 coins. Some of these coins are faked. They are less than 24 in total. These faked coins have the same weight which differs from the real coin..

The question is to how one can know how many are faked coins using the minimum scalings.

Have A Great Day!

Title: Re: Coin weight w. UNKNOWN NUMBER of f
Post by rmsgrey on Mar 21^st, 2008, 9:29pm

There's still a lot of ambiguity...

For example, is it possible, given one fake and one genuine coin, to tell which is which in a single weighing?

What does a single weighing tell you? There are two basic types of scale: one tells you the exact weight of a single set of objects; the other compares two sets of objects, and tells you which, if either, is heavier.

If you know the weights of true coins and fake coins, then weighing all 24 in one go and working out how many must be fake to give that weight does it in one weighing.

Title: Re: Coin weight w. UNKNOWN NUMBER of faked coins
Post by wonderful on Mar 21^st, 2008, 11:53pm

Good discussions. To help you have a better idea, I would like to give you a quote from one of the papers:

"Consider a set of coins where each coin is either of the heavy type or the light type. The
problem is to identify the type of each coin with minimal number of weighings on a balanced
scale. The case that only one coin, called a counterfeit, has a different weight from others, is
a classic mathematical puzzle."

Title: Re: Coin weight w. UNKNOWN NUMBER of f
Post by rmsgrey on Mar 22^nd, 2008, 9:13am

An easy upper bound is 23 weighings by weighing each other coin against the first.

A lower bound is 15 weighings - there are 2²⁴=8,388,608 possible combinations of light/heavy coins^*. As there are three possible outcomes of each weighing, 14 weighings can only produce 3¹⁴=4,782,969 different outcomes, not enough to discriminate successfully. 15 weighings offers 3¹⁵=14,348,907 different outcomes, more than enough to distinguish - if they can be used efficiently enough.

So, if there is a scheme that works in 15 weighings, it will be optimal. Anything taking more than 23 can't be optimal.

*A strict count of the number of possible combinations would discount the all-light and all-heavy combinations (one of each) but their inclusion doesn't affect the calculated lower bound.

Title: Re: Coin weight w. UNKNOWN NUMBER of faked coins
Post by tohuvabohu on Mar 22^nd, 2008, 10:02am

Are you sure about that lower limit? We don't have to distinguish all those 2^24 combinations. We don't have to identify the fakes, just find out how many.
Suppose you weigh A-B
If one is lighter then weigh AB - every other pair. Lighter, equal, or heavy will identify the number for every pair, with a total of 12 weighings.
If A-B are equal, do AB-CD, then AB-EF, until you find an unequal. Swap a coin; AC-BD for example. That will identify a light-heavy pair that can be weighed against all remaining pairs. I think the total will be 13 weighings. And I doubt that's optimum.

Title: Re: Coin weight w. UNKNOWN NUMBER of f
Post by Hippo on Mar 22^nd, 2008, 12:36pm

OK so you have already started solving without knowing the question.

So question is probably as follows:
Each coin have weight either x or y.
x<y, but their ratio can be arbitrary (less than 1).

You can compare total weight of two sets of coins with any of results <,=, >. You are not allowed to weight the coins!

(A) The question is how many coins of weight x are among the given 24. If all coins have the same weight, both answers 0, 24 are considered correct.

OK there is 2nd variant:
(B) Identify type of each coin. If all coin have the same weight both answers x²⁴, y²⁴ are correct. Otherwise answer is a string from http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lbrace.gifx,yhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rbrace.gif²⁴.

(The log₃ 2²⁴ lower bound for (B) was already mentioned.)

Title: Re: Coin weight w. UNKNOWN NUMBER of faked coins
Post by tohuvabohu on Mar 22^nd, 2008, 2:52pm

The original question just said "how many..." But wonderful's quoted problem says "identify the type of each coin." I guess if he only wanted to know how many, then the referenced classic problem where there is one fake would be pretty simple to solve (hint: the answer is one).

Title: Re: Coin weight w. UNKNOWN NUMBER of faked coins
Post by wonderful on Mar 24^th, 2008, 1:44pm

Tohuvabohu has the correct answer to the original question. Now we can into the next question: what is the minimal number of weights to identify all the faked coints?

Title: Re: Coin weight w. UNKNOWN NUMBER of faked coins
Post by tohuvabohu on Mar 25^th, 2008, 12:51pm

Correction, I just gave a simple, non-optimal answer to part one.
rmsgrey's lower bound (or +1) is probably the answer to part two.

I can at least extend my method to lower part two's upper bound to 18.
Divide the 24 in 6 groups of 4. In each group weigh A-B, then AB-CD. A third weighing within the group will identify all four, unless all four are equal. (if the answers were unequal, unequal, you already know all four; if unequal, equal or equal, unequal then weigh C-D). If equal, equal, then a third weighing against any known coin will do it.
That's 18, unless all weights have been equal after 12 weighings, and you have no known coin to finish.
In that case, take one coin from each group (label a-f) and weigh a-b, and ab-cd. Again, one more will determine all 4 (ie, all 16) unless they're the same.
Weigh e-f, then, if necessary one of them with one of the first 16. Unless I'm mistaken, that will be 17.

So part two is bounded between 15 and 18. I think the answer is going to be 15, but it probably involves weighing 8 against 8, and changing combinations of weighed and unweighed coins each time. But it would be extremely difficult to describe an exact method or prove it works every time.

Title: Re: Coin weight w. UNKNOWN NUMBER of faked coins
Post by wonderful on Mar 25^th, 2008, 2:48pm

People in this forum are really smart. I truly enjoy sharing ideas with you guys. The original question is based on the paper by:

X.D. Hu and F.K. Hwang, A competitive algorithm for the counterfeit coin problem, preprint, 1992.

Soon after this paper, Peng-Jun Wan, Qifan Yang, Dean Kelley published a paper " A 3/2 log 3 -competitive algorithm for the counterfeit coin problem" in the Theoretical Computer Science 181 (1997) 347-356. In this paper, the authors suggest an improved algorithm. I intended to attach this paper here, however, it is too big. If you are interested please let me know so that I can email you.

Have A Great Day!