# Ten types of stamps

The country Dalgonia issues stamps of only ten different denominations: $134$, $135$, $136$, $137$, $138$, $139$, $140$, $141$, $142$, and $143$ cents. What is the largest amount of cents which cannot be made up with a combination of these stamps?

• what stamps give 2016 as the answer? – JMP Mar 10 '16 at 9:43
• @Jon Mark Perry: Since 2017 is prime, there is no interval of stamp values that gives 2016 as the answer. – Gamow Mar 10 '16 at 9:46
• @Gamow well, one could say that the stamps 2017,2018,...,4032,4033 have 2016 as an answer – Ivo Beckers Mar 10 '16 at 9:48
• @Ivo Beckers: Yes, you are right. (But this is a degenerate solution, and somewhat boring.) – Gamow Mar 10 '16 at 9:51
• @JonMarkPerry if I'm not mistaken 5,2017,2018,2019,2020,2021 is the smallest set of numbers that has 2016 as an answer – Ivo Beckers Mar 10 '16 at 10:04

None of the numbers less than 134 can be obtained with this set of stamps.
All of the numbers in the range 134-143 can be obtained with a single stamp.
None of the numbers between 143 and 2 * 134 can be obtained with a combination of these stamps.
More generally, numbers that lie in the range between (n-1)143 and n(134) cannot be obtained.
Because the stamps are in increments of 1, every value between 134n and 143n can be obtained.

So we need to discover where 134 * n is less than or equal to 143 * (n-1)
Solving 134n = 143n - 143
Gives 143 = 9n
n=15.89
So , for who number values of n greater than 15, there is no number that exists between the highest number obtainable with a combination of n-1 stamps and the lowest number that can be obtained with n stamps. All values above this can be achieved. We need the highest number that exists in the gap below this, i.e. 15 * 134 -1

What is the Frobenius Number of these numbers: 134,135,136,137,138,139,140,141,142,143

Thankfully, Wolfram Alpha has a built-in function for that

We can now substitute the values $a=134$, $d=1$ and $s=9$. Using it, we get the answer 2009 as already given by @IvoBeckers