We will use the following result. Proposition 1 (corollary of Liouville's theorem) There exists a constant $C_1$ such that: $ \frac{C_1}{q^2} < \left | \sqrt{2}-\frac{p}{q} \right|$ holds for all rationals $\frac{p}{q}$. Now we are ready to prove the problem. Let us denote $q_n=2^n,\, n=0,1,\ldots$. Claim: There exists $N_0 \in \mathbb{N}$ such that the count of the numbers $n_j$ between every pair $q_n, q_{n+1} $ is no more than $N_0$. Proof: Assume on the contrary that for every $N\in \mathbb{N}$ there exists a pair $q_n, q_{n+1}$ s.t. $q_n \leq n_j \leq q_{n+1},\, j=r,r+1,\ldots,r+N-1$ Therefore: $\left |\sqrt{2} n_j- m_j\right | < \frac{C}{n_j}\leq \frac{2C}{q_{n+1}} ,\, j=r,r+1,\ldots,r+N-1$ Then pigeonhole yields: $\left |\sqrt{2} (n_j-n_i)- m\right | < \frac{4C}{N \cdot q_{n+1}}$ , for some $ j,i \in [r,r+N-1]\,,\, m\in \mathbb{N} $. This implies: (1) $\left |\sqrt{2} - \frac{m}{n} \right | < \frac{4C}{N \cdot q_{n+1} \cdot n} < \frac{4C}{N \cdot n^2} $ where $n=n_j-n_i < q_{n+1}$ In (1) we can raise $N$ as big as we want, which contradics Proposition 1. $\blacksquare$ Now we can set $q=2^{\frac{1}{2N_0}}$.

dgrozev wrote: Proposition 1 (corollary of Liouville's theorem) There exists a constant $C_1$ such that: $ \frac{C_1}{q^2} < \left | \sqrt{2}-\frac{p}{q} \right|$ holds for all rationals $\frac{p}{q}$. Can somebody explain a proof to this?

For a proof of the Liouville's result see for example here.

Another solution follows immediately from the proof of Louville's Theorem. Let $ f(x) = x^2 - 2 $ and assume we had some rational approximation (by this I mean, if the denominator is a fixed positive integer then the numerator is the optimal nonnegative integer) $ \frac{m}{n} $ to $ \sqrt{2}. $ Then by Rolle's Theorem there exists a $ r \in \mathbb{R} $ between $ \frac{m}{n} $ and $ \sqrt{2} $ such that $ \frac{f\left(\frac{m}{n}\right) - f(\sqrt{2})}{\frac{m}{n} - \sqrt{2}} = f'(r) \Longrightarrow \left|\sqrt{2} - \frac{m}{n}\right| = \frac{|m^2 - 2n^2|}{2|r|n^2}. $ The worst possible $ f(n) $ is given by $ f(1) = \sqrt{2} - 1 $ which means that $ |r| \le \sqrt{2} - 1. $ This means that $ \left|\sqrt{2} - \frac{m}{n}\right| > \frac{|m^2 - 2n^2|}{n^2} $ for all rational appriximations $ \frac{m}{n}. $ Now consider the sequence $ \frac{m_i}{n_i} $ that we care about in the problem. By the result in the last paragraph it is clear that we need $ |m_i^2 - 2n_i^2| < C $ which means that $ |m_i^2 - 2n_i^2| \in \{1, 2, \dots, \left\lfloor{C}\right\rfloor\} $ for all terms in the sequence. Now, by a well-known result of Pell Equations, since the "smallest" positive integral solution to $ |x^2 - 2y^2| = n $ for any positive integer $ n $ is given by $ (x, y) = (1, 1) $ when $ n = 1 $ and since the "smallest" unit in $ \mathbb{Z}[\sqrt{2}] $ is $ 3 + 2\sqrt{2} $ we have that for any integer $ n, $ the $ k $th smallest $ y $ in a positive integral solution to $ x^2 - 2y^2 = n $ for any positive integer $ n $ is given by $ \frac{(1+ \sqrt{2})(3 + 2\sqrt{2})^{k - 1} - (1 - \sqrt{2})(3 - 2\sqrt{2})^{k - 1}}{2\sqrt{2}} > 3^{k - 1}. $ This means that we can take $ q = \sqrt[C]{3} $ and so we are done.