A silver prospector is unable to pay his March rent in advance. He owned a bar of pure silver, 31 inches long, so he made the following arrangement with his landlady. He would cut the bar, he said into smaller pieces. On the first day of March he would give her and inch of the bar, and on each succeeding day he would add another inch to her amount of silver. She would keep this silver as security. At the end of the month, when the prospector expected to be able to pay his rent in full, she would return the pieces to him.
March has 31 days, so one way to cut the bar would be to cut it into 31 sections, each an inch long. But since it requires considerable labor to cut the bar the prospector wished to carry out his agreement with the fewest possible number of pieces. For example, he might give the lady an inch piece in the first day, another inch on the second day, then on the third day take back the two inch segments and give her a three inch piece on the third day. Assuming that the portions of the bar are traded back and forth in this fashion, see if you can determine the smallest number of pieces into which the prospector cut his silver bar. Why?
My name is Luther
31 = 1 + 2 + 4 + 8 + 16. Cut the bar into pieces one inch, two inches, four inches, eight inches and sixteen inches. In that way, you can measure all the lengths from 0 to 31 inches. If you are familiar with base 2 arithmetic, the reason why will be obvious. Otherwise, reason this way: Given a length, find the largest piece that will fit all the length. It will be more than half of the original length. next, find the largest piece that will fit into the remainder. It will be more than half of the remainder. And so on. You eventually fill in all of the original length.
You can also reason as follows: You need a length 1 for the first day. Then you need a length of 2 or another 1 for the second day. Suppose you take a piece of length 2. Thus with these two lengths you can make 1, 2, and 3 = 2 + 1. Now cut off a piece of length 4. These three peices will get you to day 7 so cut off anothe piece of length 8. This procedure leads to the five peices in the previous paragraph.
Four pieces would not be enough. Suppose you have cut the bar into four pieces. Label them a, b, c, and d. How many different lengths can you measure with these four pieces? If you are going to construct a length you either include piece a or you don't include a; you either include piece b or you don't include b; you either include piece c or you don't; and you either include piece d or you don't. That is for each piece you have two choices, include it or don't include it. Thus with four pieces of silver, the maximum number of lengths that you can measure is 2x2x2x2 = 16, which is less than 31. Notice that the 16 possibilities even includes measuring the length zero which you get by not including any of the lengths.Cheers,
Claude and Penny