3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ what stamps give 2016 as the answer? $\endgroup$ – JMP Mar 10 '16 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$ – Gamow Mar 10 '16 at 9:46
  • $\begingroup$ @Gamow well, one could say that the stamps 2017,2018,...,4032,4033 have 2016 as an answer $\endgroup$ – Ivo Beckers Mar 10 '16 at 9:48
  • $\begingroup$ @Ivo Beckers: Yes, you are right. (But this is a degenerate solution, and somewhat boring.) $\endgroup$ – Gamow Mar 10 '16 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$ – Ivo Beckers Mar 10 '16 at 10:04
10
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

https://www.wolframalpha.com/input/?i=FrobeniusNumber%5B%7B134,135,136,137,138,139,140,141,142,143%7D%5D

So the answer is

2009

$\endgroup$
1
$\begingroup$

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.

Frobenius number for AP

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

$\endgroup$
  • 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$ – Ivo Beckers Mar 10 '16 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$ – Gamow Mar 10 '16 at 9:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.