Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Discrete math hw question

  1. Nov 14, 2005 #1
    Hi,

    This is one of the question from my hw, i don't even understand what it's asking? Please shed some light on it.. thx


    what is the smallest value of k such that any integer postage greater than k cents can be formed by using only 4-cent and 9-cent stamps? Show that k cents in postage cannot be formed and use induction to prove that all larger values can be formed.



    thank you!
    A.T
     
  2. jcsd
  3. Nov 14, 2005 #2

    HallsofIvy

    User Avatar
    Science Advisor

    Obviously, since you have only 4 and 9 cent stamps, you can't "form"
    1, 2, or 3 cents in postage. You could get 4 cents obviously, but not 5 cents, 6 cents, or 7 cents. You can get 8 cents and 9 cents, but not 10 cents or 11 cents. You can make 12 cents (3 four cent stamps) or 13 cents (one 9 cent stamp and one 4 cent stamp).
    The question is asking you to show that, for some number k, ALL number from k+ 1 up CAN be made by combinations of 4 and 9: 4n+ 9m for some integers n and m.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook