[CrackMonkey] [schoen@loyalty.org: Pill-weighing]
Seth David Schoen
schoen at loyalty.org
Sun Feb 13 20:04:05 PST 2000
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
More information about the Crackmonkey
mailing list