Given a $k^2$-membered set $S$ of points with coordinates $(x,y)\in \{ 1,2,...,k \}$, prove that some $4$ points in $S'$ lie on a circle. We are given a $k^2$-membered set $S$ of points on a plane. The points' coordinates are integers between $1$ and $k$. We then construct another set $S'$ which contains at least $\frac{5}{2} k-1$ points from S. We should prove that there are always at least $4$ points in $S'$ that lie on a common circle.
The situation amounts to a $k$ by $k$ square with an integer grid, the members of $S$ being all the vertices of the grid. A certain portion of the points, $k^{2}-\frac{5}{2}k+1$ of them, is then removed. For $4$ points to be on a circle, it is sufficient that they lie in the vertices of an isosceles trapezium. It is thus sufficient to prove that taking away $k^{2}-\frac{5}{2}k+1$ points is never enough to eliminate all possible sub-sections that form an isosceles trapezium from the square grid.
This problem is rather interesting because the visually rephrased statement seems very intuitive but I am not sure how to proceed to rigorously prove this, especially concerning the specific quanitity $k^{2}-\frac{5}{2}n+1$.
I'd be grateful for any help.


For 4 points to be on a circle, they need to lie in the vertices of a sub-square.

This is not true. Consider the circle through (2, 1), (1, 2) and (1, 3). It will also pass through (2, 4), by symmetry. In fact, a sufficient (but I'm not sure if  necessary) condition is that the points are vertices of an isosceles parallelogram.
