Well Ordering Principle proof for amount of postage

274 Views Asked by At

I have encountered this task for WOP practicing and struggle with forming set of counterexamples and moving on from there.

(a) Prove using the Well Ordering Principle that, using $6¢$, $14¢$, and $21¢$ stamps, it is possible to make any amount of postage over $50¢$. To save time, you may specify assume without proof that $50¢$, $51¢$, $\dots$, 100¢ are all makeable, but you should clearly indicate which of these assumptions your proof depends on.

(b) Show that $49¢$ is not makeable.

So, if we assume $$P(n) = \text {It's possible to make any amount of postage over $50¢$ using $6¢$, $14¢$, and $21¢$ stamps}\text,$$ then: $$C = \{n \ge 50 | \neg P(n)\}$$ But how should we move on from here?

Possibly we can make something like this: $$6k_1 + 14k_2 + 21k_3 = 50$$

Then we have to find something smaller, like $c-1$ and show that C is either empty or not and prove by contradiction. How to approach it from here?