while the forum was hacked, someone asked this question:
hey can anyone help me out?
Divide $71 in whole $ increments into a number of bags so that I can ask for any amount between $1 and $71, and you can give me the proper amount by giving me a certain number of therse bags without opening them. What is the minimum number of bags you will require?
please help if you can,
lets see, well if you have to divide them into a group of equal parts, then you'd have to divde it by 71. Anything more then one each and you would not be able to ask for one.
If you can divide it into groups of unequal parts, each bag containing a certain number of whole dollars, then it gets slightly more interesting. If you put 10 in one bag, and put the remaining 61 into individual bags, then you will be able to make the numbers between 1 and 10, by using the additional ones. Therefore I suppose if you put extra in one bag, you need enough singles to cover the numbers from 1 to that point. Lets say we put 36 in one bag and put the remaining 35 into individual bags. For numbers less then 36 you can use the individual bags, for 36 you can use the big bag, any more and you can add the big bag to any number of small bags to make any number from 37 to 71. Now we reduced 71 to 36 bags, lets see if we can the 35 small bags to less bags. Again lets take the midpoint. If 18 in one bag and the remaining 17 into individual bags, we can make the numbers less then 18 by using the individual small bags, we can make 18 using the big bag, and any number between 18 and 36 by using the big bag and adding the individual small bags. So now we've got one big bag with 36, another big bag with 18, and 17 litte bags. If my reasoning proccess is correct, it looks like we are dividing the number by 2 using integer division, then giving the bigger bag the remainder, and the repeat.
So it should be 36, 18, 9, 4, 2, 1, 1. Hope I worked that out right. Kind of a confusing algorithm. I'm not used to doing integer division. lol. Anyway it looks like the answer is 7 bags.