problem: Prove the fact using WOP: every amount of postage that can be assembled using only 10 cent and 15 cent stamps is divisible by 5.
The problem provides a template for this proof and asks that we fill in the remainders after a the ellipsis.
I got through the first part of the proof:
Let C be the set of counterexamples namely C: = {n | ...S(n) and NOT 5 |n}, where S(n) returns T/F depending on whether the amount of postage can be assembled using 10 cents and 15 cents stamps. *Note 5 | n means that n is divisible by 5.
Assume for the purpose of obtain a contradiction that C is nonempty. By WOP there must be a least element m. This m > 0 because...it is assumed that the amount of postage n > 0.
But if S(m) holds and m is positive, then S(m-10) or S(m-15) must hold because...
The above statement is confusing me. For example S(25) holds because m > 0 and is comprised of one 10 cents AND one 15 cents. However, would S(25-10) or S(25-15) hold? I believe these wouldn't hold since S(15) and S(10) cannot each be comprised of 10 cent AND 15 cent multiples.
Hope my question makes sense.
Thanks.
Yes, $S(15)$ should return true because $15 = 0 \cdot 10 + 1 \cdot 15$. Note that $0$ is a $10$-cent multiple.
Now since $m > 0$, we know that this counterexample must either contain at least one $10$-cent stamp or at least one $15$-cent stamp. If the former occurs, then we know that $m - 10$ can also be assembled using (at least zero) $10$-cent stamps and (at least zero) $15$-cent stamps. If the latter occurs, then we know that $m - 15$ can also be assembled using (at least zero) $10$-cent stamps and (at least zero) $15$-cent stamps. So $S(m - 10)$ or $S(m - 15)$ must return true. But notice that since $5$ doesn't divide $m$, it also won't divide $m - 10$ or $m - 15$ (since $10$ and $15$ are multiples of $5$). Thus, $m - 10$ or $m - 15$ belong to $C$, contradicting the minimality of $m$ (as desired).