Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

James Joseph Sylvester was one the greatest British mathematicians of the 19th century, who made many fundamental contributions to number theory, combinatorics, and invariant theory. In 1884, he posed the following mathematical puzzle in the Educational Times:

A man possesses a large quantity of stamps of only two denominations: $5$-cent stamps and $17$-cent stamps. What is the largest (finite) amount of cents which the man cannot make up with a combination of these stamps?

This was apparently the first occurrence of the Frobenius problem as a mathematical puzzle. What's the solution?

share|improve this question
    
It is possible not to use 5 cent stamps or 17-cent stamps at all with your combination or you have to use at least one of each? – Oray Mar 7 at 14:34
    
@Oray: "combination of 5-cent stamps and 17-cent stamps" means "a non-negative number of 5-cent stamps and a non-negative number of 17-cent stamps". – Gamow Mar 7 at 14:36
    
then 0 is okay since it is not negative or positive. – Oray Mar 7 at 14:37
    
Yes, 0 is okay. – Gamow Mar 7 at 14:37
up vote 117 down vote accepted

For the more visually inclined, arrange all positive integers in a 5-wide chart, as follows:

 1   2   3   4   5
 6   7   8   9  10
11  12  13  14  15
16  17  18  19  20
21  22  23  24  25
26  27  28  29  30
31  32  33  34  35
36  37  38  39  40
41  42  43  44  45
46  47  48  49  50
51  52  53  54  55
56  57  58  59  60
61  62  63  64  65
66  67  68  69  70
..  ..  ..  ..  ..

To start, all the values in the rightmost column are divisible by 5, and thus can be made up simply of a number of 5-cent stamps. They can all be eliminated.

 1   2   3   4  --
 6   7   8   9  --
11  12  13  14  --
16  17  18  19  --
21  22  23  24  --
26  27  28  29  --
31  32  33  34  --
36  37  38  39  --
41  42  43  44  --
46  47  48  49  --
51  52  53  54  --
56  57  58  59  --
61  62  63  64  --
66  67  68  69  --
..  ..  ..  ..  --

Note that if you can generate a solution for any particular value on the chart, you can also generate a solution for the value directly below it by adding one 5-cent stamp. Likewise, you can find a solution for the next value down by adding another 5-cent stamp, and this cascades down into infinity.

Thus, since a solution for the value 17 is simply a single 17-cent stamp, we can eliminate that and every value below it in the second column.

 1   2   3   4  --
 6   7   8   9  --
11  12  13  14  --
16  --  18  19  --
21  --  23  24  --
26  --  28  29  --
31  --  33  34  --
36  --  38  39  --
41  --  43  44  --
46  --  48  49  --
51  --  53  54  --
56  --  58  59  --
61  --  63  64  --
66  --  68  69  --
..  --  ..  ..  --

Similarly, since a solution for the value 34 is two 17-cent stamps, we can eliminate that and every value below it in the fourth column.

 1   2   3   4  --
 6   7   8   9  --
11  12  13  14  --
16  --  18  19  --
21  --  23  24  --
26  --  28  29  --
31  --  33  --  --
36  --  38  --  --
41  --  43  --  --
46  --  48  --  --
51  --  53  --  --
56  --  58  --  --
61  --  63  --  --
66  --  68  --  --
..  --  ..  --  --

Since a solution for the value 51 is three 17-cent stamps, we can eliminate that and every value below it in the first column.

 1   2   3   4  --
 6   7   8   9  --
11  12  13  14  --
16  --  18  19  --
21  --  23  24  --
26  --  28  29  --
31  --  33  --  --
36  --  38  --  --
41  --  43  --  --
46  --  48  --  --
--  --  53  --  --
--  --  58  --  --
--  --  63  --  --
--  --  68  --  --
--  --  ..  --  --

Finally, since a solution for the value 68 is four 17-cent stamps, we can eliminate that and every value below it in the third column.

 1   2   3   4  --
 6   7   8   9  --
11  12  13  14  --
16  --  18  19  --
21  --  23  24  --
26  --  28  29  --
31  --  33  --  --
36  --  38  --  --
41  --  43  --  --
46  --  48  --  --
--  --  53  --  --
--  --  58  --  --
--  --  63  --  --
--  --  --  --  --
--  --  --  --  --

Thus we can see that the highest possible value we can not make is 63 cents.

EDIT: I sacrificed some rigor in order to make the above a more accessible read. What follows attempts to somewhat bridge the gap, but if you're satisfied with the above, you can stop reading here.

What I didn't actually prove above was that the remaining numbers in the last chart cannot be made with only 5- and 17-cent stamps. For that, note that to have a valid solution for a given value, you must have 0 or more 17-cent stamps. The first elimination above accounted for all the cases where there are 0 17-cent stamps (except for the trivial case of no stamps at all). This is apparent when you consider that stepping downward in the chart is equivalent to incrementing the count of 5-cent stamps for each step, while keeping the 17-cent stamp count constant. Likewise, the remaining 4 eliminations account for all possible values for 1, 2, 3, and 4 17-cent stamps. When we get to 5 or more 17-cent stamps, the minimum value is 5*17=85. However, since we've already determined that all values above 63 have valid solutions, no more eliminations can be made. Therefore, the remaining numbers must all have no solution.

share|improve this answer
28  
This is a lovely proof! +1 – Lynn Mar 7 at 20:09
    
Thanks for the visual explanation! – feelinferrety Mar 9 at 17:23
    
Of course 68 is (5-1)*17 and then you step down another five: (5-1)*17-5=63 to arrive to this number and as such it is visible that for any coprime k and l you'd be able to draw the exact same proof to k*l-k-l being the largest number. The symmetry is beautiful. – chx Mar 9 at 19:36
    
Very nice. The only thing I'd suggest is specifically pointing out why we can't make 63. (In other words, it can't be made with 0-3 17s plus some 5s). That's sort of inherent in your diagram, but it'd be helpful to include some statement for completeness. – Duncan Mar 9 at 23:38
    
@Duncan Yeah, there were already several answers that were attacking the mathemetical side of it when I wrote this... I made some sacrifices to make something a little easier to grasp for those without a math background. Since this has really ballooned, though, I just put in a little addendum trying to fill in some of the missing pieces. – glibdud Mar 10 at 0:37

The largest solution you cannot obtain is:

63

Reason:

This is because numbers that end in either 9 or 4 can be obtained by just taking two multiples of 17 and then using combinations of 5. As you multiple 17 more and more, you get different endings to which adding 5 will give you one more number ending. Every number from 63 and above is achievable using a combination of 17 and 5 from this.

Additionally:

I will be adding a graph/plot soon to confirm my answer. However, currently, where I am typing this answer from (my school), much of the frontend/backend required by websites to plot graphs gets blocked and so it isn't possible from here.

share|improve this answer

The general picture here is as follows: if you have two positive integers $m,n$ with no common factor then every integer bigger than $mn-m-n$ can be written as $am+bn$ with $a,b$ non-negative integers, but $mn-m-n$ itself can't.

Proof:

First, suppose $mn-m-n = am+bn$. Then $(b+1)n$ is a multiple of $m$, and therefore (since $m,n$ have no common factor) so is $b+1$; so $b \geq m-1$. Similarly, $a \geq n-1$. So $am+bn \geq 2mn-m-n$, contradiction.

So $mn-m-n$ isn't $am+bn$ with $a,b$ non-negative integers.

[In this particular case, this says: suppose $63=5a+17b$. Then $80=5a+17(b+1)$, so $17(b+1)$ is a multiple of 5, so $b+1$ is too, so $b\geq4$. And $68=5(a+1)+17b$, so $5(a+1)$ is a multiple of 17, so $a+1$ is too, so $a\geq16$. But then $5a+17b\geq80+68>63$, contradiction.]

Now, to show that any integer $k\geq mn-m-n+1=(m-1)(n-1)$ will do, we'll first do it allowing negative numbers of stamps, and then fix up the negativity.

It turns out that if you allow a negative number of stamps, you can do this for any $k$. Let's do it for $k=1$; that is, find $a,b$ not necessarily non-negative with $am+bn=1$. One way to do it is to run Euclid's algorithm on $m,n$ and keep track of how to write every number involved in the form $am+bn$. At the last step, one of those numbers is 1 and you're done.

[In this particular case, we'll find e.g. that $7\times5-2\times17=1$.]

So now we have $k=(ka)m+(kb)n$, but of course our coefficients may be negative. The remaining job will be to fix it up.

[In this particular case, let's take $k=64$; we get $64=448\times5-128\times17$.]

So, how to fix it up? If $am+bn=k$ then for any integer $t$ we have $(a+tn)m+(b-tm)n=k$. We'll try to choose $t$ to make both $a+tn$ and $b-tm$ non-negative. That means making $t\geq -a/n$ and $t\leq b/m$. If we can't do this then there's no integer between $-a/n$ and $b/m$, which means $b/m-(-a/n)<1$; that is, $b/m+a/n<1$; that is, $am+bn<mn$. The LHS here is our $k$, but (alas!) this isn't quite the inequality we're looking for; we'll have to be more precise.

The trick here is that $a+tn$ and $b-tm$ are always integers. So making them non-negative is the same as making them $>-1$; what we need, then, is $a+tn>-1$ and $b-tm>-1$; equivalently, $t>(-a-1)/n$ and $t<(b+1)/m$. If there is no integer (strictly) between $(-a-1)/n$ and $(b+1)/m$ then that interval must be no longer than 1 unit, so $(b+1)/m+(a+1)/n\leq1$. Multiplying through by $mn$ and using $am+bn=k$ gives us $k<=mn-m-n$, and we're done.

[In this particular case with k=64 as above, what we need is $448+17t\geq0$ and $-128-5t\geq0$, which we tweak to $448+17t>-1$ and $-128-5t>-1$, which are equivalent to $t>-449/17$ and $t<-129/5$. Those bounds are approximately -26.4 and -25.8 respectively, and as you can see -25 lies between them.]


What if the two positive integers $m, n$ do have a factor in common? In the case of e.g. 15 and 21, both denominations are divisible by 3. This in turn means that any combination will be divisible by 3, and thus there are infinitely many values that you cannot make up by a combination. In general, if the greatest common divisor of $m,n$ is $d$, then you can only make multiples of $d$; the largest that you can't will be $d((m/d)(n/d)-(m/d)-(n/d))=mn/d-m-n$.

share|improve this answer

with 5-cent stamps and 17-cent stamps you can find any number that ends with 4 and 9 with the equation below after 39 (considering you have at least one 5-cent and one 17-cent stamp);

$5n+34\ where\ n>0$

Similarly, you can find any number that ends with 2,7,1,6,3,8,0,5 after the numbers stated in the equations below:

$5n+17\ where\ n\geqslant 0$ after 17 ending with 2,7.

$5n+51\ where\ n\geqslant 0$ after 51 ending with 1,6.

$5n+68\ where\ n\geqslant 0$ after 68 ending with 8,3.

$5n+85\ where\ n\geqslant 0$ after 85 ending with 0,5.

$5n\ where\ n\geqslant 0$ after 0 ending with 0,5 since you do not have to use 17-cent stamp.

As a result After 68, you can find any number you want by using 5 and 17-cents. So the next number below 68 by using the equation $5n+68$ will be the upper limit where $n=-1$.

63.

share|improve this answer
    
I think you are allowed to use one type of stamp, so 13 5 cent stamps could make 85. – Trenin Mar 7 at 14:26
    
@Trenin the question states that "a combination of these stamps"... So I presume it requires to use at least one 5-cent stamp and one 13-cent stamps by "a combination of these stamps" – Oray Mar 7 at 14:28
    
To me, a valid combination would be to use zero 17 cent stamps. The point of the question seems to be what values you can make from those stamps. In my opinion, there is no need to add the restriction that you must use at least one. But that is just me - OP should either clarify or comment. – Trenin Mar 7 at 14:33
    
@Trenin you might be right, let's see what Gamow would say. – Oray Mar 7 at 14:34
    
@Trenin you were right, I fixed it with that information. – Oray Mar 7 at 14:41

I solved this by considering modulus.

Once we can make a number x from the stamps, we can then make any x + 5y by adding y more 5-cent stamps. So, once we can make a number x for each modulus of 5, we can make all the remaining numbers.

So, we can make a chart of n, where n is the number of 17-cent stamps, show its value in cents (n*17), and show which modulus of 5 it corresponds to. Once we have found all the modulus 5 values, we can make any number thereafter.

n   n*17    n*17 modulus 5
0   0       0
1   17      2
2   34      4
3   51      1
4   68      3

Once we reach 68, we can create all modulus 5 values thereafter. Since 68 is the first number we can create with modulus 5 = 3, then the previous modulus 5 = 3 value (68-5=63) must have been the last number we couldn’t create.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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