[CrackMonkey] [schoen@loyalty.org: Pill-weighing]

[Seth David Schoen]

Mr. Bad writes:

> >>>>> "SDS" == Seth David Schoen <schoen at loyalty.org> writes:
> 
>     SDS> Right.  Why are you doing this in base 10?  Isn't that a
>     SDS> little wasteful?
> 
> Well, the digits you get with the number 101 don't work out so nicely
> in any other base, do they? Although I guess you could do it in base
> 2, and shift each set by 7 bits (64 < 100 < 128).
> 
> So you add 2 ^ ((X-1) * 7) pills to the coffer each time. 1, 128, 2 ^
> 14, dot dot dot, and look for the groups of 6 where the bit pattern
> isn't, uh, lessee, 110101.
> 
> However, that takes up MORE pills than my second answer (where you
> just look at the disturbance in the digits). And you couldn't do it
> the same way, because with bits, it's not so easy to see an addition. 
> 
> I think you could figure a base smaller than 10 that would let you do
> overlaps and still get information out of them, but my brain hurts
> from thinking so much today.

As far as I know, base 2 is minimal in all cases.

Let M be the overall mass on the scale, using the plain 2^x scheme, and
then take

M-100(2^n-1)

in its binary representation.

Cool properties of place value:

(1) adding any number of distinct powers of b less than n will _always_
give a sum less than b^n, because

(2) adding one to (b-1)b^n + (b-1)b^(n-1) + (b-1)b^(n-2) + ... + (b-1)b^0
always gives b^(n+1).  (You can use that to prove a nice theorem about
exactly when digital root tests for divisibility are guaranteed to work,
and I keep meaning to put up a web page about that when I write it up
nicely.)

So even stronger than (1), although mostly useless, is this: adding
at most (b-1) copies of each distinct power of b less than n will
always give a sum less than b^n.  (This is the "all six-figure salaries
are less than a million" theorem.)

Now I can become a pharmacist, right?

-- 
Seth David Schoen <schoen at loyalty.org>  | And do not say, I will study when I
Temp.  http://www.loyalty.org/~schoen/  | have leisure; for perhaps you will
down:  http://www.loyalty.org/   (CAF)  | not have leisure.  -- Pirke Avot 2:5