1. PF Insights is off to a great start! Fresh and interesting articles on all things science and math. Here: PF Insights

Forty 1lb Weights

  1. 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.
     
  2. jcsd
  3. 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.
     
    Last edited: Aug 10, 2004
  4. 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.
     
  5. Gokul43201

    Gokul43201 11,141
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  6. Gokul, what method did you use to figure out the necessary lengths?
     
  7. Gokul43201

    Gokul43201 11,141
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  8. Galileo

    Galileo 2,002
    Science Advisor
    Homework Helper

    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,...}??
     
  9. Gokul43201

    Gokul43201 11,141
    Staff Emeritus
    Science Advisor
    Gold Member

    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
    [tex]1, 3,...,3^{n-1}[/tex] will weigh any number up to [tex]\frac {1}{2} (3^n - 1)[/tex]

    This is done easily using the fact that any number up to (3^n - 1) can be represented as [tex]\sum_0^{n-1}{a_k 3^k}~, ~~ a_k = 0, 1, 2 [/tex]
    (I don't know what this theorem is called but it is the basis of any notational system - binary, decimal, etc.) and [tex]\sum_0^{n-1}{3^k} = \frac{1}{2}(3^n - 1)[/tex] 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

    [tex]w_1 < w_2 < w_3...< w_n[/tex]

    Clearly, the largest weight that can be generated is

    [tex]W = w_1 + w_2 + ... + w_n [/tex] and the next largest will be

    [tex]W' = w_2 + w_3 + ... + w_n = W - w_1[/tex]

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

    So, [tex]~w_1 = 1 [/tex]

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

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

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

    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 [tex]-\sum_1^k {w_m} + \sum_{k+1}^n {w_m} = W - (3^k - 1).[/tex]
    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 [tex]w_{k+1}.[/tex]

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

    which is what we wanted to prove.
     
    Last edited: Aug 10, 2004
  10. BobG

    BobG 2,347
    Science Advisor
    Homework Helper

    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.
     
  11. NateTG

    NateTG 2,537
    Science Advisor
    Homework Helper

    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 [tex]n[/tex] weights, then there are [tex]3^n[/tex] possible arrangements. So, for [tex]m[/tex] possible weights to be measured (including 0), there must be at least [tex]\log_3(2m+1)[/tex] different reference weights, but we know that the 'powers of three' method generates [tex]\lceil \log_3(2m+1) \rceil[/tex] weights, which is what we need.

    Using the [tex]\log_3[/tex] it's also relatively easy to see that optimal ranges occur at [tex]\frac{3^n-1}{2}[/tex], for example 40.
     
    Last edited: Aug 11, 2004
  12. Gokul43201

    Gokul43201 11,141
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  13. 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.
     
  14. Gokul43201

    Gokul43201 11,141
    Staff Emeritus
    Science Advisor
    Gold Member

    Yes, that's true :smile:
     
  15. Integral

    Integral 7,346
    Staff Emeritus
    Science Advisor
    Gold Member

    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?
     
  16. Gokul43201

    Gokul43201 11,141
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
    Last edited: Aug 11, 2004
  17. Integral

    Integral 7,346
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  18. NateTG

    NateTG 2,537
    Science Advisor
    Homework Helper

    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 [tex]m=\frac{3^n-1}{2}[/tex] they are the only solution.
     
  19. NateTG

    NateTG 2,537
    Science Advisor
    Homework Helper

    Funny, I thought of that, but I was going to slice off quarters with both cuts instead. ;)
     
  20. Just 2 cuts!
    You are gonna use the blade just 2 times, without rearranging or moving any pieces.
     
  21. Integral

    Integral 7,346
    Staff Emeritus
    Science Advisor
    Gold Member

    I guess I have had to much time behind a hacksaw to buy that! :smile:
     
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?