
#1
Aug1004, 08:35 AM

P: 31

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
Aug1004, 10:59 AM

P: 74

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. 



#3
Aug1004, 11:35 AM

P: 640

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.




#4
Aug1004, 01:03 PM

Emeritus
Sci Advisor
PF Gold
P: 11,154

Forty 1lb Weights
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. 



#5
Aug1004, 01:42 PM

P: 4

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




#6
Aug1004, 02:06 PM

Emeritus
Sci Advisor
PF Gold
P: 11,154

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. 



#7
Aug1004, 02:33 PM

Sci Advisor
HW Helper
P: 2,004

Very clever Gokul!
Can you show that the smallest set necessary to generate any integer by sums and differences is {3^nn=1,2,3,...}?? 



#8
Aug1004, 05:32 PM

Emeritus
Sci Advisor
PF Gold
P: 11,154

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^{n1}[/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^{n1}{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^{n1}{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 W1. 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^{m1} 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. 



#9
Aug1004, 10:24 PM

Sci Advisor
HW Helper
P: 2,275

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. 



#10
Aug1104, 11:05 AM

Sci Advisor
HW Helper
P: 2,538

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^n1}{2}[/tex], for example 40. 



#11
Aug1104, 11:34 AM

Emeritus
Sci Advisor
PF Gold
P: 11,154

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. 



#12
Aug1104, 02:52 PM

P: 403

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
Aug1104, 05:42 PM

Mentor
P: 7,290

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? 



#15
Aug1104, 08:29 PM

Emeritus
Sci Advisor
PF Gold
P: 11,154

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. 



#16
Aug1204, 04:08 PM

Mentor
P: 7,290

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. 



#17
Aug1204, 06:48 PM

Sci Advisor
HW Helper
P: 2,538

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^n1}{2}[/tex] they are the only solution. 



#18
Aug1204, 06:50 PM

Sci Advisor
HW Helper
P: 2,538




Register to reply 
Related Discussions  
Wing weights  Mechanical Engineering  5  
Women: What a difference forty years can make  Social Sciences  4  
put these weights in order from smallest to largest  General Math  4 