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.

• Your amended statement is still incorrect. These four points are on the circle with radius 5 centered at (6,6), but the quadrilateral they define has no parallel sides: (3,10), (9,10), (10,9), (2, 3). May 16, 2021 at 19:33
• That is very interesting. Is this necessary to consider in the proof? Is it the case that taking away $n^{2}-\frac{5}{2}n+1$ points is sometimes enough to eliminate all isosceles parallelograms but not all the circles? @MikeEranest May 16, 2021 at 19:52
• 1. When you say "isosceles parallelogram," I think you mean "isosceles trapezoid." 2. It is probably the case that $\frac52k-1$ points will always have an isosceles trapezoid, so you do not need to consider examples like in my comment. But I am not sure. May 16, 2021 at 19:58
• Yes, thank you, got the words a little bit mixed up. Not sure about the sufficiency either. An interesting question would be if the grid reduces the cyclic quadrilateral to a specific case at all, I thought it would but I'd lean towards no now. May 16, 2021 at 20:09

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. Then $$(a+b)/2,(a+c)/2,(a+d)/2,(b+d)/2,$$ and $$(c+d)/2$$ are all distinct midpoints in that row.

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.

• Yes thank you for pointing that out! I thought about isosceles parallelogram being a sufficient condition too but for some reason I typed in square anyway. Not sure how much (if at all) that would affect the ballance between $n^{2}$ and $n^{2}-\frac{5}{2}n+1$ and thus the proof though. May 16, 2021 at 18:52