Mathematics for Computer Science, Problem 2.6. WOP

Question

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

Answer 1

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?

Answer 2

Let S = {1, 2, 4, ... $2^m$}

Let the target number of dollars be k.

Clearly k $\neq$ 0, 1, 2

Case 1: k < $2^m$

1.a) if k is even consider the number k/2 (as k is the smallest number for which this is not possible).

Thus there exists a subset $S^{'}$ such that sum of all its elements sum to k/2. also note that $2^m$ does not belong to $S^{'}$.

Consider the set 2$S^{'}$ constructed as follows.

If s $\in$ $S^{'}$ then 2*s $\in$ $2S^{'}$. As $2^m \notin S^{'}$ so $2S^{'}$ can be constructed without running out of elements.

Now the sum of elements is $2S^{'}$ is k. Thus our original assumption that k cannot be constructed from elements of Set S is wrong.

1.b) if k is odd a similar argument can be made for (k-1)/2. Since if we used 1 to construct (k-1)/2 we don't use it for 2*[(k-1)/2] and we can add 1 to the subset so that it sums to k again.

Case 2: K > $2^m$ but < $2^{m+1}$.

Since we have proved that the condition holds for all k < $2^m$ consider the number k-$2^m$ which is $\lt$ $2^m$. Thus k-$2^m$ can be created using some subset of S ( as proved in case 1. Note that this is without using $2^m$).

Add $2^m$ to the above set and you have a subset for k.

Answer 3

Here is how i see it. Let me know if this is correct.

If you really think about the question, every envelope has amount to the power of 2, like binary number. So every envelope can be thought of as a bit which can be set to 1 or 0

Hence basically what we need to prove it whether there is any number between 0 and $2^m$ that cannot be expressed using m bits.

In an m bit binary number we can actually express $2^m$ possible values.

Let there be a set Set = S {s∈S; such that 0<s<$2^m$-1 and s cannot be expressed using m bits}

Let assume N be any minimum value in this set, We can easily prove that N is not equal to 1 or 2

Since 2<N<$2^m$, N can be expressed as sum two numbers between 0 and N, let them be N1 and N2. Both N1 and N2 can be expressed in binary using subset of m bits and If we add N1 and N2 we would get a binary representation of N in at least m bits, if N cannot be expressed as sum of two binary numbers then N is not the smallest number which cannot be expressed in at least m bits both of which is contradiction to our assumption.

Hence the set S is empty.

Please let me know if this is correct.

Answer 4

Let $S(m)$ denote property that "For any nonnegative integer $k < 2^{m+1}$, there's a selection of envelopes whose contents add up to exactly $k$"

Proof. By well ordering property and contradiction. Suppose $S(m)$ doesn't hold for some nonnegative integer $m$. Let $C$ be the set of all counterexamples, namely, $m$'s for which $S(m)$ doesn't hold. By our assumption, $C$ is nonempty. Since $C$ is nonempty set of nonnegative integers, by WOP, there exists a smallest element $m \in C$. Obviously, $S(m)$ holds for $m=0$. Since $m \geq 1$ and $m \geq m-1 \geq 0$, $S(m-1)$ holds. Let's analyze $S(m)$ by cases:

1. Case: $0 \leq k < 2^m$. This inequality is exactly what $S(m-1)$ denotes. Since $S(m-1)$ holds, any k satisfying this inequality can be made using the envelopes numbered form $1, 2, ..., 2^{m-1}$ dollars
2. Case: $2^m \leq k < 2^{m+1}$. Notice that $2^m$ can be made using $1 + (1+2+..+2^{m-1})$. Now we need to make an amount $a$ using a selection of envelopes, where $0 \leq a < 2^m$ which $S(m-1)$ proves. That's it, we showed that any nonnegative integer $0 \leq k < 2^{m+1}$ can be made using a selection of envelopes containing $1, 2, ..., 2^{m+1}$ dollars, which proves $S(m)$. We get contradiction, so our assumption must be false. The set $C$, of all counterexamples, is empty. No counterexamples exist. $\blacksquare$