[Guest]

Imagine you are an empress or emperor of a new kingdom and you need to introduce a new currency named Shlumpies. You call your Minister of Finance and ask her to design paper bills for Shlumpies. What is the minimal number of different denominations that you need to design, if you want to be able to pay any number of Shlumpies (up to a 100) using no more than three bills of each type?

For example, in the US kingdom we have $1, $2, $5, $10, $20, $50 bills. You can pay any dollar amount (up to a $100) using up to three bills of each type. Your kingdom is trying to be superior, managing with less types of bills. Can you do it?

[roolstar]

If no more than 3 bills of each should be used,

1, 4, 16, 64 will cover up to 255

Adding 256 will cover up to 1023

Adding 1024 we can go as high as 4096

...

I think I've seen these numbers somewhere before... Hmmm...

Edited October 22, 2009 by roolstar

[Guest]

if you had bills of 1, 4, 16, and 64 denominations, you should be able to cover it with up to 3 bills of each type.

[Guest]

Do you mean you can only use 3 bills to pay or you can use each bill up to 3 times?

By any ammount are you talking whole Shlumpies or fractions as well? ie. 12.95

[Guest]

Do you mean you can only use 3 bills to pay or you can use each bill up to 3 times?

Valid question. But question meant the latter.

By any ammount are you talking whole Shlumpies or fractions as well? ie. 12.95

I think, no. Not fractions.

to use a 4-base number.

[Guest]

Then I suggest we alter the problem;

What denominations are required to make any whole number from 1-100 you can only use 3 bills total?

And no I do not have the answer, you guys are smart enought to figure it out.

[Guest]

What denominations are required to make any whole number from 1-100 you can only use 3 bills total?

3 bills in total "at a time" Right?

example:

if you had denominations 1, 2, 4. you cannot make 13 as 4,4,4 will be 12 only.. you cannot add 1 to it. as it will be the 4th bill for 13.

[Guest]

1 2 10 40

[Guest]

3 bills in total "at a time" Right?

example:

if you had denominations 1, 2, 4. you cannot make 13 as 4,4,4 will be 12 only.. you cannot add 1 to it. as it will be the 4th bill for 13.

Wrong, No more that THREE of EACH type of bill

in your example 4+4+4+1 = 13

[Guest]

Wrong, No more that THREE of EACH type of bill

in your example 4+4+4+1 = 13

You didnt get it. You cannot use more than three coins at a time to make a value. 4+4+4+1 uses 4 coins to make 13. While you can use only (and any) 3 AT A TIME.

Got it?

[Guest]

I believe the OP said

using no more than three bills of each type?

This would indicate more than 3 bills is OK, just not more than three of a specific denomination.

1 4 16 64 is great, and seems the most efficient

[Guest]

Lil Stinker, I believe you may have missed kkehoe's suggestion to alter the problem. Also, for what it's worth, I like Tonybz's answer more, even though it provides a lower maximum possible value, because the numbers would be easier to work with (imagine using these bills in real life).

The smallest number of bills I have stumbled on so far is 13. This could be accomplished several ways:

1,2,3,4,5,6,19,32,45,58,71,84,97 is one example

1,2,3,4,5,6,7,22,37,52,67,82,97 is another.

I can't prove that this is the best...

[Guest]

here it can be done in 11:

1,2,3,4,5,6,7,15,38,61,84

1,2,3,4,5,6,13,33,53,73,90

1,2,3,4,5,11,28,45,62,79,96

1,2,3,4,9,23,37,51,65,79,93

[Guest]

that makes the problem much more difficult that's for sure.

i believe this is the best you can do.

1,2,5,10,17,26,37,50,65,82

[Guest]

phillip, great job but I can't see how you get 58

[Guest]

well thanks for the headache.

1,2,4,7,11,16,24,37,55,80

1

2

2 1

4

4 1

4 2

7

7 1

7 2

7 2 1

11

11 1

11 2

11 2 1

11 4

16

16 1

16 2

16 2 1

16 4

16 4 1

16 4 2

16 7

24

24 1

24 2

24 2 1

24 4

24 4 1

24 4 2

24 7

24 7 1

24 7 2

16 16 2

24 11

24 11 1

37

37 1

37 2

37 2 1

37 4

37 4 1

37 4 2

37 7

37 7 1

37 7 2

24 16 7

37 11

37 11 1

37 11 2

24 16 11

37 11 4

37 16

37 16 1

55

55 1

55 2

55 2 1

55 4

55 4 1

55 4 2

55 7

55 7 1

55 7 2

37 24 4

55 11

55 11 1

55 11 2

37 16 16

55 11 4

55 16

55 16 1

55 16 2

37 37

37 37 1

37 37 2

37 24 16

55 16 7

55 24

80

80 1

80 2

80 2 1

80 4

80 4 1

80 4 2

80 7

80 7 1

80 7 2

55 24 11

80 11

80 11 1

80 11 2

55 37 2

80 11 4

80 16

80 16 1

80 16 2

55 37 7

80 16 4

[Guest]

1, 2, 4, 6, 9, 10, 31, 44, 61, 78, 95

[Guest]

There would be way to many slots in the register...

I like the original question better..