Carlsbad, CA · Member since 2010 · 1k+ posts · 1k+ votes
Divide $534 (in whole $ increments) into a number of bags so that I can ask for any amount between $1 and $534, and you can give me the proper amount by giving me a certain number of these bags without opening them. What is the minimum number of bags you will require? And how much in each bag?
Rental Property Investor · Mercer Island, WA · Member since 2008 · 22k+ posts · 14k+ votes
15y
Sorry, that's trivial. Use binary numbers. You need 10 bags. The first nine hold $1, $2, $4, $8, $16, $32, $64, $128, $256. That's $511 total, so the last bag holds the remaining $23. For any requested amount less than $511, just hand over the proper combination of the first nine bags. For amounts from $512 to $534, hand over the $23 bag, subtract $23 from the requested amount and then apply the first half of the solution.
This is actually a useful problem for real estate. If you go to the trustee sale and they require a cashier's check for the bid amount, but you don't know where the bidding will end, just bring checks arranged like this and hand over the proper set of checks.
Rental Property Investor · Mercer Island, WA · Member since 2008 · 22k+ posts · 14k+ votes
15y
Sorry, that's trivial. Use binary numbers. You need 10 bags. The first nine hold $1, $2, $4, $8, $16, $32, $64, $128, $256. That's $511 total, so the last bag holds the remaining $23. For any requested amount less than $511, just hand over the proper combination of the first nine bags. For amounts from $512 to $534, hand over the $23 bag, subtract $23 from the requested amount and then apply the first half of the solution.
This is actually a useful problem for real estate. If you go to the trustee sale and they require a cashier's check for the bid amount, but you don't know where the bidding will end, just bring checks arranged like this and hand over the proper set of checks.
Real Estate Investor · Phoenix, AZ · Member since 2009 · 1k+ posts · 1k+ votes
15y
No, I was actually dumb. I got to 256 and forgot that I could have one more bag with $23 and remove bags to get to any number I wanted. The funny thing is, my alternative proposal does involve removal.
Investor · Sarasota, FL · Member since 2008 · 18k+ posts · 17k+ votes
15y
Originally posted by Vikram C.:
No, I was actually dumb. I got to 256 and forgot that I could have one more bag with $23 and remove bags to get to any number I wanted. The funny thing is, my alternative proposal does involve removal.
I used the same binary logic, but then made the same mistake you did when I said 17.
I pointed out those 10 bags, and then added the other 7 to build up to $534...forgetting that you could just subtract instead once you added the $23 bag.
Good call, Jon! I guess I'm too much of a brute force type of engineer and not so much a elegant thinker type... :D