Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

From the book "Putnam and Beyond."

The problem:

Show that the interval [0, 1] cannot be partitioned into two disjoint sets A and B such that B = A + a for some real number a.

Proof:

Assume that A,B, and a satisfy A∪B =[0,1], A∩B =∅, B =A+a. We can assume that a is positive; otherwise, we can exchange A and B. Then (1 − a, 1] ⊂ B; hence (1 − 2a, 1 − a] ⊂ A. An inductive argument shows that for any positive integer n, the interval (1−(2n+1)a, 1−2na] is in B, while the interval (1−(2n+2)a, 1−(2n+1)a] is in A. However, at some point this sequence of intervals leaves [0, 1]. The interval of the form (1 − na, 1 − (n − 1)a] that contains 0 must be contained entirely in either A or B, which is impossible since this interval exits [0, 1]. The contradiction shows that the assumption is wrong, and hence the partition does not exist.

I don't really understand what's going on:

An inductive argument shows that for any positive integer n, the interval (1−(2n+1)a, 1−2na] is in B.

How did he come to this conclusion?

The interval of the form (1 − na, 1 − (n − 1)a] that contains 0 must be contained entirely in either A or B, which is impossible since this interval exits [0, 1].

The wording here is very confusing. Is he merely pointing to the fact that [0, 1] is a closed interval, while the other is open? — "This interval exists [0, 1]" is not a sentence that makes any syntactical sense to me.

share|improve this question
5  
The verb that was used was exits not exists. It simply means that as $n$ increases, the small interval drifts to the left, and eventually leaves (=exits) the interval $[0,1]$. Just before the exit, it must contain $0$. –  Jyrki Lahtonen Jun 23 '11 at 5:59
2  
The induction really is straight forward: $(1-a,1]$ is contained in $B$, so $(1-2a,1-a]$ is contained in $A$, so $(1-3a,1-2a]$ is contained in $B$, so $(1-4a,1-3a]$ is contained in $A$,... –  Jyrki Lahtonen Jun 23 '11 at 6:03
add comment

2 Answers

For your first question: He's shown that $(1-(2n+1)a, 1-2na] \subseteq B$ when $n = 0$. Suppose that this statement is true for some non-negative integer $n$. The fact that $B = A + a$ implies that $(1 - (2n+2)a, 1-(2n+1)a] = (1-(2n+1)a, 1-2na] - a \subseteq A$. If any point $x$ of $(1 - (2n+3)a, 1 - (2n+2)a]$ were in $A$, $x+a$ would have to be in $B$; but $x+a \in (1 - (2n+2)a, 1-(2n+1)a] \subseteq A$, so this is impossible, and we must have $(1 - (2n+3)a, 1 - (2n+2)a] \subseteq B$. That is, if $(1-(2n+1)a, 1-2na] \subseteq B$, then $(1-(2n+3)a, 1-(2n+2)a] = (1 - (2(n+1)+1)a, 1- 2(n+1)a] \subseteq B$, and it follows by induction that $(1-(2n+1)a, 1-2na] \subseteq B$ for all non-negative integers $n$.

For your second question: Part of the problem is that you've misread 'exits' as 'exists'. But yes, he's pointing to the fact that if an interval of the form $(x,y]$ contains $0$, it must also contain some negative real numbers and therefore cannot be a subset of $[0,1]$.

share|improve this answer
    
congrats‌‌‌‌‌‌‌‌‌‌‌‌. –  user102092 Oct 26 '13 at 15:53
add comment

"How did he come to this conclusion?"

By using an inductive argument, just like he said.

So, you know that $(1-a,1]\subset B$ and $(1-2a,1-a]\subset A$. Now, $1-2a$ has to be in either $A$ or $B$. It cannot be in $A$, because then $(1-2a)+a = 1-a\in B$, but $1-a\in A$ and we are assuming $A\cap B=\emptyset$. So $1-2a\in B$, which means that $1-3a\in A$. No $x$ between $1-3a$ and $1-2a$ can be in $A$, because then you would have something that lies in both $A$ and $B$ (since $x+a$ would be in $B$, but it would also be in $A$ since $1-2a \lt x+a \leq 1-2a$). So $(1-3a,1-2a]\subseteq B$, which means $(1-4a,1-3a]\in A$.

Now assume that you have shown that $(1-(2n+1)a,1-2na]\subseteq B$ and $(1-(2n+2)a,1-(2n+1)a]\subseteq A$. We cannot have $1-(2n+2)a\in A$, so it must be in $B$; hence $1-(2n+3)a\in A$, and now you can check that nothing between $1-(2n+3)a$ and $1-(2n+2)a$ can be in $A$ thanks to the induction hypothesis. This establishes the induction and the assertion.

(How did he come up with it? Probably along the lines of how I did the $n=2$ case above).

"Is he merely pointing out the fact that $[0,1]$ is a closed interval..."

If you think about what the previous part of the argument shows, it shows that $A$ and $B$ are each a (finite) union of disjoint intervals that are open on the left and closed on the right, and you keep alternating until you get to $0$. That is, there must be some $n$ such that $0\in (1-na,1-(n-1)a]$. But you need all of that interval contained in either $A$ or $B$ for the previous part to work. But if $0$ is in an interval of the form $(r,s]$, then $r\lt 0$; so either $A$ or $B$ has to contain numbers strictly smaller than $0$, which is impossible.

share|improve this answer
    
Makes sense. Thanks. –  fakaff Jun 23 '11 at 6:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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