|
|
EGMO 7 papers
official solutions (pdf)
video solution (at the University of Bath Vimeo site)
Problem 6
(a) Prove that for every real number $t$ such that $0<t<\frac{1}{2}$ there exists a positive integer $n$ with the following property: for every set $S$ of $n$ positive integers there exist two different elements $x$ and $y$ of $S$, and a non-negative integer $m$ (i.e. $m \geq 0$), such that
\[
|x-m y| \leq t y .
\]
(b) Determine whether for every real number $t$ such that $0<t<\frac{1}{2}$ there exists an infinite set $S$ of positive integers such that
\[
|x-m y|>t y
\]
for every pair of different elements $x$ and $y$ of $S$ and every positive integer $m$ (i.e. $m>0$).
Solution
Part (a)Let $n$ be any positive integer such that
\[\tag{Q6.1}
(1+t)^{n-1} \geq \frac{1}{t}
\]
(this inequality is actually true for every large enough $n$ due to Bernoulli's inequality).
Let $S$ be any set of $n$ distinct positive integers, which we denote by
\[
s_{1}<s_{2}<\ldots<s_{n} .
\]
We distinguish two cases.
- If $s_{i+1} \leq(1+t) s_{i}$ for some $i \in\{1, \ldots, n-1\}$, then
\[
\left|s_{i+1}-s_{i}\right|=s_{i+1}-s_{i} \leq t s_{i},
\]
and therefore the required inequality is satisfied with $x=s_{i+1}, y=s_{i}$, and $m=1$.
- If $s_{i+1}>(1+t) s_{i}$ for every $i \in\{1, \ldots, n-1\}$, then by induction we obtain that
\[
s_{n}>(1+t)^{n-1} s_{1} .
\]
As a consequence, from (Q6.1) it follows that
\[
\left|s_{1}\right|=s_{1}<\frac{1}{(1+t)^{n-1}} \cdot s_{n} \leq t s_{n}
\]
and therefore the required inequality is satisfied with $x=s_{1}, y=s_{n}$, and $m=0$.
Part (b) (Explicit formula)We claim that an infinite set with the required property exists.
To this end, we rewrite the required condition in the form
\[
\left|\frac{x}{y}-m\right|>t \text {. }
\]
This is equivalent to saying that the distance between the ratio $x / y$ and the set of positive integers is greater than $t$.
Now we construct an increasing sequence $s_{n}$ of odd coprime positive integers satisfying
\[
\frac{1}{2}-\frac{1}{2 s_{n}}>t \quad \forall n \geq 1,
\]
and such that for every $j>i$ it turns out that
\[
\frac{s_{i}}{s_{j}}<\frac{1}{2} \quad \text { and } \quad t<\left\{\frac{s_{j}}{s_{i}}\right\}<\frac{1}{2},
\]
where $\{\alpha\}$ denotes the fractional part of $\alpha$. This is enough to show that the set $S:=\left\{s_{n}: n \geq 1\right\}$ has the required property.
To this end, we consider the sequence defined recursively by
\[
s_{n+1}=\frac{\left(s_{1} \cdot \ldots \cdot s_{n}\right)^{2}+1}{2}
\]
with $s_{1}$ large enough. An easy induction shows that this is an increasing sequence of odd positive integers. For every $i \in\{1, \ldots, n\}$ it turns out that
\[
\frac{s_{i}}{s_{n+1}} \leq \frac{2}{s_{i}} \leq \frac{2}{s_{1}}<\frac{1}{2}
\]
because $s_{1}$ is large enough, which proves the first relation in (Q6.3). Moreover, it turns out that
\[
\frac{s_{n+1}}{s_{i}}=\frac{\left(s_{1} \cdot \ldots \cdot s_{n}\right)^{2}}{2 s_{i}}+\frac{1}{2 s_{i}} .
\]
The first term is a positive integer plus $1 / 2$, from which it follows that the distance of $s_{n+1} / s_{i}$ from the positive integers is greater than or equal to
\[
\frac{1}{2}-\frac{1}{2 s_{i}} \geq \frac{1}{2}-\frac{1}{2 s_{1}},
\]
which is greater than $t$ if $s_{1}$ is large enough. This proves the second relation in (Q6.3).
Part (b) (Arithmetic approach)We produce an increasing sequence $s_{n}$ of odd and coprime positive integers that satisfies (Q6.3) every $j>i$. As in the previous solution, this is enough to conclude.
We argue by induction. To begin with, we choose $s_{1}$ to be any odd integer satisfying the inequality in (Q6.2). Let us assume now that $s_{1}, \ldots, s_{n}$ have already been chosen, and let us choose $s_{n+1}$ in such a way that
$$s_{n+1} \equiv \frac{s_{i}-1}{2} \quad\left(\bmod s_{i}\right) \quad \forall i \in\{1, \ldots, n\}$$
We can solve this system because the previously chosen integers are odd and coprime. Moreover, any solution of this system is coprime with $s_{1}, \ldots, s_{n}$. Indeed, for every $1 \leq i \leq n$ it turns out that
\[
s_{n+1}=\frac{s_{i}-1}{2}+k_{i} s_{i}
\]
for some positive integer $k_{i}$. Therefore, any prime $p$ that divides both $s_{n+1}$ and $s_{i}$ divides also $\left(2 k_{i}+1\right) s_{i}-2 s_{n+1}=1$, which is absurd. Finally, we observe that we can assume that $s_{n+1}$ is odd and large enough. In this way we can guarantee that
\[
\frac{s_{i}}{s_{n+1}}<\frac{1}{2} \quad \forall i \in\{1, \ldots, n\},
\]
which is the first requirement in (Q6.3), and
\[
k_{i}+t<k_{i}+\frac{1}{2}-\frac{1}{2 s_{i}}=\frac{s_{n+1}}{s_{i}}<k_{i}+\frac{1}{2} \quad \forall i \in\{1, \ldots, n\},
\]
which implies the second requirement in (Q6.3).
Part (b) (Algebraic approach)Again we produce an increasing sequence $s_{n}$ of positive integers that satisfies (Q6.3) every $j>i$.
To this end, for every positive integer $x$, we define its security region
\[
S(x):=\bigcup_{n \geq 1}\left((n+t) x,\left(n+\frac{1}{2}\right) x\right) .
\]
The security region $S(x)$ is a periodic countable union of intervals of length $\left(\frac{1}{2}-t\right) x$, whose left-hand or right-hand endpoints form an arithmetic sequence. It has the property that
\[
t<\left\{\frac{y}{x}\right\}<\frac{1}{2} \quad \forall y \in S(x) .
\]
Now we prove by induction that we can choose a sequence $s_{n}$ of positive integers satisfying (Q6.3) and in addition the fact that every interval of the security region $S\left(s_{n}\right)$ contains at least one interval of $S\left(s_{n-1}\right)$.
To begin with, we choose $s_{1}$ large enough so that the length of the intervals of $S\left(s_{1}\right)$ is larger than 1. This guarantees that any interval of $S\left(s_{1}\right)$ contains at least a positive integer. Now let us choose a positive integer $s_{2} \in S\left(s_{1}\right)$ that is large enough. This guarantees that $s_{1} / s_{2}$ is small enough, that the fractional part of $s_{2} / s_{1}$ is in $(t, 1 / 2)$, and that every interval of the security region $S\left(s_{2}\right)$ contains at least one interval of $S\left(s_{1}\right)$, and hence at least one positive integer.
Let us now assume that $s_{1}, \ldots, s_{n}$ have been already chosen with the required properties. We know that every interval of $S\left(s_{n}\right)$ contains at least one interval of $S\left(s_{n-1}\right)$, which in turn contains an interval in $S\left(s_{n-2}\right)$, and so on up to $S\left(s_{1}\right)$. As a consequence, we can choose a large enough positive integer $s_{n+1}$ that lies in $S\left(s_{k}\right)$ for every $k \in\{1, \ldots, n\}$. Since $s_{n+1}$ is large enough, we are sure that
\[
\frac{s_{k}}{s_{n+1}}<t \quad \forall k \in\{1, \ldots, n\} .
\]
Moreover, we are sure also that all the intervals of $S\left(s_{n+1}\right)$ are large enough, and therefore they contain at least one interval of $S\left(s_{n}\right)$, which in turn contains at least one interval of $S\left(s_{n-1}\right)$, and so on. Finally, the condition
\[
t<\left\{\frac{s_{n-1}}{s_{n}}\right\}<\frac{1}{2}
\]
is guaranteed by the fact that $s_{n+1}$ was chosen in an interval that is contained in $S\left(s_{k}\right)$ for every $k \in\{1, \ldots, n\}$. This completes the induction.
|
|
