makaren@alberta.UUCP (Darrell Makarenko) (04/18/85)
Ok we have seen the well known weighing problem of the
twelve coins, one counterfeit (lighter or heavier) , three
weighings find the phoney.
Lets generalize the problem as follows.
Given that there is one counterfeit in a pile of coins
and that it is lighter or heavier than the others (you dont
know which). Derive the formula F(n) that will tell you
that if you are allowed n weighings on a balance scale what
is the maximum number of coins there could be where you could
find the counterfeit among them and whether it is heavier or lighter.
From the original problem and numerous solutions posted
we know that F(3) >= 12. i.e. we can determine a counterfeit
in at least twelve coins given three weighings.
Derive F, either in closed form or failing that place limits
on F eg. F(n) < n!, F(n) > n**2 etc.
You dont have to describe the n weighings necessary to find the
coin, just the formula as to the max number of coins there could be
such that it is possible to find it in n weighings.
Post solutions or ideas to net.puzzle.steve@siemens.UUCP (04/19/85)
I already answered this question, but it's quite possible my response never made it out to the net. Here's the relevant part: > /* Written 10:02 am Apr 11, 1985 by steve@siemens in siemens:net.puzzle */ > > To prove you cannot distinguish which one is heavy or light from 13 > coins, in three weighings. The first weighing must split the 26 cases > into three sets of no more than 9 cases each. (Because the following two weighings can distinguish at most 9 cases.) > It must be a weighing of > n coins against n coins, and will divide the 26 cases into 2n, 26-2n, > and 2n cases for outcomes of <, =, and > respectively. For no integral > value of n is 2n <= 9 and 26-2n <= 9. Therefore there is no way to > determine which of 13 coins is heavy or light in 3 weighings. > > In fact, by just looking at the first weighing you can show by a > generalization of the proof above that for w weighings, an upper bound on > the number of coins you can distinguish is > (3^w - 3)/2 > (which is an integer), and the first weighing must be 1/3 vs 1/3 of > those coins, which is also integral. Can you actually find the bad coin > (and whether it is heavy or light) from 39 coins in 4 weighings? > > Steve Clark ...princeton!siemens!steve > /* End of text from siemens:net.puzzle */
heddaya@harvard.ARPA ( Solom) (04/19/85)
> Ok we have seen the well known weighing problem of the > twelve coins, one counterfeit (lighter or heavier) , three > weighings find the phoney. > > Lets generalize the problem as follows. > Given that there is one counterfeit in a pile of coins > and that it is lighter or heavier than the others (you dont > know which). Derive the formula F(n) that will tell you > that if you are allowed n weighings on a balance scale what > is the maximum number of coins there could be where you could > find the counterfeit among them and whether it is heavier or lighter. Here is a derivation of F(n), the maximum number of items for which the problem can be solved in n weighs. I give only a proof sketch, using the 12 item problem as an example, and I also give a hint as to how a complete formal proof can be constructed. I'll show that: F(n) <= 0.5 * (3**n) First, the problem: the distinguished item (x) can be any one of the 12 items, and it can be either heavier or lighter than the 11 identical items. Therefore, we have 24 distinct states from which we have to select one. Second, the means: we have a balance that can tell us one of three things (<, =, >) every time we weigh two groups of items against each other. So, it seems that the best we can do is eliminate 2/3 of the possible states by any one weigh (the weigh tells which third is right). It is not possible to eliminate more, since you don't know before hand which of the three outcomes is going to happen. In our case of 24 states, the first weigh can eliminate at most 16 states (leaving 8), the second at most 6 (leaving 2), the third at most 1 (giving us the solution). So, we cannot do better than 3 weighs. In general, for k items (2*k states), we cannot do it in less than log to the base 3 (2*k); taking the lowest integer higher than that number, of course. To formally prove this lower bound, on can use a decision tree argument, where every decision can have 3 outcomes, as someone pointed out before. Let the number of weighs be n, then, what we showed was that: n >= log3 (2*k) so, k <= 0.5 * (3**n) The constructive result of this analysis is that each weigh must be designed in such a way that each of the 3 possible outcomes implies at least one third of the possible states of x, the distinguished item. I have a sort of derivation of a solution for the 12 item problem using this condition (I can mail it to interested people). It is conceivable that, as n increases and/or k approaches its upper bound, this condition becomes harder and harder to achieve. It may even become impossible, in which case our lower bound on the number of weighs becomes unachievable. Abdelsalam Heddaya
muffy@lll-crg.ARPA (Muffy Barkocy) (04/22/85)
In article <455@alberta.UUCP> makaren@alberta.UUCP (Darrell Makarenko) writes: > > Ok we have seen the well known weighing problem of the > twelve coins, one counterfeit (lighter or heavier) , three > weighings find the phoney. > > Lets generalize the problem as follows. > Given that there is one counterfeit in a pile of coins > and that it is lighter or heavier than the others (you dont > know which). Derive the formula F(n) that will tell you > that if you are allowed n weighings on a balance scale what > is the maximum number of coins there could be where you could > find the counterfeit among them and whether it is heavier or lighter. > > From the original problem and numerous solutions posted > we know that F(3) >= 12. i.e. we can determine a counterfeit > in at least twelve coins given three weighings. > > Derive F, either in closed form or failing that place limits > on F eg. F(n) < n!, F(n) > n**2 etc. > You dont have to describe the n weighings necessary to find the > coin, just the formula as to the max number of coins there could be > such that it is possible to find it in n weighings. > > Post solutions or ideas to net.puzzle. There are 2n+1 possible solutions, either one of the n coins is light (n), one is heavy (n) or they are all equal (1). The tree for this problem is ternary. The first weighing has three possible outcomes (< = >), as does each subsequent weighing. Therefore, at any level of the tree L, L being the number of weighings that has taken place, there are 3^(L - 1) possible places for solutions. Thus, 2n + 1 <= 3^(L - 1), for all the solutions to be possible. 2n <= (3^(L - 1)) - 1, n <= ((3^(L - 1) - 1)/2. Muffy