Author |
Topic: Coin weight w. UNKNOWN NUMBER of faked coins (Read 3145 times) |
|
wonderful
Full Member
Posts: 203
|
 |
Coin weight w. UNKNOWN NUMBER of faked coins
« on: Mar 20th, 2008, 7:57pm » |
 Quote  Modify
|
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.
|
| « Last Edit: Mar 20th, 2008, 7:58pm by wonderful » |
 IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender: 
Posts: 919
|
|
Re: Coin weight w. UNKNOWN NUMBER of faked coins
« Reply #1 on: Mar 21st, 2008, 1:18am » |
Quote Modify
|
What are the allowed basic operations?
What does the "fake" mean?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Coin weight w. UNKNOWN NUMBER of f
« Reply #2 on: Mar 21st, 2008, 1:35am » |
Quote Modify
|
Are all the fake coins equal, and are the real coins in the majority?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Coin weight w. UNKNOWN NUMBER of f
« Reply #3 on: Mar 21st, 2008, 5:46am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
wonderful
Full Member
Posts: 203
|
|
Re: Coin weight w. UNKNOWN NUMBER of faked coins
« Reply #4 on: Mar 21st, 2008, 4:01pm » |
Quote Modify
|
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!
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Coin weight w. UNKNOWN NUMBER of f
« Reply #5 on: Mar 21st, 2008, 9:29pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
wonderful
Full Member
Posts: 203
|
|
Re: Coin weight w. UNKNOWN NUMBER of faked coins
« Reply #6 on: Mar 21st, 2008, 11:53pm » |
Quote Modify
|
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."
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Coin weight w. UNKNOWN NUMBER of f
« Reply #7 on: Mar 22nd, 2008, 9:13am » |
Quote Modify
|
An easy upper bound is 23 weighings by weighing each other coin against the first.
A lower bound is 15 weighings - there are 224=8,388,608 possible combinations of light/heavy coins*. As there are three possible outcomes of each weighing, 14 weighings can only produce 314=4,782,969 different outcomes, not enough to discriminate successfully. 15 weighings offers 315=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.
|
|
IP Logged |
|
|
|
tohuvabohu
Junior Member
Gender:
Posts: 102
|
|
Re: Coin weight w. UNKNOWN NUMBER of faked coins
« Reply #8 on: Mar 22nd, 2008, 10:02am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Coin weight w. UNKNOWN NUMBER of f
« Reply #9 on: Mar 22nd, 2008, 12:36pm » |
Quote Modify
|
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 x24, y24 are correct. Otherwise answer is a string from  x,y 24.
(The log3 224 lower bound for (B) was already mentioned.)
|
| « Last Edit: Mar 22nd, 2008, 3:17pm by Hippo » |
IP Logged |
|
|
|
tohuvabohu
Junior Member
Gender:
Posts: 102
|
|
Re: Coin weight w. UNKNOWN NUMBER of faked coins
« Reply #10 on: Mar 22nd, 2008, 2:52pm » |
Quote Modify
|
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).
|
|
IP Logged |
|
|
|
wonderful
Full Member
Posts: 203
|
|
Re: Coin weight w. UNKNOWN NUMBER of faked coins
« Reply #11 on: Mar 24th, 2008, 1:44pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
tohuvabohu
Junior Member
Gender:
Posts: 102
|
|
Re: Coin weight w. UNKNOWN NUMBER of faked coins
« Reply #12 on: Mar 25th, 2008, 12:51pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
wonderful
Full Member
Posts: 203
|
|
Re: Coin weight w. UNKNOWN NUMBER of faked coins
« Reply #13 on: Mar 25th, 2008, 2:48pm » |
Quote Modify
|
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!
|
| « Last Edit: Mar 25th, 2008, 2:49pm by wonderful » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print