Thread: Sum of two postage stamps: Part One

This is an academic question that is a little tricker than it appears to be.

Joe has a big box of 5-cent and 6-cent postage stamps. He wants to determine the amounts of total postage he can create using ONLY 5-cent and 6-cent stamps and the amounts that he CANNOT create using only 5-cent and 6-cent stamps.

Joe makes the following partial list of postage amounts he can create with only 5-cent and 6-cent stamps:

5 cents (one 5)
6 cents (one 6)
10 cents (two 5's)
11 cents (one 6 & one 5)
12 cents (two 6's)
15 cents (three 5's)
16 cents (two 5's & one 6)
17 cents (one 5 & two 6's)
18 cents (three 6's)
20 cents (four 5's)

However, he makes the following list of postage totals that he CANNOT make using only 5-cent and 6-cent stamps:

7 cents
8 cents
9 cents
13 cents
14 cents
19 cents

For individual stamp values "m" and "n" (which are positive integers) Joe wants to "generalize" the total amounts that he gets (he wants a general statement or rule that describes the relationship between x stamps of value "m", and y stamps of value "n".)

Can you give a "generalization" and explain why it works?

Under what conditions will the numbers of stamps of value m and the number of stamps of value n generate all but a finite number of postage amounts? (I.e., a certain finite number of total postage values cannot be created but all others can be.)

Under these conditions what is a formula for the largest "impossible" postage amount? I.e., a formula for the largest amount that Joe cannot create.

Thanks for any help anybody can give me.

In order that a positive integer X be a sum of 5 and 6 cent stamps, there must exist positive integers m and n such that 5m+ 6n= X. That's a "Diophantine equation". It is clear that 6- 5= 1 so 6X+ 5(-X)= X. That is, m= -X and n= X are solutions. Of course, -X is not a positive integer. But if we add 6A to m subtract 5A from n, for A any integer, 5(-X+ 6A)+ 6(X- 5A)= -5X+ 30A+ 6X- 30A = X for all A. We want or . But we must also have or . That is, , recalling that A must be an integer. In particular, that means, in particular, that if X/5 and X/6 differ by at least 1, there exist such an integer. So the first requirement we have is that from which, multiplying on both sides by 5(6)= 30, we can always form such a combination if . That does not mean that every number below that can't be formed by 5 and 6 cent stamps but gives us an upper bound so we can start just working down from that:
29= 4*6+ 5 so 29 cents is 4 six cent and 1 five cent stamp.
28= 6+ 22 and 22 is not a multiple of 5
28= 12+ 16 and 16 is not a multiple of 5
28= 18+ 10 so 28 cents is 3 six cent stamps and 2 five cent stamps.

27= 6+ 21 and 21 is not a multiple of 5
27= 12+ 15 so 27 cents is 2 six cent stamps and 3 five cent stamps.

26= 6+ 20 so 26 cents is 1 six cent stamp and 4 five cent stamps.

25= 5 five cent stamps.

24= 6 six cent stamps.

23= 6+ 17 and 17 is not a multiple of 5
23= 12+ 11 and 11 is not a multiple of 5
23= 18+ 5 so 23 is 3 six cent stamps and 1 five cent stamps.

22= 6+ 16 and 16 is not a multiple of 5
22= 12+ 10 so 22 is 2 six cent stamps and 2 five cent stamps

21= 6+ 15 so 21 is 1 six cent stamp and 3 five cent stamps

20 is 4 five cent stamps

19= 6+ 13 and 13 is not a multiple of 5
19= 12+ 17 and 17 is not a multiple of 5
19= 18+ 1 and 1 is not a multiple of 5

Whew! We have determined that every number larger than 19 can be found as a combination of 5 and 6.

HallsofIvy,

Sir, your excellent post has a syntax error message.

Could be something important has been omitted. It reads as follows:

*So the first requirement we have is that [ LaTeX Error: Syntax error ]*

Any chance you could clarify??

Regards,

MathGeezer

Thanks for pointing that out. I have editted it. (I used "\" when I should have had "/"!)