5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What is with all the 2015-themed puzzles recently? $\endgroup$ – user1717828 Oct 28 '15 at 14:52
  • 1
    $\begingroup$ I know it was you, Fredo. You broke my heart. You broke my heart! $\endgroup$ – Michael McGriff Oct 28 '15 at 19:05
7
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ One could say that $\sum_{k=1}^0$ is not well defined. In this case I decided to sacrifice accuracy for intuition: assume it is 0. $\endgroup$ – Ara Oct 28 '15 at 17:07
  • 3
    $\begingroup$ There's nothing wrong with that expression. It's a sum of 0 terms, which is 0. $\endgroup$ – f'' Oct 28 '15 at 17:44
  • $\begingroup$ Depending on your definition of the sum notation it could be correct, but I think most people won't agree, wikipedia in English wouldn't for instance. $\endgroup$ – Ara Oct 28 '15 at 19:09
  • $\begingroup$ Note that weights can be used on either side of the scale and hence subtractively, so your inequality with powers of two is incorrect : 1,3,9 is sufficient for measuring any integer up to and including 13, and this continues in powers of 3. $\endgroup$ – IanF1 Oct 29 '15 at 6:50
  • $\begingroup$ @IanF1: countrary to another quite similar question , this one states that 'Any integer weight [...] can be balanced by placing it into the left pan and some subset of the weights into the right pan'. If you allow both sides then you are indeed right, the first inequality becomes false and I have no easy patch that comes to mind, as the weights can now become arbitray large. $\endgroup$ – Ara Oct 29 '15 at 11:50
5
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ This is nice, but it lacks proof that 147 is the smallest possible. $\endgroup$ – klm123 Oct 28 '15 at 9:51
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The binary weights from 1 to 128 number 8 and not 7. (1, 2, 4, 8, 16, 32, 64, 128) Following your solution the last step would be to divide 991 by 6 which amounts to about 165.17. $\endgroup$ – The Dark Truth Oct 28 '15 at 11:24
  • $\begingroup$ fixed @TheDarkTruth $\endgroup$ – Kate Gregory Oct 28 '15 at 11:52
  • $\begingroup$ +1. Since weights are allowed to be placed on both pans, why not use ternary base system (+1, 0, -1). I think the largest weight may get smaller. Does it? $\endgroup$ – Bhaskar Oct 28 '15 at 14:26
  • $\begingroup$ @L16H7 it would get smaller and such an answer was already posted before. However the question clearly states that you can only put the weights on one of the two pans. $\endgroup$ – The Dark Truth Oct 28 '15 at 14:29
  • $\begingroup$ Argh! Sorry I misunderstood it. :) $\endgroup$ – Bhaskar Oct 28 '15 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.