1

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.

Gerry Myerson
  • 179,216
user3761743
  • 87
  • The question doesn't mean that you must use at least one 10-cent stamp and at least one 15-cent stamp: it means that you're allowed to use 10-cent stamps and you're allowed to use 15-cent stamps, and you're not allowed to use any other sorts of stamps. –  Aug 09 '14 at 23:58

1 Answers1

1

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).

Adriano
  • 41,576
  • Sorry, I don't think I follow, esp. your statement: "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." Say m = 15, then S(15) = True. But shouldn't S(5) or S(0) return False since neither of those values can be assembled from 10 or 15 cents? Otherwise for any number n S(n) will always return True which doesn't make sense... – user3761743 Aug 10 '14 at 03:04
  • Think of the argument like this. Suppose that $m \in C$ so that $S(m)$ returns true and $m$ is not divisible by $5$. Now since $S(m)$ returns true, we know that $m \geq 0$ (since $m$ can be assembled using $x$ $10$-cent stamps and $y$ $15$-cent stamps, where $x,y \geq 0$). But since $5 \mid 0$, we know that $m \neq 0$ so that $m \geq 1$. Hence, either $x \geq 1$ or $y \geq 1$. In other words, $m$ can be assembled with at least one stamp. Removing this stamp doesn't change the fact that it will still belong to $C$. – Adriano Aug 10 '14 at 04:38
  • That makes sense. But can you explain why S(0) holds? – user3761743 Aug 10 '14 at 13:40
  • After this step the template continues: "So suppose S(m-10) holds. Then 5 | (m-10) because if 5 | (m-10) weren't true, it would be a smaller counterexample than m, contradicting the minimality of m. Then it continues that if 5 | (m-10), then 5 | m because if 5 | (m-10), then obviously 5 | m. I don't really get the last statement. Instead I wrote that since m is a linear combination of 10 and 15, 10 and 15 share common factor of 5. Therefore 5 | m. Does this work? – user3761743 Aug 10 '14 at 14:02
  • $S(0)$ holds true because $0 = 0 \cdot 10 + 0 \cdot 15$. They are using the fact that since $5 \mid (m - 10)$ and since $5 \mid 10$, we know that $5$ divides their sum so that $5 \mid m$. That is, $m$ is a linear combination of $m - 10$ and $10$. What you wrote was a direct proof that avoids the Well-Ordering Principle altogether. – Adriano Aug 10 '14 at 22:00
  • @Adriano I have real difficulties with proving things by WOP. The theorems are very easy statements, but the logical deduction is really hard. I guess to large part, this is due to general difficulty with proof by contradiction as stated here. Do you have any suggestions how one could come up with the statements like yours? – senseiwu Jan 14 '22 at 07:43