Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Stamp denominations

  1. Dec 18, 2008 #1
    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 :)
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted