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.

Question

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.

Answer 1

Let $M$ be the set of points which are the midpoints of $p$ and $q$, where $p$ and $q$ are points in $S'$ with the same $y$-coordinate (so in the same row of $S$). If there are two distinct points of $M$ with the same $x$-coordinate, then there will exist an isosceles trapezoid in $S'$, and therefore four points in $S'$ on a circle.

For each $i\in \{1,\dots,k\}$, let $r_i$ be the number of points in $S'$ whose $y$-coordinate is $i$. I claim there are at least $2r_i-3$ distinct midpoints in $M$ whose $y$-coordinate is $i$. Once the claim is proven, the total number of distinct midpoints in $M$ would be $$ \sum_{i=1}^k (2r_i-3)=2\sum_{i=1}^k r_i-\sum_{i=1}^k3\ge 2(\tfrac52k-1)-3k=2k-2. $$ There are at least $2k-2$ midpoints in $M$, but there are $2k-3$ possible $x$-coordinates for these midpoints (why?). You can then conclude with the pigeonhole principle.

For help proving the claim, here is a hint, behind a spoiler block in case you want to try to solve the problem without it:

Suppose there are four points in a row, whose $x$ coordinates are $\{a,b,c,d\}$, where $a<b<c<d$. Then $(a+b)/2,(a+c)/2,(a+d)/2,(b+d)/2,$ and $(c+d)/2$ are all distinct midpoints in that row.

Answer 2

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.