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.

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: