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?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ what stamps give 2016 as the answer? $\endgroup$– JMPMar 10, 2016 at 9:43
-
$\begingroup$ @Jon Mark Perry: Since 2017 is prime, there is no interval of stamp values that gives 2016 as the answer. $\endgroup$– GamowMar 10, 2016 at 9:46
-
$\begingroup$ @Gamow well, one could say that the stamps 2017,2018,...,4032,4033 have 2016 as an answer $\endgroup$– IvoMar 10, 2016 at 9:48
-
$\begingroup$ @Ivo Beckers: Yes, you are right. (But this is a degenerate solution, and somewhat boring.) $\endgroup$– GamowMar 10, 2016 at 9:51
-
2$\begingroup$ @JonMarkPerry if I'm not mistaken 5,2017,2018,2019,2020,2021 is the smallest set of numbers that has 2016 as an answer $\endgroup$– IvoMar 10, 2016 at 10:04
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
Answer = 2009
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
Answer = 2009
$\begingroup$
$\endgroup$
What your basically asking is
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
So the answer is
2009
$\begingroup$
$\endgroup$
2
I'm not sure if this even qualifies as a puzzle; it's more of a math problem. There's a simple formula given on Wikipedia for finding the Frobenius number for a given arithmetic sequence.
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
answered Mar 10, 2016 at 9:34
-
1$\begingroup$ +1. it's better than my answer because you actual use a formula. And I agree that the question might be off-topic $\endgroup$– IvoMar 10, 2016 at 9:38
-
$\begingroup$ You can also solve this by using your brain. It is a puzzle for children of age 15, posed in the year 2009. $\endgroup$– GamowMar 10, 2016 at 9:41