lotus

previous page: 360 logic/weighing/optimal.weights.p
  
page up: Puzzles FAQ
  
next page: 362 logic/zoo.p

361 logic/weighing/weighings.p




Description

This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

361 logic/weighing/weighings.p


Some of the supervisors of Scandalvania's n mints are producing bogus coins.
It would be easy to determine which mints are producing bogus coins but,
alas, the only scale in the known world is located in Nastyville,
which isn't on very friendly terms with Scandalville. In fact, Nastyville's
king will only let you use the scale twice. Your job? You must determine
which of the n mints are producing the bogus coins using only two weighings
and the minimum number of coins (your king is rather parsimonious, to put it
nicely). This is a true scale, i.e. it will tell you the weight of whatever
you put on it. Good coins are known to have a weight of 1 ounce and it is
also known that all the bogus mints (if any) produce coins that are
light or heavy by the same amount.

Some examples: if n=1 then we only need 1 coin, if n=2 then clearly 2
coins suffice, one from each mint.

What are the solutions for n=3,4,5? What can be said for general n?

logic/weighing/weighings.s

Oh gracious and wise king, I have solved this problem by first
simplifying and then expanding. That is, consider the problem of
being allowed only a single weighing. Stop reading right now if you
want to think about it further.

There are three possible outcomes for each mint (light, OK, heavy)
which may be represented as (-1, 0, +1). Now, let each mint represent
one place in base 3. Thus, the first mint is the ones place, the
second the threes place, the third is the nines place and so on. The
number of coins from each mint must equal the place. That is, we'll
have 1 coin from mint 1, 3 from mint 2, 9 from mint 3, and, in
general, 3^(n-1) from mint n.

By weighing all coins at once, we will get a value between 1 + 3 + 9 +
... and -1 + -3 + -9 + ... In fact, we notice that that value will
be unique for any mint outcomes. Thus, for the one weighing problem,
we need

sum for i=1 to n (3^(i-1))

which evaluates to (3^n - 1)/2

I'm fairly satisfied that this is a minimum for a single weighing.
What does a second weighing give us? Well, we can divide the coins
into two groups and use the same method. That is, if we have 5 mints,
one weighing will be:

1 coin from mint 1 + 3 coins from mint 2 + 9 coins from mint 3

while the other weighing will be:

1 coin from mint 4 + 3 coins from mint 5

It's pretty plain that this gives us a total coinage of:

   3^(n/2) - 1 for even n and, after some arithmetic agitation:
   2 * 3^((n-1)/2) - 1 for odd n

I think the flaw in this solution is that we don't know ahead of time
the amount by which the coins are off weight. So if you weigh 1 coin
from mint 1 together with 3 coins from mint 2 and the result is heavy
by 3x units, you still don't know whether the bogus coins are from
mint 3 (heavy by x units) or from mint 1 (heavy by 3x units). Note
that we're not given the error amount, only the fact that is is equal
for all bogus coins.

Here is my partial solution:

After considering the above, it would seem that on each of the two
weighings we must include coins from all of the mints (except for the
special cases of small n). So let ai (a sub i) be the number of coins
from mint i on weighing 1 and bi be the number of coins from mint i on
weighing 2. Let the error in the bogus coins have a value x, and let
ci be a the counterfeit function: ci is 0 if mint i is good, 1
otherwise.

Then
	Sum   ai ci x = delta1		error on weighing 1
	Sum   bi ci x = delta2		error on weighing 2

Now the ratio of delta1 to delta2 will be rational regardless of the
value of x, since x will factor out; let's call this ratio p over q (p
and q relatively prime). We would like to choose { ai } and { bi }
such that for any set of mints J, which will be a subset of { 1 , 2 ,
... , n }, that

Sum aj ( = Sum ai ci ) is relatively prime to Sum bj.

If this is true then we can determine the error x; it will simply be
delta1/p, which is equal to delta2/q.

If the { ai } have been carefully chosen, we should be able to figure
out the bogus mints from one of the weighings, provided that
all subsets ( { { aj } over all J } ) have unique sums.
This was the strategy proposed above, where is was suggested
that ai = 3 ** (i-1) ; note that you can use base 2 instead
of base 3 since all the errors have the same sign.

Well, for the time being I'm stumped.

This agrees with the analysis I've been fighting with. I actually
came up with a pair of functions that "almost" works. So that the
rest of you can save some time (in case you think the way I did):
Weighing 1: 1 coin from each mint
Weighing 2: 2^(k-1) coins from mint k, for 1...k...n
(total 2^n - 1 coins)

Consider the n mints to be one-bit-each -- bit set -> mint makes bogus
coins. Then we can just state that we're trying to discover "K",
where K is a number whose bit pattern _just_ describes the bogosity of
each mint. OK - now, assuming we know 'x', and we only consider the
*difference* of the weighing from what it should be, for weighing 1,
the devaiation is just the Hamming weight of K -- that is the number
of 1-bits in it -- that is, the number of bogosifying mints. For
weighing 2, the deviation is just K! When the nth bit of K is set,
then that mint contributes just 2^n to the deviation, and so the total
deviation will just be K.

So that set me in search of a lemma: given H(x) is the hamming weight
of x, is f(x) = x / H(x) a 1-1 map integers into rationals? That is,
if x/H(x) = y/H(y) can we conclude that x = y?

The answer (weep) is NO. The lowest pair I could find are 402/603
(both give the ratio 100.5). Boy it sure looked like a good
conjecture for a while! Sigh.

There are two parts to the problem. First let us try to come up with a
solution to finding the answer in 2 weighings - then worry about using the
min. number of coins.
Solutions are for GENERAL n.

Let N = set of all mints, 1 to n. Card(N) = n.
Let P = set of all bogus mints. Let Card(P) = p.

Weighing I: Weigh n coins, 1 from each mint.

Since each "good" coins weighs one ounce, let delta1 be the error in weighing.
Since all bogus coins are identical, let delta1 be abs(error).
If x is the weight by which one bogus coin differs from a good coin,
delta1 = p * x.

Weighing II: The coins to be weighed are composed thusly.

Let a1 be the number of coins from mint 1, a2 # from mint2 .. and an from
mint n. All ai's are distinct integers.

Let A = Set of all ai's.

Let delta2 = (abs.) error in weighing 2 = x * k
where k is the number of coins that are bogus in weighing two.
Or more formally
k = sigma(ai)
(over all i in P)

Assuming p is not zero (from Weighing I - in that case go back and get beheaded
for giving the king BAAAAAD advice),
Let ratio = delta1/delta2 = p/k.
Let IR = delta2/delta1 = k/p = inverse-ratio (for later proof).

Let S(i) be the bag of all numbers generated by summing i distinct elements
from A. Clearly there will be nCi (that n comb. i) elements in S(i).

[A bag is a set that can have the same element occur more than once.]

So S(1) = A
and S(n) will have one element that is the sum of all the elements of A.

Let R(i) = {x : For-all y in S(i), x = i/y} expressed as p/q (no common
factors).
(R is a bag too).

Let R-A = Bag-Union(R(i) for 1>= i >=n). (can include same element twice)

Choose A, such that all elements of R-A are DISTINCT, i.e. Bag(R-A) = Set(R-A).

Let the sequence a1, a2, .. an, be an L-sequence if the above property is
true. Or more simply, A is in L.

**********************************************************************
CONJECTURE: The bogus mint problem is solved in two weighings if A is in L.

Sketchy proof: R(1) = all possible ratios (= delta1/delta2) when p=1.
R(i) = all possible ratio's when p=i.

Since all possible combinations of bogus mints are reflected in R, just match
the actual ratio with the generated table for n.

************************************************************************
A brief example. Say n=3. Skip to next line if you want.
Let A=(2,3,7).

p=1 possible ratios = 1/2 1/3 1/7
p=2 possible ratios = 2/5 2/9 1/5(2/10)
p=3 possible ratios = 1/4(3/12) (lots of blood in Scandalvania).

As all outcomes are distinct, and the actual ratio MUST be one of these,
match it to the answer, and start sharpening the axe.

Note that the minimum for n=3 is A=(0,1,3)
possible ratios are
p=1 infinity (delta2=0),1,1/3
p=2 2/1,2/3,1/2
p=3 3/4

************************************************************************

All those with the determination to get this far are saying OK, OK how do we
get A.

I propose a solution that will generate A, to give you the answer in two
weighings, but will not give you the optimal number of coins.

Let a1=0
 
For i>=2 >=n
 
ai = i*(a1 + a2 + ... + ai-1) + 1
 
*****************************************
*		i-1			*
*	ai = i* [Sigma(aj)] + 1 	*   ****Generator function G*****
*		j=1			*
*****************************************

If A is L, all RATIO's are unique. Also all inverse-ratio's (1/ratio) are
unique. I will prove that all inverse-ratio's (or IR's) are unique.

Let A(k), be the series generated by the first k elements from eqn. G.(above)

************************************************************************

PROOF BY INDUCTION.

A(1) = {0} is in L.
A(2) = {0,1} is in L.

ASSUME A(k) = {0,1, ..., ak} is in L.

T.P.T. A(k+1) = {0,1, ..., ak, D) is in L where D is generated from G.

We know that all IR's(inverse ratio's) from A(k) are distinct.

Let K = set of all IR's of A(k).

Since A(k+1) contains A(k), all IR's of A(k) will also be IR's of A(K+1).

So for all P, such that (k+1) is not in P, we get a distinct IR.

So consider cases when (k+1) is in P.

p=1 (i.e. (k+1) = only bogus mint), IR = D

______________________________________________________________________
CONJECTURE: Highest IR for A(k) = max(K) = ak

Proof: 	Since max[A(k)] = ak,
		for p'= 1, max IR = ak/1 = ak
		for p'= 2, max IR (max sum of 2 ai's)/2
			   = (ak + ak-1)/2 < ak (as ak>ak-1).
		for p'= i max IR sum of largest i elements of A(k)
			          --------------------------------
						i
				< i * ak/i = ak.
	So max. IR for A(k) is ak.
______________________________________________________________________

D > ak
So for p=1 IR is distinct.

Let Xim be the IR formed by choosing i elements from A(k+1).
Note: We are choosing D and (i-1) elements from A(k).
m is just an index to denote each distinct combination of
(i-1) elemnts of A(i).

______________________________________________________________________
CONJECTURE : For p=j, all new IR's Xjm are limited to the range
D/(j-1) > Xjm > D/j.

Proof:
	Xjm = (D + {j-1 elements of A(k)})/j
 
	Clearly Xjm > D/j.
 
	To show: max[Xjm] < D/(j-1)
 
	Note: a1 + a2 .. + ak < D/(k+1)
 
       max[Xjm] = (D + ak + ak-1 +  ... + a(k-j+1))/j
		< (D + D/(k+1))/j
		= D (k+2)/(k+1)j
		= [D/(j-1)] * alpha.
 
	alpha = (j-1)/(j)  *  (k+2)/(k+1)
 
		Since j <= k, (j-1)/j <= (k-1)/k < (k+1)/(k+2)
 
	IMPLIES alpha < 1.

Conjecture proved.

______________________________________________________________________
CONJECTURE : For a given p, all newly generated IR's are distinct.

Proof by contradiction:

Assume this is not so.

Implies
	(D + (p-1) elements of A(k))/p 
	= (D + some other (p-1) elements of A(k))/p 

Implies SUM[(p-1) elements of A(k)] = SUM[ some other (p-1) elements of A(k)]

Implies SUM[(p-1) elements of A(k)]/(p-1) 
		= SUM[some other (p-1) elements]/(p-1)

Implies A(k) is NOT in L.

Contra.

Hence conjecture.
______________________________________________________________________

CONJECTURE: A(k+1) is in L.

Since all newly generated IR's are distinct from each other, and all newly generated IR's are greater than previous IR's, A(k+1) is in L.

 

Continue to:













TOP
previous page: 360 logic/weighing/optimal.weights.p
  
page up: Puzzles FAQ
  
next page: 362 logic/zoo.p