Another scale problem
by Tom Temple
22 June 2009
Somebody at work asked about the chicken scratchings I used in the snack room and in response to my solution said something fawning about how neat it was that I could just change my number representation however it suited me.
As Jon would guess, that led to a conversation about balanced tertiary, and the following problem arose.
You have a balance with two pans and an object with integer mass, N, that you would like to determine. You have the following known masses:
let k be an odd, positive integer. You have (_k_ – 1)/2 of each mass of weight kn for n in the non-negative integers. With this set of masses, each integer will have a unique representation.
You would like to determine N in a minimum number of weighings. Any time you add or remove a single mass from the scale counts as a weighing.
For instance let k=3, and I wanted to put 128g (=243-81-27-9+3-1) on the scale when 256g (=243+9+3+1) was on their previously. To do so counts as 6 weighings.
I’m looking for the big-Oh (in terms of N,k) of your strategy. From the above example I think it would be easy to argue that binary search is O(log 2 (N)). Can anyone do better?
