Determine all positive real numbers $a$ such that there exists a positive integer $n$ and partition $A_1$, $A_2$, ..., $A_n$ of infinity sets of the set of the integers satisfying the following condition: for every set $A_i$, the positive difference of any pair of elements in $A_i$ is at least $a^i$.
Problem
Source: MOP 2006 Homework - Black Group #1
Tags: ceiling function, logarithms, combinatorics unsolved, combinatorics
28.04.2014 17:46
This is easy if you know the idea of upper density. The upper density of a set $K$ is equal to $\overline{d}(K)=\limsup_{m\rightarrow\infty}\frac{|K\cap\{1, 2, \ldots m\}|}{m}$. It can be proven that $\overline{d}(K\cup L)\leq \overline{d}(K)+\overline{d}(L)$ for any $K$ and $L$.
Let us suppose (without harm) that if it's possible to be done, we have that the $A_i$ contain only natural numbers, and $B_i$ contain all the negative numbers. We can also without harm forget about 0; we can just replace each number $x$ in each $A_i$ with $x-1$ to cover 0. Let us work solely with the natural numbers now - assume that $A_i\subseteq\mathbb{N}$. Now in $A_i$, the difference between any two consecutive terms is at least $a^i$, so the size of $A_i$ that is in $\{1, 2, \ldots m\}$ is at most $\left\lceil\frac{m}{a^i}\right\rceil$. Thus dividing by $m$ and taking the $\limsup$, we find that the upper density of $A_i$ is at most $\frac{1}{a^i}$. Then this means that $1=\overline{d}(\mathbb{N})=\overline{d}(A_1\cup A_2\cup A_3\ldots \cup A_n)\leq \sum_{i=1}^n\overline{d}(A_i)\leq\sum_{i=1}^n\frac{1}{a^i}<\sum_{i=1}^{\infty}\frac{1}{a^i}$ $=\frac{\frac{1}{a}}{1-\frac{1}{a}}=\frac{1}{a-1}$. So $a<2$. We can prove that any such $a$ works. Let $n$ be an integer so that $2^{n-1}>a^n$ (take, for example, $n=\left\lceil\frac{\log 2}{\log 2-\log a}\right\rceil$). Then let $A_i$ be the set of all integers $2^{i-1}\mod 2^i$ for $1\leq i\leq n-1$, and let $A_n$ be all numbers divisible by $2^{n-1}$. Clearly any two consecutive numbers in $A_i$ have a difference of $2^i>a^i$ for $i\neq n$, and two consecutive numbers in $A_n$ have difference $2^{n-1}>a^n$ as required.