| |
 |
|
| Science Forum Index » Mathematics Forum » can Huffman coding method be used to coin weighing problem? |
|
Page 1 of 1 |
|
| Author |
Message |
| lucy |
 Posted: Fri Feb 11, 2005 12:12 am |
|
|
|
Guest
|
Suppose one has n coins, among which there may or may not be ONE counterfeit
coin.
If there is a counterfeit coin, it may be either heavier or lighter than the
other coins.
The coins are to be weighed by a balance.
What is the coin weighing strategy for k = 3 weighings and 12 coins?
I am trying to figure this weighing scheme out by using optimal Huffman
coding scheme to achieve the minimal code length...
How to do that? |
|
|
| Back to top |
|
| M.J.T. Guy |
| Posted: Fri Feb 11, 2005 1:41 pm |
|
|
|
Guest
|
In article <cuher9$d8o$1@news.Stanford.EDU>, lucy <losemind@yahoo.com> wrote:
Quote: Suppose one has n coins, among which there may or may not be ONE counterfeit
coin.
If there is a counterfeit coin, it may be either heavier or lighter than the
other coins.
The coins are to be weighed by a balance.
What is the coin weighing strategy for k = 3 weighings and 12 coins?
I am trying to figure this weighing scheme out by using optimal Huffman
coding scheme to achieve the minimal code length...
Dunno what relevence Huffman has, but the straightforward approach is
to use the fact that k weighings can distinguish at most 3^k cases.
Initially, we have 25 cases (each coin heavy/light, or all coins OK)
which is less that 27, so we are OK. After the first weighing,
these cases must be divided into 3 groups of <= 9 each. If we initially
weigh n coins against n coins, what value must n have?
Mike Guy |
|
|
| Back to top |
|
| Jonathan Campbell |
| Posted: Sat Feb 12, 2005 9:07 am |
|
|
|
Guest
|
"lucy" <losemind@yahoo.com> wrote in message news:<cuher9$d8o$1@news.Stanford.EDU>...
Quote: Suppose one has n coins, among which there may or may not be ONE counterfeit
coin.
If there is a counterfeit coin, it may be either heavier or lighter than the
other coins.
The coins are to be weighed by a balance.
What is the coin weighing strategy for k = 3 weighings and 12 coins?
I am trying to figure this weighing scheme out by using optimal Huffman
coding scheme to achieve the minimal code length...
How to do that?
See D.J.C. Mackay, Information Theory, Inference, and Learning
Algorithms, Cambridge Univ. Press, 2003. At the beginning of the
chapter on Source Coding, Exercise 4.1, p. 66, andwered on p. 69.
Marvellous book.
Mackay has a machine readable version of it on his website.
Best regards,
Jon C. |
|
|
| Back to top |
|
| Guest |
| Posted: Sat Feb 12, 2005 10:16 am |
|
|
|
|
Closer inspection indicates that Mackay's exercise has a slight
difference to the one posed by Lucy, namely that in Mackay's, that one
item is different is given. However, as Mike Guy points out, the number
of cases is now 25, < 3^3, and some of the 'impossible' leaves in
Mackay's tree are possible in this problem, so that (I think) the book
strategy is optimal for this problem too.
Not so clear however. The more obvious first experiment: weigh 1..6
versus 7..12, in the present problem does have three possible outcomes
(information 1.6 bits), whereas in the book problem this experiment
yields only 1.0 bits of information.
Jon C. |
|
|
| Back to top |
|
|
|
All times are GMT - 5 Hours
The time now is Sat Jul 04, 2009 10:23 pm
|
|