hard | discrete |

We have a beam balance (with two pans to compare weights) and a positive integer N. How do we select fewest number of pebbles to weigh all possible integers from 1 to N

We will require the set (1,3,9.....3^x ) where x is lowest integer with 3^x > N. This is true because each number now has exactly one ternary representation. Any 2 * 3^i can always be represented as 3^(i+1) - 3^i. So, there is a unique way of representing a number in the form of sigma s_i * 3^i where s_i belongs to {0, 1, -1}. So, this is optimal Verify that this can be used to weigh all integers from 1 to N Number of pebbles = log_{base:3} (2N+1)

If each weight w_i has k copies, then 2k+1 combinations can be weighed using them (from -k * w_i to 0 to k * w_i). So, if we choose w_i = (2k+1)^{i-1}, i=1...p, then everything till k*((2k+1)^p - 1)/((2k+1)-1) = ((2k+1)^p-1)/2 can be weighted, thus requiring p=log_{2k+1} (2N+1) number of distinct weights.