(a) Prove that given constants $a,b$ with $1<a<2<b$, there is no partition of the set of positive integers into two subsets $A_0$ and $A_1$ such that: if $j \in \{0,1\}$ and $m,n$ are in $A_j$, then either $n/m <a$ or $n/m>b$. (b) Find all pairs of real numbers $(a,b)$ with $1<a<2<b$ for which the following property holds: there exists a partition of the set of positive integers into three subsets $A_0, A_1, A_2$ such that if $j \in \{0,1,2\}$ and $m,n$ are in $A_j$, then either $n/m <a$ or $n/m>b$.
Problem
Source: Brazil National Olympiad 2019 #5
Tags: algebra
Pathological
16.11.2019 04:51
(a) Color a positive integer $x$ white if it's in $A_0$ and black if it's in $A_1.$ Select some huge $x \in \mathbb{N}$, to be specified later. We know that if $x$ is black then all integers in $(ax, bx)$ are white. If we let $f(n)$ be the smallest integer greater than $an$ and $g(n)$ be the greatest integer less than $bn$, for all $n \in \mathbb{N}$, then we know that $[f^{(k)}(x), g^{(k)}(x)]$ is all the same color. However, for sufficiently large $k, x$, we have that some two numbers $y, z$ in this interval satisfy $\frac{z}{y} \in [a, b]$, contradiction. (b) We claim that the answer is all real numbers $a, b$ satisfying $1 < a < 2 < b$ and $b \le a^2.$ First we'll show that these pairs actually work. Indeed, simply put a positive integer $n$ in $A_i$ if $ \left \lfloor \log_a (n) \right \rfloor \equiv i$ (mod $3$). Let's show that it fails if $b > a^2.$ Consider some large enough $x$. Since $x$ is big enough and $b > a^2$, the numbers $x, f(x),$ and $g(x)$ are in different sets. This also holds true if $g(x)$ is replaced by any number in the interval $[f(f(x)), g(x)].$ Hence, for sufficiently large $x$, we have that the entire interval $[f(f(x)), g(x)]$ is in the same set. By applying this for $x, x+1, x+2, \cdots$ we can obtain that all sufficiently large numbers are in the same set, which is absurd. $\square$
Letteer
16.11.2019 15:16
a)
Suppose there is such a partition. Let $M = \frac{a + 1}{b - a}$. Then for any integer $m > M$, we have $bm - a(m + 1) = (b - a)m - a > 1$.
This means that there exists at least one integer $n$ such that $n \geq a(m + 1)$ and $n \leq bm$.
Since $am < a(m + 1) \leq n \leq bm$, we have $a \leq \frac{n}{m} \leq b$. Hence $n$ and $m$ are not in the same subset.
Since $a(m + 1)\leq n \leq bm < b(m + 1)$, we have $a \leq \frac{n}{m + 1} \leq b$. Hence $n$ and $m + 1$ are not in the same subset.
But there are only two subsets, so $m$ and $m + 1$ must be in the same subset.
This being true for all $m > M$ leads to a contradiction.
Note that we only used $b > a$, instead of the full inequality $1 < a < 2 < b$.
---
b)
I only have obtained a sufficient condition: $\sqrt2 < a < 2 < b \leq a^2$.
Under this condition, let us define three subsets of $\mathbb R$: for $j = 0, 1, 2$, define $B_j$ as the union $\bigcup_{k \geq 0} [a^{3k + j}, a^{3k + j + 1})$.
Now define $A_j$ as the set of positive integers in $B_j$. Let us verify that this partition indeed satisfies our condition.
Suppose $n > m$ are in one subset $A_j$. Let $k$ (resp. $t$) be the integer such that $n$ (resp. $m$) is in the interval $[a^{3k + j}, a^{3k + j + 1})$ (resp. $[a^{3t + j}, a^{3t + j + 1})$).
If $k = t$, then we have $\frac{n}{m} < \frac{a^{3k + j + 1}}{a^{3k + j}} = a$.
If $k > t$, then $k \geq t + 1$ and we have $\frac{n}{m} > \frac{a^{3(t + 1) + j}}{a^{3t + j + 1}} = a^2 \geq b$.
---
I don't know whether this condition is also necessary. This seems to be the key point of the question, the rest being somewhat easy.
mela_20-15
19.11.2019 20:49
Consider $1<a<b$ . Draw an edge between $n<m$ iff $\frac{m}{n} \in [a,b]$. Then the chromatic number of $1,2,3,...$ is $ k=\lceil log_ab \rceil+1 $ First we show that the natural numbers are $k$-colorable . Define $T(n)=\lceil an \rceil$. Assign to: $$[1,...,T(1)-1] \to color0$$$$[T(1),...,T(T(1))-1]\to color1$$and generally $$[T^m(1),...,T^{m+1}(1)-1] \to color(m modk)$$It suffices to check that $\frac{T^{m+k-1}(a)}{T^m(a)-1}>b$ because these two are the closest numbers in the two distinct blocks with the same color ,and the inequality is true since $a^{k-1}\ge b$ . Next we show that at least $k$ colors are needed. Obviously we can find arbitrarily large $N$ such that $N-1,N $ have different colors . Note that $T(n)\le an+1$ so $T^m(n)\le a^mn+1+a+...+a^{m-1}=a^mn+C$. Choose $N$ large enough such that $N-1,N,T(N),...,T^{k-2}(N)$ should have different colours . It suffices to check that the ratio $\frac{T^{k-2}(N)}{N-1}\le b $ , $\frac{a^{k-2}N+C}{N-1}<b$ which is possible since $a^{k-2}<b$. Thus we need at least $k$ colors.
Jontronbanana16
05.03.2021 18:19
Hey @mela_20-15 , about the proof using $N-1, N, T(N), \dots, T^{k-2}(N)$, it is proved that the ratio between every pair among them, expect for $N-1$ and $N$, lies between $a$ and $b$. In fact, for large enough $N$, this isn't true. So how can we prove that it's not possible to find a $k-1$ coloring?
jayz0
27.05.2024 14:41
In fact,this problem is a special case of 2009 CTST P7.