This was the statement that appeared on the shortlist. The version that I proposed to BMO 2023 had two parts 1) to show that the claim holds for some constant $c<1$; and 2) to show that it holds for $c=3/4$. In fact, the official solution in the shortlist shows that $c=1/(2\ln 2)$ works. It uses a bit (just a bit) of calculus. I don't understand the reason for the change. No trace of calculus is needed to prove $c=3/4$ works. We discussed this problem at the Bulgarian BMO 2024 camp and during the discussion Marin Hristov (@marinchoo) also solved it using an estimate of the partial sum of harmonic series. His solution is easier than mine. It yields $c=1/(2\ln 2)$.

Here is the abovementioned solution: We will prove the statement for $c = \frac{1}{2\log 2}+\epsilon$. Assume that there doesn't exist pairs $(m, n)$ for $m>N$ , such that $|x_m-x_n|\leq\frac{c}{m}$. Then arrange the numbers $x_{N}, x_{N+1}, \ldots, x_{2M}$ (for $M$ sufficiently large) in increasing order on the interval $[0,1]$ and label them as $x_{i_1}<x_{i_2}< \ldots <x_{i_{2M-N+1}}$. Using the inequality $x_{i_{j+1}}-x_{i_j}>\frac{c}{\max(i_{j}, i_{j+1})}$ leads to: \[1\geq x_{i_{2M-N+1}}-x_{i_1} = \sum\limits_{j=1}^{2M-N} x_{i_{j+1}}-x_{i_{j}} > \sum\limits_{j=1}^{2M-N} \frac{c}{\max(i_{j}, i_{j+1})}\]However, each number from $N, N+1, \ldots, 2M$ can appear at most twice among the numbers $\max(i_j, i_{j+1})$, so we have: \[\sum\limits_{j=1}^{2M-N} \frac{c}{\max(i_{j}, i_{j+1})} \geq c\sum\limits_{j = M-N/2}^{2M} \frac{2}{j}=2c(H_{2M}-H_{M-N/2})=2c(\log 2M-\log (M-N/2)+O(1/M))=2\log 2 c + O(1/M)\]which implies the desired $c<\frac{1}{2\log 2} + \epsilon$.

Awesome problem !