5
$\begingroup$

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.

  • 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$,...2011-06-23

2 Answers 2

2

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]$.

  • 0
    congrats‌‌‌‌‌‌‌‌‌‌‌‌.2013-10-26
2

"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.

  • 0
    Makes sense. Thanks.2011-06-23