Forty 1lb Weights

[Ian Rumsey]

With the aid of a set of balance scales an Iron Monger was able to weigh goods up to 40lb, in increments of 1lb, by cutting up a uniform iron bar 40 inches long weighing 40lb.
Having an infinitely thin hacksaw blade he cut the bar 39 times into 1 inch lengths and produced forty 1lb weights.
What would be the minimum number of cuts required to obtain the same result of being able to weigh goods of up to 40lb in 1lb increments on his set of balance scales.

[Robert Zaleski]

11 cuts. Make four equidistant lengthwise cuts. Hold these five pieces together and make seven right angle crosscuts at five inches on center.

You can also make seven equidistant lengthwise cuts and four right angle crosscuts at 8 inches on center.

[K.J.Healey]

8 Cuts. 5 times from the end, through the whole bar, like a pizza. Then cutting it into shorter segments 3 times. This yeilds 40 pieces of the bar equal in volume.

[Gokul43201]

The lengths you need are 1, 3, 9, 27 - 3 cuts.

Or you could make 1 cut at say 4" and arraange the bars so you can make the required 2 other cuts in a single cutting action. So, if you're counting the number of 'cutting actions' it could be just 2.

[EFischer]

Gokul, what method did you use to figure out the necessary lengths?

[Gokul43201]

To generate any integer in terms of the sums of certain chosen numbers, the optimal choice of numbers (ie. the smallest set) is 1,2,4,...2^n to make up any number up to 2^(n+1) - 1

To generate any integer in terms of the sums or differences of certain chosen numbers, the smallest set is {1,3,9,...,3^n}.

If you are allowed to place weights on both pans of a weighing scale, you are allowing addition and subtraction. So the second set is optimal.

If you are only allowed to place weights on only one pan, you would have to go with the first set.

[Galileo]

Very clever Gokul!

Can you show that the smallest set necessary to generate any integer by sums and differences is {3^n|n=1,2,3,...}??

[Gokul43201]

I think I can, but it's a little long and not especially elegant. Let me give you the outline...perhaps someone can find a better proof.

First prove that the weights
1, 3,...,3^{n-1} will weigh any number up to \frac {1}{2} (3^n - 1)

This is done easily using the fact that any number up to (3^n - 1) can be represented as \sum_0^{n-1}{a_k 3^k}~, ~~ a_k = 0, 1, 2
(I don't know what this theorem is called but it is the basis of any notational system - binary, decimal, etc.) and \sum_0^{n-1}{3^k} = \frac{1}{2}(3^n - 1) and subtracting one from the other.

It's a little more cumbersome to prove than no other combination will generate so long a sequence...but it can be done by induction.

Clearly, no two weights must be the same if there is to be no wastage (as in the case of 1,3,9,...). Let the weights be

w_1 < w_2 < w_3...< w_n

Clearly, the largest weight that can be generated is

W = w_1 + w_2 + ... + w_n and the next largest will be

W' = w_2 + w_3 + ... + w_n = W - w_1

But since every weight can be measured so should W-1. Then clearly, W' = W- 1.

So, ~w_1 = 1

Proceeding along these lines, it can be shown that w_2 = 3.

Now assuming ~w_m = 3^{m-1} for~~ m=1, 2, 3, ..., k if we can show that w_{k+1} = 3^k we are through.

Consider all the weights and put them into 2 groups such that
W = \sum_1^k {w_m} + \sum_{k+1}^n {w_m}

Leave the second set alone. By transferring weights from the first set to the other pan (or eliminating them), it is possible to generate all weights down to -\sum_1^k {w_m} + \sum_{k+1}^n {w_m} = W - (3^k - 1).
The next lower weight must be 1 less than this and can be made by transferring back all the weights in the 'other' pan and eliminating w_{k+1}.

By subtracting the above equation from the definition of W, you get w_{k+1} = 3^k ,

which is what we wanted to prove.

[BobG]

The lengths you need are 1, 3, 9, 27 - 3 cuts.

Or you could make 1 cut at say 4" and arraange the bars so you can make the required 2 other cuts in a single cutting action. So, if you're counting the number of 'cutting actions' it could be just 2.

Pretty clever. :smile:

It didn't occur to me that I could put the weights on both sets of scales. I wound up with 5 cuts with a 9 inch piece left over.

[NateTG]

I think I can, but it's a little long and not especially elegant. Let me give you the outline...perhaps someone can find a better proof.

The number system associated with this is called balanced ternary.

How about this:

The solution provides all of the desired weights, so it's sufficient to prove that it is an ideal solution.

Each weight can be on the left hand of the scale, the right hand of the scale, or off the scale, so if there are n weights, then there are 3^n possible arrangements. So, for m possible weights to be measured (including 0), there must be at least \log_3(2m+1) different reference weights, but we know that the 'powers of three' method generates \lceil \log_3(2m+1) \rceil weights, which is what we need.

Using the \log_3 it's also relatively easy to see that optimal ranges occur at \frac{3^n-1}{2}, for example 40.

[Gokul43201]

Ahh..very nice,

But how does this prove that there is not another combination that also generates as many different weights (or uses as few) ?

In other words, I was also trying to establish that the 'powers of 3' was the unique optimal solution.

[Rogerio]

Only 2 orthogonal cuts.

The first cut divides the bar in 2 pieces proportional to 1:3

The second cut divides the bar in 2 pieces proportional to 1:9

Then you get 1lb + 9lb from the 10lb piece, and 3lb + 27lb from the 30lb piece.

[Gokul43201]

Only 2 orthogonal cuts.

The first cut divides the bar in 2 pieces proportional to 1:3

The second cut divides the bar in 2 pieces proportional to 1:9

Then you get 1lb + 9lb from the 10lb piece, and 3lb + 27lb from the 30lb piece.

Yes, that's true :smile:

[Integral]

Only 2 orthogonal cuts.

The first cut divides the bar in 2 pieces proportional to 1:3

The second cut divides the bar in 2 pieces proportional to 1:9

Then you get 1lb + 9lb from the 10lb piece, and 3lb + 27lb from the 30lb piece.
Hold on for a moment! how do you do this with only 2 cuts?

cut 1 yields 10 and 30 lb pieces
cut 2 yields 1 and 9 or 27 and 3 depending on which piece you cut.
A third cut is required to cut the remaining piece. This is the same solution as given above.

Or am I missing something?

[Gokul43201]

You're missing the word 'orthogonal'.

Cut 1 is a longitudinal cut that yields 10 and 30 lb bars (each as long but thinner than the original)

Cut 2 is a transverse cut at the 4" mark (along the 40" length) that results in the 10 lb thin bar becoming 1 lb and 9 lb bars. The 30 lb bar gets cut into a 3 lb bar and a 27 lb bar.

Of course, the order is not important.

By 'cut' the poster means 'cutting action' as opposed to 'boundaries created' or whatever.

[Integral]

Ahhh... In my mind orthogonal needs a reference, othogonal to what? Perhaps,The word needed here is lengthwise.

Even in this case each long section needs a cut, so three cuts are still required.

[NateTG]

Ahh..very nice,

But how does this prove that there is not another combination that also generates as many different weights (or uses as few) ?

In other words, I was also trying to establish that the 'powers of 3' was the unique optimal solution.

In some situations, the powers of 3 are not a unique solution. For example, I'm pretty sure that
1,3,3,9,27
and
1,2,3,9,28
can both measure every weight from 0 to 43.

It's relatively easy to show that the 'powers of three' are the smallest set of weights that provide for optimal coverage, so that cases where m=\frac{3^n-1}{2} they are the only solution.

[NateTG]

Only 2 orthogonal cuts.

The first cut divides the bar in 2 pieces proportional to 1:3

The second cut divides the bar in 2 pieces proportional to 1:9

Then you get 1lb + 9lb from the 10lb piece, and 3lb + 27lb from the 30lb piece.

Funny, I thought of that, but I was going to slice off quarters with both cuts instead. ;)

[Rogerio]

Ahhh... In my mind orthogonal needs a reference, othogonal to what? Perhaps,The word needed here is lengthwise.

Even in this case each long section needs a cut, so three cuts are still required.

Just 2 cuts!
You are gonna use the blade just 2 times, without rearranging or moving any pieces.

[Integral]

I guess I have had to much time behind a hacksaw to buy that! :smile:

[Tau_Muon_PlanetEater]

Then you get 1lb + 9lb from the 10lb piece, and 3lb + 27lb from the 30lb piece.


Your proof is wrong. How do i measure a good that is 5 lbs. using on a 1lb 9lb 3lb and 27lb weight. That is just crazy.


This is the only solution:
1 longitudal cut to yield 20lb and 20lb rods.
1 diagonal cut through both rods near their ends to yield 1lb. + 19lb. and 2lb. + 18lb.
1 diagonal cut through both rods to yield 4lb. + 15lb.(19lb.) and 8lb. + 10lb.(18lb.)
That's all folks!

Now you have six pieces of rod weighing 1lb. 2lb. 4lb. 8lb. 10lb. and 15lb. and combined they can add together to form any number between 1-40.

So all you need is 3 cuts.

P.S. Half the so-called 'correct' solutions listed don't even cover all the increments needed (1-40). Sup with that?

[chroot]

Your proof is wrong. How do i measure a good that is 5 lbs. using on a 1lb 9lb 3lb and 27lb weight. That is just crazy.
No, once again, for the third time in so many minutes, you are wrong.

How about putting the 9 lb weight on one side of the scale and the 1 and 3 lb weights on the other? Then only way to make the scales balance is to put exactly 5 lbs on the second side along with the 1 and 3 lbers.

Unless my arithmetic fails me, 1 + 3 + 5 = 9.
P.S. Half the so-called 'correct' solutions listed don't even cover all the increments needed (1-40). Sup with that?
You don't know what you're talking about, that's what's "sup with that."

- Warren

[Tau_Muon_PlanetEater]

sorry i thought you could only put weights on one side of the scale. In that case I am correct. That's sup with that.

[chroot]

sorry i thought you could only put weights on one side of the scale. In that case I am correct. That's sup with that.
Why would you have assumed that?

- Warren

[Tau_Muon_PlanetEater]

If the weights were only allowed on one side, would my answer be correct? Or is there a better one?

[TenaliRaman]

Tau,
I think u are right with ur modified version of the problem.More specifically u have answered the question "number of weights required to form every number between 1 and 40".

The correctness of ur solution can be easily proved (Additional Note : its quite a known method for address translation in computers)

The optimality of the solution tho , i cannot prove. But i am pretty sure it is optimal ...

-- AI

[Gokul43201]

I guess I have had to much time behind a hacksaw to buy that! :smile:

Uh Oh !! That's the problem. You see, Rog uses his shiny new Mobile base, Horizontal Band Saw. :biggrin:

[Gokul43201]

It's not hard to prove that it's optimal...though it seems hard to prove that it is the only optimal solution.

Proof for the former : Surely, it is known that the set 1,2,4, ...,2^(n-1) will weigh any number upto 2^n - 1. (This can be proved using that fact that every number has a binary representation). Next, it is clear that there is no 'waste' - no two different binary representations refer to the same number. Since there is no waste, no equally large set can weigh more weights - there may be other sets that weigh an equal number of weights, but we shall not address that (actually, this part too can be proved - inductively).

So any number up to 31 can be made using 5 weights :1,2,4,8,16. And any number greater than 31, must necessarily require a larger set. So the number of weights required for 40 must be >= 6.

Since Tau's answer uses 6 weights, it must be optimal.

1,2,4,8,9,16 will also work, if you can find a way to get that in 3 cuts (without rearrangement).

[4newton]

The answer is 6 cuts
1-2-4-8-16-8-1

1-2-4-8-16 gives you all numbers up to 31

8-8-16 gives you 32

Numbers 1-2-4 may be added to 32 to produce 33 to 39

Numbers 1- 2 –4-8-16-8-1 equals 40

[NateTG]

The answer is 6 cuts
1-2-4-8-16-8-1

1-2-4-8-16 gives you all numbers up to 31

8-8-16 gives you 32

Numbers 1-2-4 may be added to 32 to produce 33 to 39

Numbers 1- 2 –4-8-16-8-1 equals 40

It should be pretty clear that 1 2 4 8 16 9 work - you don't need to split the last 1 off. You know that you can get 1-31 with 1,2,4,8, and 16 for 32-40, just use 23-31 using subsets of those, and add 9.

[4newton]

you are right. I just thought of that today and was going to change it. thanks for getting that.