Register to reply

Stamp denominations

by feynomite
Tags: combinatorics
Share this thread:
Dec18-08, 03:59 AM
P: 22
This is a question I recently solved, but only with brute force computation. I don't know how to represent it with mathematics and am interested if anyone could help out. I'd also be impressed if anyone came up with the solution, and even more impressed for a generalized way to solve problems of this type. Here it goes:

You have to create a set of stamps wherein you can produce all numbers from 1 to 100 from the sum of up to 3 stamps. Integers only, of course.

What's the minimum number of stamps needed? Call this number K. How many different sets of stamps of size K complete the solution? This I've computed, but don't know how to count it otherwise.

Other alterations: whats the furthest a set of n stamps can reach? Example:
n=1: [1] goes up to 3.
n=2: [1, 3] goes up to 7.
n=3: ?
Also computed, but would have no idea how to count.

And here's a permutation I'm stuck on right now.. what's the maximum amount of distinct a set of size n can produce? This is a weird combinatorics problem that I cannot grasp...
n=1: 1.
n=2: 9.
n=3: 21.
n=4: ?

Thanks all for your input, and have fun :)
Phys.Org News Partner Science news on
Experts defend operational earthquake forecasting, counter critiques
EU urged to convert TV frequencies to mobile broadband
Sierra Nevada freshwater runoff could drop 26 percent by 2100

Register to reply

Related Discussions
Stamp collecting and science Biology 1
Stamp collecting General Discussion 24
Stamp problem General Math 4
Basic STAMP 2 Electrical Engineering 1