3
$\begingroup$

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!:)

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Rob Arthan Jan 21 '18 at 20:51
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Carl Mummert Jan 22 '18 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.