Frugal Selection of Weights


I got this problem from Rustan Leino, who got it or a slight variation of it from Matthew Parkinson.

I solved it and wrote up my solution.


You are given a balance (that is, a weighing machine with two trays) and a positive integer $N.$ You are then to request a number of weights. You pick which denominations of weights you want and how many of each you want. After you receive the weights you requested, you are given a thing whose weight is an integer between $1$ and $N,$ inclusive. Using the balance and the weights you requested, you must now determine the exact weight of the thing.

As a function of $N,$ how few weights can you get by requesting?

Solution     Reveal