I have a weight problem.

What is the least number of weights that can be used on a set of scales to weigh any whole number of kilograms from 1 to 40?

I can do it with 4. I won't say which 4 yet...

Originally posted by mtthw
I can do it with 4. I won't say which 4 yet...

Spot on! Yeah but see if a few others can work it out - cheers.

I wrote a prog to work it out first, then I figured out why it works.

The bias of the scale is simply the weight on left minus weight on right. I must be able to bias the scale from 1-40 kg, per stipulation.

To get the most use out of each weight, we use it in each of its three possible positions: right, left, or off-scale.

1 kg is the natural starting point. We need to be able to fine-tune all the way to 40. Using it by itself gives biases of -1, 0 and 1.

We can skip -1 and 0 because we're only concerned about positive weight. After using 1 in each of three positions, we put it back on the right and must add a 2nd weight to count any higher. The obvious next choice is 3kg on left - and move the 1kg weight as before to obtain biases of 2, 3 and 4.

The combinations of the first two weights are exhausted. Weight 3 comes into play. Our next bias required is 5. This means we need a 9kg weight on left and 3 and 1 go back to the right.

Using the same 'counting' method [1 moves through all positions, then 3 moves, then 1 moves through all positions, then 3 moves again, etc.] we get all the way up to 9 + 3 + 1 = 13kg. Weight 4 and a bias of 14 is needed. 27 - 13 = 14, so the fourth weight is 27kg. This gets us all the way up to 27+9+3+1 = 40kg, which solves (and reveals why the problem's creator chose 40kg as the upper limit).

Originally posted by SwissGambit
I wrote a prog to work it out first, then I figured out why it works.

The bias of the scale is simply the weight on left minus weight on right. I must be able to bias the scale from 1-40 kg, per stipulation.

To get the most use out of each weight, we use it in each of its three possible positions: right, left, or off-scale.

1 kg is the natural s ...[text shortened]... = 40kg, which solves (and reveals why the problem's creator chose 40kg as the upper limit).

You don't happen to have a copy of "Fermat's Last Theorem" do you?

Originally posted by demonseed
You don't happen to have a copy of "Fermat's Last Theorem" do you?

Nope. I'm not much of a mathematician.

I was going to say, but in thinking about it, 4 is sufficient.

I won't say which weights, but I will give a hint. There are 2 sides to the scale.

EDIT: Oops, didn't see that SwissGambit already answered it.

The technique:

Suppose we wish to guess the weight of the object to weigh, then place it on one side of the scale (or that we know its weight and want to verify it)

For this, we'll keep track of the weight difference in kg.

If the weight of the object is at least 14 kg, then we'll place the 27kg weight ooppostie the object being weighed, and subtract it from the weight of the object.

Whether we placed the 27kg weight or not, our number is now between -13 and +13 inclusive.

If our number is within 4kg of zero, we set the 9kg weight aside, otherwise we add it to the lighter side, and update our difference.

Our number is now anywhere from -4 to +4 inclusive.

If it is within 1kg of even, we set aside the 3kg weight, otherwise we place it on the lighter side.

Our number is now within 1kg of the (presumed) object weight, and placing the 1 kg weight should be easy.

My approach was this.

OK, we're probably going to need a 1kg weight. Start with that.

We need to be able to weigh 2kg. We could use a 2kg weight, but that's inefficient. A 3kg weight will do it, being able to use the difference.

That gets us up to 4kg. To weigh 5kg, the largest new weight that will give us that capability is 9kg (when you subtract all the ones we've already got).

That takes us up to 13kg. The same argument means we now take a 27kg weight. A couple of minutes verification confirms that covers everything up to 40kg.

It's pretty obvious what the pattern is if you take it further...

some years ago i did some thinking on that find-the-odd-ball-in-3-measurings-problem. hope you know that one. well, outcome of that was, that in 3 measuring you can find an odd ball out of 3^0 + 3^1 + 3^2 = 13 balls. in 4 measuring you can find one odd ball in a total of 13 + 3^3 = 40 balls.

now, back to the point. for some reason that is unknown to me, those numbers work here too.
3^0 = 1 kg
3^1 = 3 kg
3^2 = 9 kg
3^3 = 27 kg

with those 4 numbers/weights you can express all numbers up to 40 using only + and -

now big question: how many weights do you need to weigh any number between 1 and 364 kg? 😉

edit: technically, all you have to do is start with 1 kg. then add up all weights you have, multiply by 2 and add 1. thats the number for the next weight. makes sense, doesnt it? 🙂

Originally posted by crazyblue
some years ago i did some thinking on that find-the-odd-ball-in-3-measurings-problem. hope you know that one. well, outcome of that was, that in 3 measuring you can find an odd ball out of 3^0 + 3^1 + 3^2 = 13 balls.

What method do you use? I believed the maximum to be 12, unless you know beforehand if the odd weight is heavier or lighter. With 13 balls there is a chance you don't find out if the odd ball is heavier or lighter.

My solution to the problem of the post is similar to the one SwissGambit gave. I just didn't use a computer.

You start with 1 kg.

Possible weights this can balance on the LEFT scale:

1, 0, -1

The next weight should be able to make a measurement of 2 kg. The maximum we can use for that is a weight of 3 kg.

Possibilities:

1+3 0+3 -1+3 1 0 -1 1-3 0-3 -1-3
gives
4 3 2 1 0 -1 -2 -3 -4

Next we need something to make 5. The maximum we can use is 9.

4+9 3+9 2+9 1+9 0+9 -1+9 ...and so on... 0-9 -1-9 -2-9 -3-9 -4-9
gives
13 to -13

Finally we need to make 14, so the maximum we can add is 27 giving the possible weighings of 40 to -40