Two integers $n, k$ satisfies $n \ge 2$ and $k \ge \frac{5}{2}n-1$. Prove that whichever $k$ lattice points with $x$ and $y$ coordinate no less than $1$ and no more than $n$ we pick, there must be a circle passing through at least four of these points.
Problem
Source: 2016 Final Korean Mathematical Olympiad P2
Tags: analytic geometry, combinatorics
rkm0959
19.03.2016 15:10
So I tried to use "don't make a rectangle" argument with some sets and stuff. I'm a noob at combo lol. Wrote down a double counting bound of $O(n\sqrt{n})$ then wrote some ramblings Here's a solution on the local forum.
Lemma. Let there be $T$ points on a line.
Now take all pairs of two points and draw the perpendicular bisectors.
There must be at least $2T-3$ different perpendicular bisectors.
Proof of Lemma. Let that line be the $x$-axis and let the $x$ values be $a_1, \cdot a_T$.
WLOG, $a_1 < a_2 < \cdots <a_T$. Now we have $$a_1+a_2 < a_1+a_3< \cdots <a_1+a_T < a_2 + a_T < \cdots a_{T-1}+a_T$$which gives us $2T-3$ perpendicular bisectors as required.
Now let the number of points on the line $y=i$ be $d_i$.
Let the number of different perpendicular bisectors of the points on the line $y=i$ be $x_i$.
Now $\sum_{i=1}^n x_i \ge \sum_{i=1}^n (2d_i-3) = 2k-3n \ge 2n-2$.
However, the number of possible perpendicular bisectors are $2n-3$.
(There are $x=\frac{3}{2}$ to $x=\frac{2n-1}{2}$, so there are $2n-1-3+1=2n-3$)
Therefore, there are two points on $y=i$, two points on $y=j$ such that the perpendicular bisector of the two points on $y=i$ is equal to the perpendicular bisector of the two points on $y=j$.
This makes a isosceles trapezoid, which is indeed cyclic. GG. $\blacksquare$
Darn I should've thought of that when isosceles trapezoid came across my mind...
fattypiggy123
19.03.2016 15:19
Reminds me of this question. In both of them, you have to consider a very specific type of quadrilateral that meets the required property which makes it easy to count.
buzzychaoz
20.03.2016 10:34
Although there is no solution yet, would like to point out this is essentially the same question.
IsoLyS
20.03.2016 10:44
@above, it's not exactly same question, since the link also asks for y-axis too.
ABCDE
20.03.2016 11:36
Given a horizontal line of lattice points, define the number of values of that line to be the sums of pairs x coordinates of points in that row. Clearly, if we have $a$ points in a row $(x_1,b),(x_2,b),\ldots,(x_a,b)$ then we have at least $2a-3$ distinct values with $x_1+x_2,x_1+x_3,\ldots,x_1+x_a,x_2+x_a,\ldots,x_{a-1}+x_a$. Let $v_i$ be the number of lattice points chosen on the line $y=i$. We have that $v_1+v_2+\ldots+v_n\geq\frac{5}{2}n-1$. The sum of the number of values of every row is thus $2v_1-3+2v_2-3+\ldots+2v_n-3\geq2n-2$. There are only $2n-3$ possible values from $1+2=3$ to $n-1+n=2n-1$, so by Pigeonhole two different rows must contain the same value. But then the corresponding points form an isosceles trapezoid which is cyclic as desired.
YanYau
01.03.2017 08:34
rkm0959 wrote: Lemma. Let there be $T$ points on a line. Now take all pairs of two points and draw the perpendicular bisectors. There must be at least $2T-3$ different perpendicular bisectors. Proof of Lemma. Let that line be the $x$-axis and let the $x$ values be $a_1, \cdot a_T$. WLOG, $a_1 < a_2 < \cdots <a_T$. Now we have $$a_1+a_2 < a_1+a_3< \cdots <a_1+a_T < a_2 + a_T < \cdots a_{T-1}+a_T$$which gives us $2T-3$ perpendicular bisectors as required. Now let the number of points on the line $y=i$ be $d_i$. Let the number of different perpendicular bisectors of the points on the line $y=i$ be $x_i$. Now $\sum_{i=1}^n x_i \ge \sum_{i=1}^n (2d_i-3) = 2k-3n \ge 2n-2$. However, the number of possible perpendicular bisectors are $2n-3$. (There are $x=\frac{3}{2}$ to $x=\frac{2n-1}{2}$, so there are $2n-1-3+1=2n-3$) Therefore, there are two points on $y=i$, two points on $y=j$ such that the perpendicular bisector of the two points on $y=i$ is equal to the perpendicular bisector of the two points on $y=j$. This makes a isosceles trapezoid, which is indeed cyclic. GG. $\blacksquare$ If there is only one point on the line $y=i$ then $x_i$ evaluates to negative 1? Also, wouldn't there only be a pair of common perpendicular bisectors when $\sum_{i=1}^n x_i>2n+3$? Right now $2n-2<2n-3$ Maybe I am missing something... but I don't think that solution works? Also is there another solution?
pandadude
07.08.2018 01:19
Wow nice problem! I thought of isosceles trapezoids and no 2 perpendicular bisectors can be the same very quickly but then I wasted a bunch of time trying to come up with bounds for the bisectors. Turns out we only need to consider vertical bisectors! If there are k guys in row I, then we have at least 2k-3 vertical bisectors. We have 2n-3 vertical bisectors total. Summing over all the rows, we get at least 2n-2 bisectors, contradiction. Also is 4 collinear points considered a cyclic quad?
yayups
18.05.2020 07:26
Note that if there are $A,B,C,D$ such that $\{A,B\}$ and $\{C,D\}$ are in the same column, and the midpoint of $AB$ and $CD$ are aligned horizontally, then we have an isosceles trapezoid. However, $a$ points in a column generate at least $2a-3$ unique midpoints, so if there is no isosceles trapezoid, then there are at least $2k-3n\ge 2n-2$ distinct midpoints among elements of the set $\{1,2,\ldots,n\}$, which is easily seen to be false, so we're done.
khina
12.08.2020 21:50
pandadude wrote: Also is 4 collinear points considered a cyclic quad? LOL anyways i think the idea is quite natural: basically you want an easy way to characterize cyclic quads, and sharing a perpendicular bisector works. A similar but easier problem is https://artofproblemsolving.com/community/c6h1203226p5926022.
pandadude
17.11.2020 01:24
pandadude wrote: Also is 4 collinear points considered a cyclic quad? Is some maths passionate answer pls? I struggling 2 years.