9
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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). $\endgroup$ May 16, 2021 at 19:33
  • $\begingroup$ 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 $\endgroup$
    – wimano
    May 16, 2021 at 19:52
  • 1
    $\begingroup$ 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. $\endgroup$ May 16, 2021 at 19:58
  • $\begingroup$ 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. $\endgroup$
    – wimano
    May 16, 2021 at 20:09

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – wimano
    May 16, 2021 at 18:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .