I thought more about the last question I added into the addendum of the Numberphile, Graph theory and Mathematica post
It can be succinctly stated as:
\((\forall m\in\mathbb{Z}, m\ge 19) (\exists p,q\in\mathbb{Z}, 1\le p,q<m, p\ne q)\) such that \(\sqrt{p+m}\in\mathbb{Z}\) and \(\sqrt{q+m}\in\mathbb{Z}\).
In words:
For all integers m, greater than 19, there are two other distinct positive integers less than m such that the sum of each with m, when square rooted is an integer.
What is the shortest proof you can find for this statement?
I’ll give it a shot:
To cheat a bit and simplify the argument, assume that we have verified the cases up to and including \(m=23\). By direct calculation
\[\sqrt{m}(\sqrt{2} -1) > 2.02, \hspace{2mm} \forall m > 23\]
(this is true for \(m = 24\) and so true for all \(m > 24\)). So the interval \([\sqrt{m}, \sqrt{2m}]\) is of length >2, which means that that it contains two distinct natural numbers \(a,b\). Now:
\(\sqrt{m} < a,b < \sqrt{2m}\)
\(\implies m < a^2, b^2 < 2m\)
\(\implies 0 < p, q < m\)
where \(p = a^2 - m\), \(q = b^2 - m\). Then \(p\) and \(q\) satisfy the requirements of the question.
Lovely
So, the next question is, what other sufficient conditions for non-traceability might exist?