a) Determine which amounts of postage can be formed using just 4 cent stamps and 11 cent stamps. b) Prove your answers to a using strong induction.

My work:
(I am only working on part a for now)
I saw that this problem was a variation of this one 12 or more cents but that one came with the initial bounds, "Prove that every amount of postage of 12 cents or more", but here, you have to come with the initial bounds. I watched a Youtube video on how to do that problem Youtube: Strong Induction and here's the author's basis case enter image description here

Here's my work off that author's basis case
12 = 3(4) + 0(11)
19 = 2(4) + 1(11)
26 = 1(4) + 2(11)
33 = 0(4) + 3(11)
And my conclusion is that postage of 12 + multiples of 7 can be formed with just using 4 cent stamps and 11 cent stamps. Is that the correct conclusion to which amounts of postage can be formed using just 4 cent and 11 cent stamps? I wasn't completely sure because 4 can be formed with just using 1 cent stamp but I felt like there was a reason you start from 12 in the other problem, to make the induction step easier? Would you have to include numbers like 4 and 11?


Hint: start writing out all the combinations you can think of, in ascending order (for instance, the first few are $4,8,11,12,15,\dots$). You do have to include these "pre-induction" values in your answer, because they are possible to attain with only $4$ and $11$ cent stamps.

Eventually, you will write down four consecutive numbers (you'll get there before you reach $50$), and then you are ready for induction (since, for any higher number, you can the appropriate multiple of $4$ to one of the four consecutive numbers you found).

  • $\begingroup$ I went all the way up to 50 but I there was ever four consecutive numbers. The closest I got to was 32, 33, 34, 38? $\endgroup$ – committedandroider Mar 6 '15 at 19:23
  • $\begingroup$ Do it carefully! Are you sure you can't get 35, 36, or 37? $\endgroup$ – John Brevik Mar 6 '15 at 19:36
  • $\begingroup$ (you can also get $30$ and $31$) $\endgroup$ – BaronVT Mar 6 '15 at 19:44
  • 1
    $\begingroup$ @JohnBrevik Oh ok thanks guys, I got a sequence of 30, 31, 32, 33. Can I just stop here and say that every amount of postage of 30 cents or more can be made with just 4 cent and 11 cent stamps? $\endgroup$ – committedandroider Mar 9 '15 at 0:51
  • 1
    $\begingroup$ You should say why you can get every amount of postage of $30$ cents or more. It doesn't have to be a long explanation, a sentence or two will do. $\endgroup$ – BaronVT Mar 9 '15 at 14:29

the first thing to note is that the highest common factor of 4 and 11 is 1. so there is an integer combination of these two numbers that gives one. And in fact we have $$ 3 \times 4 -11 = 1. $$ So we can get any number provided we allow negative stamps. We can't allow negative stamps however.

it is clear that we can get 1 more than any multiple of 11 from this. We can get two more than any multiple of 11 that is bigger or equal to 33. And three more from 33. To get 4 more just add.

So from 11, we get 1,4, 5, 8, 9 above multiplies of 11. from 22 we 1 2 4 5 6 8 9 10 from 33 1 2 3 4 5 6 7 8 9 10

we are done.


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.