Bay Area Mathematical Olympiad

Solution:

Suppose the statement is false. So there are only finitely many values for which $y_{n}>\sqrt{n}$; suppose there are $R_{1}$ such values. Let $m$ be the largest integer such that $x_{n} / y_{n} \geq m$ for all $n$ (this is possible since every $x_{n} / y_{n}>0$; note that it may be the case that $m=0$ ). We have $x_{n} / y_{n}<m+1$ for some $n$, say $n=R_{2}$, and since the sequence $\left(x_{n} / y_{n}\right)$ is decreasing, we then get $x_{n} / y_{n}<m+1$ for all $n \geq R_{2}$. Letting $R=R_{1}+R_{2}$, we obtain
$$y_{n} \leq \sqrt{n} \quad \text{ and } \quad m \leq x_{n} / y_{n}<m+1$$
for all $n$, with at most $R$ possible exceptions.

Now fix any positive integer $N$. The pairs of positive integers $\left(x_{n}, y_{n}\right)$ for $n<N^{2}$ are all distinct, since the corresponding values of $y_{n} / x_{n}$ are strictly increasing; and except for at most $R$ of them, the remaining ones all satisfy
$$y_{n} \leq \sqrt{n}<N$$
and
$$m y_{n} \leq x_{n}<m y_{n}+y_{n} .$$
So we have $N-1$ possible values for $y_{n}$ (namely $1,2, \ldots, N-1$ ), and for each such value, we have $y_{n}$ choices for $x_{n}$ (namely $m y_{n}, m y_{n}+1, \ldots, m y_{n}+y_{n}-1$ ), giving $1+2+\cdots+(N-1)=$ $N(N-1) / 2$ possible pairs obtained in this way. Hence, counting all the pairs $\left(x_{n}, y_{n}\right)$ for $n<N^{2}$, we have
$$N^{2}-1-R \leq N(N-1) / 2 .$$
But since $R$ is fixed, clearly this inequality will become false for large enough $N$. At this point we have a contradiction, and the problem is solved.