Fall 2016, problem 28
Comments
It's based on the idea that in a certain precise sense npq has exactly "one more factor" of p than n has, if npq happens to be a natural number. |
The short and simple - and a bit sketchy - answer:
You start with $A = \{\}$ and $B = \{\}$ and make these sets larger step by step: You go through all natural numbers $n$ in the order 1, 2, 3, 4.... and if there is already a number $a \in A$, such that $\frac{n}{a} = c$ or $\frac{a}{n} = c$, then put $n$ in $B$. Otherwise put it in $A$. You can easily proof by induction, that $A$ and $B$ satisfy the requirement at every step. You get the final partition of $\mathbb{N}$ by defining $A$ (or $B$) as the union of all the intermediate $A$s (or $B$s) constructed so far. Done.
This is the general construction giving you all such partitions. I also give an
Explicit example:
It's based on the idea that in a certain precise sense $n \frac{p}{q}$ has exactly "one more factor" of $p$ than $n$ has, if $n \frac{p}{q}$ happens to be a natural number. So you partition into numbers with an even number of factors $p$ and numbers with an odd number of factors of $p$:
Let $c = \frac{p}{q}$. We may assume that $p$ and $q$ are coprime. At least one of $p$ and $q$ is not equal to 1. Since $A$ and $B$ satisfy the requirements if and only if they satisfy the same requirements with $c$ replaced by $\frac{1}{c} = \frac{q}{p}$ we may assume, that $p \neq 1$.
Given a natural number $n$, there exists unique pair of numbers $k,a$ with $k$ a nonnegative integer and $a \in \mathbb{N}$ such that:
- $a$ is not a multiple of $p$ and
- $n = p^k a $
If $n$ and $k$ are related in this way, we write: $p[n] = k$
We define $A$ and $B$ like this:
- $A := \{n \in \mathbb{N}: p[n] \textrm{ is even}\}$
- $B := \mathbb{N} \setminus A = \{n \in \mathbb{N}: p[n] \textrm{ is odd}\}$
Now we only need to check, that this choice indeed works. So consider $x, y \in A$ arbitrary. We assume for the moment, that $\frac{x}{y} = c$ and from this derive a contradiction. We have $x = a p^{2k}$ and $y = b p^{2l}$, where none of $a,b$ is divisible by $p$ and: $$\frac{x}{y} = c = \frac{p}{q} \implies p^{2(k - l) - 1} a q = b$$
If $2(k -l) -1$ is positive, then $b$ is a multiple of $p$: a contradiction. If on the other hand $2(k -l) -1$ is negative, then $a q$ is a multiple of $p$ and so - since $p$ and $q$ are coprime - $a$ is a multiple of $p$: a contradiction. The case $2(k - l) - 1 = 0$ obviously cannot occur. So we have a contradiction in any case.
If $x,y \in B$ and $\frac{x}{y} = c$ we get a contradiction in exactly the same way. Done.
For each q in Q^+ there exist exactly one smaller and one greater number such that their quotient is c. Starting from any q we can thus form a chain of these numbers, this chain is trivially a bipartite graph and can thus be split into the required sets.
Since the chains are non intersecting their union is also a bipartite graph. Since the natural numbers are a proper subset of Q^+ the proposition follows.