2007-05-18

$136

Time for another puzzle. And, like, way to go with the problem solving to-date! You're just encouraging me to keep this up.

This one is from my friend J. I cried quietly to myself when he first sent it to me, but I solved it in the end. I know you can too.

You have $136. You have to divide it up into some number of bags, in whole dollar increments, so that I can come along and ask brashly for any amount and you can give it to me by handing over one or more bags (without rearranging the amounts inside). What is the minimum number of bags you require?

I had to ask J a couple of follow-up questions; I'll repeat them here for your benefit:
Q: Do I know the amount in each bag?
A: Um. Yes. (duh)
Q: When you ask for an amount, can you ask only for whole dollar increments? (Like, $12.56 is not allowed, right?)
A: Correct.

3 comments:

philxan said...

Just came across your blog, and have enjoyed looking at old puzzles. Nice work.

On this one, it can be easily solved by using a binary system, similar to how computers represent numbers:

136 = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 9 (the extra bit).

That's 8 bags total, and can be used to make any amount up to 136. Interestingly, some amounts can be made in 2 different ways. Eg. 10 = 8+2, and 9+1.

fiona-h said...

Oh perfect! Good for you.

Yours is the solution J had in mind. I came up with 8 bags too, but I divided the $ differently (I divided by 2 until I got to 17 and went from there):

1
2
2
6
6
17
34
68
---
136

Mark Hanington said...

Rats! Beaten out by philxan be mere minutes!