Suppose you want to create a set of weights so that any object with an integer weight from 1 to 40 pounds can be balanced on a two-sided scale by placing a certain combination of these weights onto that scale.
What is the fewest number of weights you need, and what are their weights?
It turns out that you need four weights, measuring 1, 3, 9, and 27 pounds.
The trick here is that you can put weights on both sides of the scale. If you have an object of 2 pounds on the left side, you can place the 3-lb. weight on the right side and the 1-lb. weight on the left side for the scale to balance.
Similarly, if the object weighs 5 pounds, you put the 9-lb. weight on the right side and the 3-lb. and 1-lb. on the left side.
If you have a set of weights that can balance any weight from $1$ to $N$ pounds, then they can also balance any weight from $-1$ to $-N$ pounds just by switching the sides of the scale that you place them on. So the next weight you'd want to add would weigh $2N + 1$ pounds, and then you can balance any weight from $1$ to $3N + 1$ pounds on the scale.
So, starting with the 1-lb. weight, which can balance any weight from $1$ to $1$ pounds, we get $2(1) + 1 = 3$ pounds for the next weight, and they can balance anything up to $1 + 3 = 4$ pounds.
Then, for those two weights, we get $2(4) + 1 = 9$, and they can balance up to $1 + 3 + 9 = 13$ pounds.
And finally, for all three of those weights, we get $2(13) + 1 = 27$, and they can balance up to $1 + 3 + 9 + 27 = 40$ pounds, as required.
In general, to measure any weight up to $n$ pounds, you will need at least $\lceil\log_3(2n)\rceil$ weights due to the above formula.
The minimum is still four weights for up to 40 pounds, but you can do it a bit more efficiently than the previous answer. Assuming you can also tell if a set of weights is heavier/lighter than another set and not just if they are equal, we can also find out the weight of an object through comparisons with other weights. For example, with a single weight weighing $2$ pounds, we can find weights within the range of $1$ to $3$. Using $x$ as our mystery weight, we can find all values as:
Using two weights, the new one being size $6$, we can find the values of mystery weights up to $9$ pounds.
Utilising this, the maximum values for any integer weight up to $n$ pounds is only $\lceil\log_3(n)\rceil$ rather than $\lceil\log_3(2n)\rceil$. The four weights we need for $n=40$ are 2, 6, 18 and 54. This will also allow you to find weights up to a $(2 + 6 + 18 + 54) + 1 = 81$ pounds.
Each of the 4 weights has 3 possibilities. It can be in the left pan, right pan or off the scale. That gives 3 to the fourth = 81 possibilities. Ignoring the case where all the weights are off the scale, the same weight is represented twice, once with the left side tipping and once with the right side tipping, giving 80/2 = 40 possibilities. We need at least 4 weights. We need to show that 4 weights suffices.
Let us designate the left pan as negative and the right pan as positive. Each weight placement w on the scale is multiplied by a coefficient of -1, 0 or 1, depending on whether the weight is on the left pan, off the scale, or in the right pan. We know that if the coefficients were instead 0, 1 and 2, we could represent the number in base 3 by assigning powers of 3 to the weights - 1, 3, 9 , and 27. The highest base 3 number = 2222 = 80 base ten.
Suppose we take a base 3 representation of the weight and subtract 1 from each of the coefficients. That would give a weight with coefficients -1, 0 and 1. Of course, subtracting 1 from each coefficient is equivalent to subtracting 1111 base 3 = 40 base 10. We adopt the following strategy. For any weight w from 0 to 40, add 40, then convert to base 3, and finally subtract 40 by subtracting 1 from each base 3 coefficient. Since w is at most 40 = 1111 base 3, w + 40 is between 1111 and 2222 base 3, giving the base 3 numbers with 4 columns from 40 to 80. Subtracting one from each column gives the four column numbers for 0 to 40 using -1, 0, and 1 as coefficients.
Here is an example. Let w = 17. w + 40 = 57 = 2010 base 3. Subtracting 1 from each column gives 1 -1 0 -1. We get 17 by placing 9 and 1 in the left pan and 27 in the right pan.
Once we have determined that the weights must be 1, 3, 9 and 27 grams, an obvious question to ask is how to use these weights to weigh an object.
One method, which is my candidate for most efficient, is to proceed as follows. Place the object to be weighed in the right pan. Now do a binary search to find the heaviest single weight that is lighter than the object. Suppose, for example, that this is the 9 gram weight.
We now know that either the 9 gram or 27 gram weight will be the heaviest weight needed to measure the weight of the object. To choose between them, place all the weights less than or equal to 9 grams on the left pan. If the scale balances then the object weighs 9+3+1=13 grams and we are done. Otherwise, if the object weighs less than 13 grams, then the 9 gram weight will be needed to find the object's weight and the 27 gram weight will not be used. On the other hand, if the object weighs more than 13 grams, then the 27 gram weight will be needed.
Place whichever weight is needed on the left pan. The problem now reduces to finding the combination of weights less than the one selected that will be needed to cover the net weight that is on the scale. We can again look for the heaviest single weight that will be needed. Note that if the 9 gram weight was chosen then we will be placing weights on the left pan and if the 27 gram weight was chosen, we will be placing weights on the right pan. For future weighings we may be switching back and forth between placing weights on the left or right pan.
As a complement to the other answers, let me elaborate the idea of using base-3 representation in details. Consider any positive integer $m$ that can be represented in base 3 with $n$ digits as follows: $$ m=\sum_{i=0}^{n-1}a_i\cdot 3^{i}, \quad\quad a_i\in\{0,1,2\} $$ Our goal is to represent it using $a_i\in\{-1,0,1\}$. This can be done as follows $$ m^*=m-\sum _{i=0}^{n-1}3^i=\sum_{i=0}^{n-1}(a_i-1)\cdot 3^{i}=\sum_{i=0}^{n-1}c_i\cdot 3^{i}, \quad\quad c_i\in\{-1,0,1\} $$ Note $$ \sum _{i=0}^{n-1}3^i=\frac{1-3^n}{1-3}=\frac{3^n-1}{2} $$ Since $$ m\in\{k\in\mathbb{Z}:k\in[0,3^n-1]\} $$ we have $$ m^*\in\left\{k\in\mathbb{Z}:k\in\left[-\frac{3^n-1}{2},\frac{3^n-1}{2}\right]\right\} $$ In other words, any integer between $-\frac{3^n-1}{2}$ and $\frac{3^n-1}{2}$ can be represented in base 3 with $n$ digits where the digits can be $-1$, $0$, or $1$.
Then, given $m^*$, we can find the smallest $n$ such that it can be represented as above. If $m^*>0$, then, we need $$ m^*\leq\frac{3^n-1}{2}\Rightarrow n\geq\log_3(2m^*+1) $$ So the smallest $n$ is $\lceil \log_3(2m^*+1) \rceil$.
Back to the problem, to "weigh" any integer, we can first identify the smallest $n$ such that the integer is in the range. Since $m^*=40$, we have $n=\lceil \log_3(2\times 40+1) \rceil=4$. To obtain the combination of weights and their positions, we can represent the target integer using base 3 with $\{-1,0,1\}$. Then, for each digit (weight), if it is $-1$, then put it on the same side as the target integer; if it is 0, then do not use it; if it is 1, then put it on the other side of the scale.
Extension. The above framework works only if each weight can be used only once (no extra ones). Suppose that the number of each weight is 2. Then, the question becomes how to represent an integer in base 5 where each digit can be $-2$, $-1$, $0$, $1$, and $2$. In this case, to map $\{0,1,2,3,4\}$ to $\{-2,-1,0,1,2\}$, we subtract $\sum_{i=0}^{n-1}2\cdot 5^{i}$. Then, the range for $m^*$ becomes $$ -\frac{5^n-1}{2}\leq m^* \leq\frac{5^n-1}{2} $$ The same idea can be generalized in other similar problems.
