# Mathematics for Computer Science, Problem 2.6. WOP

This is a problem from Mathematics for Computer Science book and the same MIT course.

You are given a series of envelopes, respectively containing $1,2,4,...,2^m$ dollars. Define

Property $m$: For any nonnegative integer less than $2^{m+1}$, there is a selection of envelopes whose contents add up to exactly that number of dollars.

Use the Well Ordering Principle (WOP) to prove that Property $m$ holds for all nonnegative integers $m$.

Hint: Consider two cases: first, when the target number of dollars is less than $2^m$ and second, when the target is at least $2^m$.

I see how it this can be proved by induction but got really stuck with proving it using WOP. For example, I consider a case when $n<2^m$. I look for contradiction => some number n which is not the sum of envelopes. 0,1,2 can be made from envelopes (ok, I have some doubts about $0$, but I ignore them for now) so $n>2$. Here I totally stuck: if I try (n-1) = sum, then I can't find a way to show than { (n-1) +1 = sum of envelopes } or find any contradiction.

Please, help!:)

• What they probably want you to do is apply WOP to the set of $m$ for which Property $m$ fails and derive a contradiction if this set is non-empty. This is essentially Fermat's method of infinite descent and is basically just a form of proof by complete or strong induction. – Rob Arthan Jan 21 '18 at 20:51

## 1 Answer

After a lot of googling and considerations a have this idea:

let $n$ be the minimum number that can't be expressed as the sum of envelopes. Choose the maximum $2^k$ which is still smaller than $n$. Then we have $y = n - 2^k, n = y + 2^k$. Now by cases: if $y$ is a sum of the power of 2 that $n$ is also the sum of powers(and $2^k > y$ so not included in $y$), else $y$ is not a sum, but then $n$ is not the smallest number.

Is it correct?

• This is correct apart from one thing: perhaps $n = 0$, so we cannot choose any $2^k$ smaller than $n$. Of course, in this case the empty selection of envelopes adds up to $n$ - this should be mentioned in the proof, though. If you were to rewrite this as a proof by induction, it would become the base case for the induction. Typically, in a proof that uses WOP and contradiction like this, there are two cases: one for if the smallest bad number is as small a possible (so we have an immediate contradiction) and one when it is not (so we can make it smaller) – Carl Mummert Jan 22 '18 at 12:10