Prove that a counterexample exists without knowing one I strive to find a statement $S(n)$ with $n \in N$ that can be proven to be not generally true despite the fact that noone knows a counterexample, i.e. it holds true for all $n$ ever tested so far. Any help?

If we require that $S(n)$ must be decidable by a known algorithm, then how about:

$S(n)$ iff either there is a comparison-based sorting strategy for $16$ elements that uses at most $n-1$ comparisons, or every comparison-based sorting strategy for $16$ elements uses at least $n+1$ comparisons in the worst case.

This can be determined simply by by enumerating strategies, and clearly there is exactly one counterexample, but it is not known what it is.
In fact it is known that the counterexample is either 45 or 46.
