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.
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.
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.
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.
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.
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,...}??
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.
Pretty clever. 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.
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.
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.
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?
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.
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.
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.