18. Let $A$ be a set containing only positive integers, and for any elements $x$ and $y$ in $A, |x-y| \geq \frac{x y}{30}$. Determine at most how many elements $A$ may contain.
(2 marks)
18. Let $A$ be a set containing only positive integers, and for any elements $x$ and $y$ in $A, |x-y| \geq \frac{x y}{30}$. Determine at most how many elements $A$ may contain.
18. 10
18. We note that \(x\) and \(y\) cannot be too large. Starting with \(A=\{1\}\) and applying the greedy algorithm, we try to append the smallest possible element into \(A\) each time. By this process, we get
\[
A=\{1,2,3,4,5,6,8,11,18,45\},
\]
after which we can no longer append more elements into \(A\). So \(A\) has at most 10 elements.
Let \(A=\left\{a_{1}, a_{2}, \ldots, a_{n}\right\}\). We will show that \(n \leq 10\), so that the answer is indeed 10. Suppose \(1 \leq a_{1}<a_{2}<\cdots<a_{n}\). Then \(a_{i+1}-a_{i} \geq \frac{a_{i+1} a_{i}}{30}\), or \(\frac{1}{a_{i}}-\frac{1}{a_{i+1}} \geq \frac{1}{30}\) for \(1 \leq i \leq n-1\). Summing from \(i=5\) to \(i=n-1\), we get \(\frac{1}{a_{5}}-\frac{1}{a_{n}} \geq \frac{n-5}{30}\). So \(\frac{1}{a_{5}} \geq \frac{n-5}{30}\). Noting that \(a_{i} \geq i\) for all \(i\), this implies \(5 \leq a_{5}<\frac{30}{n-5}\), from which we get \(n \leq 10\) as desired.