NMO Selection Tests for the Junior Balkan Mathematical Olympiad

Among the given $51$ points there cannot exist simultaneously a point with odd coordinates and a point with even coordinates. Indeed, that be the case, let $(2a, 2b)$ and $(2c+1, 2d+1)$ be such points. The square of the distance between them is $(2a - 2c - 1)^2 + (2b - 2d - 1)^2 = M4 + 2$, which is not the square of an integer.

By the same argument as above, if an (even, odd)-coordinate point existed, there cannot exist an (odd, even)-coordinate point.

Let now $k$ be the number of points with coordinates of the same parity, then notice that all distances among them are even integers. So there exist $51 - k$ points with coordinates of different parity, again all distances among them being even integers.

Therefore, at least $\binom{k}{2} + \binom{51-k}{2}$ distances are even numbers (by definition $\binom{n}{k} = 0$ if $k > n$). Since there are $\binom{51}{2}$ distances in all, one has
$$\begin{aligned} \frac{\binom{k}{2} + \binom{51-k}{2}}{\binom{51}{2}} &= \frac{k(k-1) + (51-k)(50-k)}{51 \cdot 50} \\ &= 1 + \frac{k^2 - 51k}{51 \cdot 25} \ge 1 - \frac{51^2}{51 \cdot 25} = 1 - \frac{51}{100} = 49\%. \end{aligned}$$