Suppose that I have k envelopes, numbered $0,1,…,k−1$, such that envelope i contains $2^i$ dollars. Using the well-ordering principle, prove the following claim.
Claim: for any integer $0 ≤ n < 2^k$, there is a set of envelopes that contain exactly n dollars between them.
How would I tackle this problem? I am stumped. I know that the well-ordering principle states that a non-empty set will always have a smallest element in the set, but I don't exactly know how to apply it to write the proof.
Best Answer
Call the positive integer $k$ bad if there is a set of $k$ envelopes, numbered $0$ to $k-1$, with contents as described in the question, and an integer $n\lt 2^k$, such that no subset of the envelopes contains exactly $n$ dollars between them.
We want to prove there are no bad $k$. Suppose to the contrary that there are. Then the set $B$ of bad $k$ is non-empty. It follows that there is a smallest bad $k$. Call it $m$.
$m$ is greater than $0$, because $m=0$ holds obviously.
So $m$ is bad, and all positive integers $\lt m$ are good.
We arrive at a contradiction by showing that $m$ is good, that is, that any number $n\lt 2^m$ of dollars can be obtained by choosing an appropriate collection of the envelopes.
Case (i), $n\lt 2^{m-1}$: Since $m-1$ is good, there is a subset of the first $m-1$ envelopes that gives sum $n$.
Case (ii), $2^{m-1}\le n\lt 2^m$. Take the contents of the biggest envelope, that is, envelope with label $m-1$, which has $2^{m-1}$ dollars.
Then we still need an amount $a$ of dollars, where $0=2^{m-1}-2^{m-1}\le a\lt 2^m-2^{m-1}=2^{m-1}$. Because $m-1$ is good, we can produce this amount $a$ from the first $m-1$ envelopes. Hence by adding the contents of the envelope with label $m-1$, we get our $n$ dollars.
Remark: This is just an ordinary proof by induction, rewritten to use "well-ordering principle" language.