Let $ \alpha,\beta$ be real numbers satisfying $ 1 < \alpha < \beta.$ Find the greatest positive integer $ r$ having the following property: each of positive integers is colored by one of $ r$ colors arbitrarily, there always exist two integers $ x,y$ having the same color such that $ \alpha\le \frac {x}{y}\le\beta.$
Problem
Source: Chinese TST 2009 3rd quiz P1
Tags: ceiling function, ratio, function, floor function, logarithms, combinatorics proposed, combinatorics
16.04.2009 21:53
I claim that the answer is $ r = 2$. We'll first show that $ r = 2$ has the desired property. Consider $ \gamma = \beta - \alpha$. We know from the Archimedean property of the reals that there exists an $ N$ such that $ N\gamma > \lceil \alpha \rceil + 3$. Then we know that we have at least $ \lceil \alpha\rceil + 1$ integers in the range $ (N\alpha,N\beta)$. Suppose for contradiction that for all $ y$ there is no $ x$ such that $ \frac {x}{y} \in (\alpha,\beta)$ and $ x$ and $ y$ are the same color. Then that means that all of the integers in the range $ (N\alpha,N\beta)$ are the opposite color as $ N$. However, we also know that every integer in the range $ ((N + 1)\alpha,(N + 1)\beta)$ is the opposite color as $ N + 1$. Since we chose $ N(\beta - \alpha)$ to be bigger than $ \lceil\alpha\rceil + 3$, these two intervals will have an integer in their intersection. Thus, $ N$ and $ N + 1$ have the same color. Since this holds for all $ N > N_0$ for some $ N_0$, we also know that $ \lceil N\alpha\rceil$ has the same color, but since this integer is in the first range, we get a contradiction. Thus, $ r = 2$ has the desired property. Now for $ r = 3$ consider the coloring $ 123111222333111111111222222222333333333...$, where $ [\frac {3^n - 1}{2},\frac {3^n - 1}{2} + 3^{n - 1})$ is colored $ 1$, $ [\frac {3^n - 1}{2} + 3^{n - 1},\frac {3^n - 1}{2} + 2\cdot3^{n - 1})$ is colored $ 2$, and $ [\frac {3^n - 1}{2} + 2\cdot3^{n - 1},\frac {3^{n + 1} - 1}{2})$ is colored $ 3$. The smallest two groups of ratios will be where you choose two from the same group or from adjacent groups. The largest you can get for the smallest group will be choosing the first and last $ 1$ of a group, which gives $ \frac {\frac {3^n - 1}{2} + 3^{n - 1} - 1}{\frac {3^n - 1}{2}} = \frac {3^n - 1 + 2\cdot 3^{n - 1} - 2}{3^n - 1} = \frac {\frac {5}{3}(3^{n} - 1) - \frac {4}{3}}{3^n - 1} < \frac {5}{3}$. The smallest you can get for the second smallest group will be choosing the last $ 3$ of one group and the first $ 3$ of the next group which gives $ \frac {\frac {3^{n + 1} - 1}{2} + 2\cdot 3^n}{\frac {3^{n + 1} - 1}{2} - 1} = \frac {3^{n + 1} - 1 + 4\cdot 3^n}{3^{n + 1} - 3} = \frac {\frac {7}{3}(3^{n + 1} - 3) + 6}{3^{n + 1} - 3} > \frac {7}{3}$. Thus, the choice $ (\alpha,\beta) = (\frac {5}{3},\frac {7}{3})$ leads to a counterexample for $ r = 3$.
16.04.2009 22:17
Hamster1800 wrote: the choice $ (\alpha,\beta) = (\frac {5}{3},\frac {7}{3})$ Presumably you are meant to find $ r$ as a function of $ \alpha, \beta$.
16.04.2009 22:42
Ahhh... I see, I misread the problem. Ah well. More practice
18.04.2009 03:12
I claim that the answer is $ \lfloor \log_\alpha \beta \rfloor + 1$. Consider the intervals $ [\alpha^n, \alpha^{n + 1})_{n = 0}^{\infty}$. First notice that we can color each of them with a single color with no problems internally. Thus the only problems which can come up are from external sources. This means that we'll have a problem if our $ n$th interval is the same as our $ n + m$th interval where $ \alpha^{n + m} < \alpha^{n + 1}\beta$, or $ \alpha^{m - 1} < \beta$ or $ m < \log_\alpha \beta + 1$, or $ m \leq \lfloor\log_\alpha\beta\rfloor + 1$. Thus, if we consider the graph where the vertices correspond to each of these intervals and there is an edge between interval $ n$ and interval $ n + m$ if $ 0 \leq m \leq \lfloor\log_\alpha \beta\rfloor + 1$, we see that if we do a greedy coloring starting from the $ 0$th interval, we'll always have colored at most $ \lfloor\log_\alpha \beta\rfloor$ of its neighbors (the ones which come before it). Thus we can color this graph with $ \lfloor \log_\alpha\beta\rfloor + 2$ colors such that there are no two integers of the same color with $ \alpha \leq \frac {x}{y} \leq \beta$. Now suppose for contradiction that we can color it with $ \lfloor\log_\alpha\beta\rfloor$ colors such that no two integers of the same color have a ratio between $ \alpha$ and $ \beta$. Consider these same intervals. Suppose that the first interval (containing $ 1$) contains an element of color $ 1$. Then the second interval's first element must not be colored $ 1$, or else we would have such a pair. Without loss of generality, let one of these integers be colored $ 2$. Then the third interval's first element must not be colored $ 1$ or $ 2$ (or maybe some others). Continuing in this way, we see that the $ k$th interval (for $ k \leq \lceil\log_\alpha\beta\rceil + 2$ (we are $ 1$-indexing where we $ 0$-indexed in the first part, giving the shift by one), since these are the intervals whose first elements could form a pair with a suitable ratio with the element $ 1$) has a corresponding set of at least $ k - 1$ colors which it cannot be. Thus, the $ \lfloor\log_\alpha\beta\rfloor + 2$nd interval's first element can not be any color contained in some set of $ \lfloor \log_\alpha\beta\rfloor + 1$ colors, which is all the colors. Thus, the first element of this interval cannot be colored suitably, a contradiction. Thus, our answer is $ r = \lfloor \log_\alpha \beta\rfloor + 1$.
06.02.2011 12:31
Hamster1800 wrote: I claim that the answer is $ \lfloor \log_\alpha \beta \rfloor + 1$. When $ \alpha=2 $, $ \beta=4 $ and $ r =\lfloor\log_\alpha\beta\rfloor+1=3 $, if we color all the integers between $ 2^{i} $ and $ 2^{i+1}-1 $ with $ i\mod3 $, there are no two integers of the same color with $ 2\leq\frac{x}{y}\leq4 $. I think the answer is $ \lceil\log_\alpha\beta\rceil $.