A balance and twenty weights

Question

Fredo owns a nice balance with two pans. He now wants to design a system of 20 integer weights $w_1,w_2,\ldots,w_{20}$ with the following properties:

• $1\le w_1\le w_2\le w_3\le\cdots\le w_{20}$
• Any integer weight $U$ from the range $1\le U\le2015$ can be balanced by placing it into the left pan and some subset of the weights into the right pan.

Question: What is the smallest possible value that weight $w_{20}$ can take under these conditions?

Answer 1

The weight $w_i -1$ for $i\in [1, 20]$ can only be weighted using the weights $w_1$ to $w_{i-1}$: indeed all other weights are more heavy than $w_i -1$ (recall that the weights are ordered by increasing weights).

Therefore when you add all the weights $w_1$ to $w_{i-1}$ they must at least weight $w_i -1$. This gives the relation :

$$w_i -1 \leq \sum_{k=1}^{i-1} w_k$$

This gives in particular that $w_1 -1 \leq 0$ and because we imposed the property $1 \leq w_1$ we have $w_1 =1$.

It also leads to $w_2 -1 \leq w_1$, i.e. $w_2 \leq 2$, and $w_3 -1 \leq w_1 + w_2$ i.e. $w_3 \leq 4$

More generally it leads to:

$$w_i \leq 2^{i-1}$$

Let's now look at $\sum_{i=1}^{20}w_i \geq 2015$ (this comes from the fact that you can weight 2015).

We can separate the 12 last terms of the sum as follows:

$$\sum_{i=9}^{20}w_i \geq 2015 - \sum_{i=1}^{8}w_i$$

Hence $\sum_{i=9}^{20}w_i \geq 2015 - \sum_{i=1}^{8}2^{i-1}$ and $\sum_{i=9}^{20}w_i \geq 1760$

We conclude that $max_{i=9}^{20} w_i \geq \lceil{1760/12}\rceil$

And in particular that:

$$max_{i=1}^{20} w_i \geq 147$$

There should be a weight of weight at least 147.

---

On the other hand there exists a set of weights where all weights are at most 147 satisfying the conditions, for instance : {1, 2, 4, 8, 16, 32, 63, 125, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147}

The proof of this can take the other answers to this post as indication.

---

So this proves that 147 is the smallest value $w_{20}$ can take under the mentioned conditions.

Answer 2

I have a solution with the largest weight being:

147

First i tried using binary weigths ($2^{N-1}$) but this solution would be giving me the possibility of balancing way larger weights than what is needed.

So i tried to think about where to stop using binary weigths so that the higher weights can be balanced by using equal weights of smaller size than the would be next binary weigth.

My solution uses the binary weigths 1, 2, 4, 8, 16, 32, 64, 128.

With those i can balance all weights between 1 and 255.

Subtracting all binary weights from 2015 leaves us with 1760.

Now we only need to divide 1760 by the amount of our left over weigths to determine the smallest amount they should have:

$w=\frac{1760}{12}=146\frac{2}{3}$

So our smallest possible biggest weight is 147.

Answer 3

If you used binary weights, you wouldn't need 20. You could use 1,2,4, ... 1024 to weigh anything up to 2096, which is more than 2015, with just 11 weights. But you've been told to use 20 weights.

So you could take the last one, 1024, and replace it with two 512s. Now you're using 12 weights and the largest is 512. But you still have 8 more weights available. If you try to split 1024 into three, you're getting down below 512, the binary weight before the 1024. What's more, you're still trying to reach 2096 when you don't need to. So set aside the 1024 and the 512, and you have 1,2,4, ... 256 for 9 weights, and can use 11 weights for the remaining (2015-511) 1504 g. That's an average of 137 each, which is below the 256, so set aside 256 also. Now you have 1,2, 4 ... 128 for 8 weights, and 12 weights for (2015-255) 1760, averaging 147.

In order to make any number up to 512, you will need a "256" - which will be made up of these extra weights - use a pair of 128s, and you have 10 weights accounted for.

In order to make any number up to 1024, you will need a "512". Use 4 128s and you have 14 weights accounted for.

If you wanted to make numbers up to 2096 the next step would be to create a "1024", but you don't. The largest number you need is 2015 which is 991 more than 1024. So if you can make 991 out of 6 weights, you can make any number between 991 and 2015. It averages 165. So you could use 5 165s and a 164.

Can this be improved? What if I had 12 147s after the 1..128 and didn't bother with the "256" and the "512"? They pull the average down because they're only 128. I can make any number up to 255 with the 1..128, so I can make 147, then throw in a 147 and carry on adding 1, 2, 3, 4, to that until I hit 294, then use 2 of the 147s and so on. Now 12x147 is 1764 not 1760, so I need a mix of 157 and 156s to hit 1887.

Using that approach, do I even need that first 128? Well, how else will I make 129? or 130? So I do and the largest weight will have to be 147g.