This problem is proposed by ltf0501and me!

Kamran011 wrote: So this year it's basically GACCCC lol Sadness... Give us NT!

Here is the solution I found while proctoring the exam. I'll use asymptotic notation $O(f)$ and $\Omega(f)$ throughout, which denote $\le C_1f$ and $\ge C_2f$ respectively for absolute constants $C_1,C_2>0$. In what follows, we will assume $n$ to be a sufficiently large positive integer. The main idea is to cover all of the points with a pizza. If the pizza is big, then the points will be far apart. If the pizza is small, we can look at the crust of a slice, which cannot contain that many points by the distance condition. Lemma 1: For all $A>1$, any $1\times A$ rectangle contains $O(A)$ points. Proof: Draw a circle of radius $1/2$ around every point. All of these circles are disjoint by the distance $1$ condition, and they are all contained in the $2\times(A+1)$ rectangle around our original rectangle. It follows that we cannot have more than $\frac{2(A+1)}{\pi/4}=O(A)$ rectangles. Lemma 2: Consider a line $\ell$ and the projections of all points onto this line, which we sort into the order $P_1,P_2,\ldots,P_n$. If $P_kP_{k+1}=\Omega(n^{-1/3})$ for some $1\le k<n$, then we are done. Proof: Take the perpendicular bisector of $P_kP_{k+1}$, and note that the distance from any point in the set to this line is at least the distance of $P_k$ or $P_{k+1}$ to the line, which is $\Omega(n^{-1/3})$. Now, take the circle of minimal radius that contains all of the points. Suppose that this circle has center $O$ and radius $r$. By assumption of minimality, among the $n$ points there either exist three points $A$, $B$, and $C$ which lie on the circle and form an acute triangle or two points $A$ and $B$ which form a diameter of the circle. Otherwise, it is possible to find a smaller circle containing all of the points. In any case, we can find two points $A$ and $B$ on the circle with $AB>r$. If $r\ge n^{2/3}$, then we have that $AB=\Omega(n^{2/3})$. Apply Lemma 2 to line $AB$, noting that we will get $n$ points $P_1,P_2,\ldots,P_n$ on this line in that order with $P_1P_n\ge AB$. There are $n-1$ segments $P_1P_2,P_2P_3,\ldots,P_{n-1}P_n$ in total, so it follows that one of these segments have length at least $\frac{P_1P_n}{n-1}\ge\frac{AB}{n-1}=\Omega(n^{-1/3})$, as desired. If $r\le n^{2/3}$, then consider the point $D$ on segment $OA$ with $AD=1$. Let the perpendicular to $OA$ at $D$ meet the circle again at $E$ and $F$, and let $G$ and $H$ be points such that $\overrightarrow{EH}=\overrightarrow{FG}=\overrightarrow{DA}$. By the Pythagorean theorem, we have that $EF=2\sqrt{r^2-(r-1)^2}=O(\sqrt r)$. Note that $EFGH$ is a $1\times EF$ rectangle, so by Lemma 1 it contains $O(\sqrt r)$ points. Now we apply Lemma 2 to line $AD$. Since all of the points are assumed to lie in the circle, all of the points that project onto segment $AD$ lie in $EFGH$. Let these projected points be $\ldots,Q_0,Q_1,Q_2,\ldots,Q_m=A$ in that order, where $Q_1,\ldots,Q_m$ are the points that project onto segment $AD$. In particular, $m=O(\sqrt r)=O(n^{1/3})$ as the projection preimages of these $m$ points must lie in $EFGH$. We have that $Q_0Q_m\ge AD=1$. Among the $m$ segments $Q_0Q_1,Q_1Q_2,\ldots,Q_{m-1}Q_m$ one of them has length at least $\frac{Q_0Q_m}m\ge\frac1m=\Omega(n^{-1/3})$, as desired.

Also by the way, I would be really interested in any solution that proves the result for some $\alpha$ strictly between $1/2$ and $1/3$.

ABCDE wrote: Here is a sketch of the solution I found while proctoring the exam, will clean up later: ok so the idea is: 1. For reals a,b>1, any a by b rectangle contains O(ab) points, proof by drawing nonintersecting circles of radius 0.5 around each point 2. Consider the smallest circle containing all points, of radius R. If R=Omega(n^(2/3)) then there is some segment among the points that has length Omega(n^(2/3)). Project onto that segment, which gives us n points on a line of length Omega(n^(2/3)), at least one small segment has length Omega(n^(-1/3)) and that perpendicular works. If R=O(n^(2/3)) then take a point P on the circle that is in the set of points. Let the circle have center O and consider the point Q on ray OP with OQ=R-1. Cut the circle along the perpendicular line to OP at Q and look at the slice of the circle that contains P. This slice is contained in a rectangle of sides 1 and O(sqrt(R)) by Pythagorean theorem, so it has O(sqrt(R))<=O(n^(1/3)) points in it. Now project those points onto segment PQ and do the exact same thing in the previous case. I think this solution is much cleaner than mine. Nice one! (I think it is correct but it's almost 3am here so I'll check again tmr morning)

Yo this is crazy. Any solves at competition?

Kamran011 wrote: So this year it's basically GACCCC , sad TBH, as one of the proposer, i have no idea why this problem is G . One possible reason is PSC wanted to have more than 2 combinatorics problems((just kidding lol

v_Enhance wrote: Imagine that the fashion swings the other way. The IMO jury become alarmed at the trend of train-able problems, and in response, the problems become designed specifically to antagonize trained students. The entire Geometry section of the IMO shortlist ceases to exist, because some Asian kid wrote this book that gives you too much of an advantage if you’ve read it, and besides who does geometry after high school anyways? The IMO 2014 used to be notable for having three combinatorics problems, but by 2040 the norm is to have four or five, because everyone knows combinatorics is harder to train for. Gradually, the IMO is redesigned to become an IQ test.

I liked the original wording better lol Anyway, to the proposers, what did you intend the problem to be categorized as?

Imayormaynotknowcalculus wrote: v_Enhance wrote: Imagine that the fashion swings the other way. The IMO jury become alarmed at the trend of train-able problems, and in response, the problems become designed specifically to antagonize trained students. The entire Geometry section of the IMO shortlist ceases to exist, because some Asian kid wrote this book that gives you too much of an advantage if you’ve read it, and besides who does geometry after high school anyways? The IMO 2014 used to be notable for having three combinatorics problems, but by 2040 the norm is to have four or five, because everyone knows combinatorics is harder to train for. Gradually, the IMO is redesigned to become an IQ test. I spent 2/3 of my olympiad journey studying for geometry. The one year I get into the IMO, there is not a single >IMO 1 level geometry problem to be found....

Imayormaynotknowcalculus wrote: v_Enhance wrote: Imagine that the fashion swings the other way. The IMO jury become alarmed at the trend of train-able problems, and in response, the problems become designed specifically to antagonize trained students. The entire Geometry section of the IMO shortlist ceases to exist, because some Asian kid wrote this book that gives you too much of an advantage if you’ve read it, and besides who does geometry after high school anyways? The IMO 2014 used to be notable for having three combinatorics problems, but by 2040 the norm is to have four or five, because everyone knows combinatorics is harder to train for. Gradually, the IMO is redesigned to become an IQ test. The geometry part is kind of exaggerated. Last year a medium and a hard was geo, so sometimes there is geometry, sometimes there isn't. What's sad is that there is almost no serious NT/Algebra anymore.

rmtf1111 wrote: Imayormaynotknowcalculus wrote: v_Enhance wrote: Imagine that the fashion swings the other way. The IMO jury become alarmed at the trend of train-able problems, and in response, the problems become designed specifically to antagonize trained students. The entire Geometry section of the IMO shortlist ceases to exist, because some Asian kid wrote this book that gives you too much of an advantage if you’ve read it, and besides who does geometry after high school anyways? The IMO 2014 used to be notable for having three combinatorics problems, but by 2040 the norm is to have four or five, because everyone knows combinatorics is harder to train for. Gradually, the IMO is redesigned to become an IQ test. The geometry part is kind of exaggerated. Last year a medium and a hard was geo, so sometimes there is geometry, sometimes there isn't. What's sad is that there is almost no serious NT/Algebra anymore. This is so true. People here complaining about Geometry... look at Algebra. The last P3 or P6 in Algebra was 2011 like wtf... Why df did this IMO have 4 problems of C???!!??

Is $\alpha=1/3$ known to be minimal?

pieater314159 wrote: Is $\alpha=1/3$ known to be minimal? Yes. See my long comments above.

khina wrote: I spent 2/3 of my olympiad journey studying for geometry. The one year I get into the IMO, there is not a single >IMO 1 level geometry problem to be found.... “Its the not the Destination, It's the journey.” ― Ralph Waldo Emerson, Self-Reliance Congratulations on your long and fruitful journey up to the IMO.

Quite a bit off, but here goes a solution for $\alpha =1$ Choose an arbitrary $xy$ plane and project the points to both $x$ and $y$ axis. Denote the distances between consecutive projections on the $x$ axis as $x_1, x_2, ..., x_{n-1}$, and do the same for the $y$ plane. Let $d$ be the maximum of $x_1, x_2, ..., x_{n-1}, y_1, y_2, ..., y_{n-1}$. Denote by $\sum k$ the distance on $y$ axis of the projections of two points who's projections on the $x$ axis are the $k-$th pair of projections on it. I sincerely apologize for this wording. By the distance condition, we have $x_i^2+(\sum i)^2 \geq 1 \implies \sum_{i=1}^{n-1}(x_i^2+(\sum i)^2) \geq n-1$. Obviously $\sum i \leq y_1+...+y_{n-1}\leq (n-1)d \implies (\sum i)^2 \leq (n-1)^2d^2$. From this and the first inequality we get $(n-1)^3d^2+(n-1)d^2 \geq \sum_{i=1}^{n-1}(x_i^2+(\sum i)^2) \geq n-1$. It follows that $d^2 \geq \frac{1}{(n-1)^2+1}>\frac{1}{n^2} \implies d\geq \frac{1}{n}$. Now by drawing a perpendicular bisector of the segment of length $d$, the distance between it and any point in $\mathcal S$ is at least $0.5n^{-1} \square$

People that claim that 5th problem was C need to think more before posting anything online. It was 90% NT and 10% A

@above so why posting this in problem 6?! (also I disagree)

@above It indeed felt kind of off-topic, but 3 people in this thread said that this IMO featured 4 combinatorics, so I wanted to reply to them. In order for this to not be that off-topic I want to say that I think this problem is beautiful. One very interesting remark that marking scheme mentions is that if you want to consider only partitions that separate S into two parts containing at least $\frac{n}{100}$ points then you can't do better than $\alpha=\frac{1}{2}$, hence each correct solution must focus on parts close to boundary.

Double post By taking a random set of $n $ points in a disk of area $50n,$ say, and removing points that are closer than distance $1$ to another point $, $ we obtain a set where the best separating line is at distance of order $\frac {n^{-\tfrac 13}}{\ln (n)}$ from the closest point.

USJL wrote: This problem is proposed by ltf0501and me!

Really nice solution!! Although shouldn’t one say that D gets devided into at most n-1 Intervals with the projection (two points can map to same point) The argument still holds identically from there

yoyoflo wrote: USJL wrote: This problem is proposed by ltf0501and me!

Really nice solution!! Although shouldn’t one say that D gets devided into at most n-1 Intervals with the projection (two points can map to same point) The argument still holds identically from there Ah that's a really minor point. I guess it can be easily fixed by allowing intervals to have length zero.

and it still amazes me to see such simple tricks solve this hard problem. . here is mine (maybe similar to others...) . . let $d$ be the maximum number that we can achieve for the seperating line. . we need to prove $d^3 \ge \frac{c}{N}$ for some $c$. . let in the set of $N$ points , the maximal distance be $D_N$ for points $X,Y$ now we take the line $XY$ and project the other points on it. clearly it will be a closed segment with points $X,Y$ at it ends. so it has at most $N-1$ peices. so one of those segment pieces has at least $\frac{D_N}{N-1}$ lenght taking the prependicular bisector of that segmest gives $d \ge \frac{D_N}{2N-2}$ so we just need to prove $\frac{d^2 D_N}{2N-2} \ge \frac{c}{N}$ so we need (these $c$ that i wrote are just some constants we really dont care what they are) $d \ge c \sqrt{ \frac{1}{D_N}}$ . now take the smallest circle possible such that at has all the $N$ points inside of it. let it have radios $r$ we have $r \le D_N$ so we prove $d \ge c \sqrt{\frac{1}{r}}$ instead. . since that circle is the smallet one possible it has one point of the $N$ point on its bondrary. lets name it $A$ let the circle have the center $O$ take point $M$ on the segment $OA$ such that $OM=r- \frac 12$ . the line prependicular to $AO$ that passes through $M$ cut the circle at $B,C$. . now we only need to prove in the area bounded by segment $BC$ and arc $BAC$ there are atmost $c \sqrt{r}$ points of $N$ points. bc if we have that there are atmost $c \sqrt{r}$ project these points on the segment $MA$ so we have atmost $c \sqrt{r} +1$ pieces on the segment $MA$ so one of them has the lenght of atleast $\frac{\frac{1}{2}}{c \sqrt{r}}$. taking the prependicular bisector of this gives $d \ge \frac{\frac{\frac{1}{2}}{c \sqrt{r}}}{2}$ which is exactly what we wanted. . so it is left to prove the points in the area bounded by $BC$ and arc $BAC$ are atmost $c \sqrt{r}$ we have $OB^2=BM^2+MO^2=r^2=(r-\frac 12)^2+BM^2$ so $BM= \sqrt{r-\frac 14}$ also $BM^2+MA^2=AB^2=r$ so $AB=\sqrt{r}=AC$. lets have there are $P$ points in that area. now we create $P$ circles with theire centers being one of the $P$ points and having the radious of $\frac 12$ since the circles are disjoint they cover an area of at least $\frac{3p}{4}$ now take the region named $W$ such that the distance of any point in $W$ with the bounded region of segment $BC$ and arc $BAC$ is $\frac 12$. some compiutations show that the area of $W$ contains all of the sircles so $Area_W \ge \frac{3p}{4}$ but also there is a $c$ such that $c \sqrt{r} \ge Area_W$ (this is not hard to prove , but hard to say without a good diagram) so we are done. . sorry for the minor spelling misstakes if there are any.

I put here the essential part of the solution. The proofs of some claims are omitted. One may find them, along with the motivation and other comments, in my blog post. The idea. We fix some $ \varepsilon<n^{-1/3}$, which exact value will be determined later. Let us draw a circle with radius $ \varepsilon$ around each point in $ S$ and let the polygon $ P$ be the convex hull of $ S$. We want to show there is a line $ \ell$ that intersects $ P$ and does not meet any circle. Denote by $ p$ the perimeter of the polygon $ P$. We'll consider two cases. The first case is when the interior of $ P$ is "too densely" packed with circles of radius $ \varepsilon$ (thou, the distance between any two of their centers is at least $ 1$). In this case we do not allow the line $ \ell$ to penetrate deeply into the interior of $ P$, because there are "too many" circles inside it and it would meet someone. We rotate the line $ \ell$ and allow it to cut off only a "small piece" of the the polygon $ P$. The second case is when the perimeter of $ P$ is "too large", i.e. the small circles of radius $ \varepsilon$ are not tightly packed inside $ P$. It's dealt in a routine manner. We project $ P$ on an appropriate line $ \ell'$ (the line on which $ P$ has the longest projection) and establish that some line $ \ell$ that is perpendicular to $ \ell'$ does not meet any circle. The details. Let the polygon $ P$ be the convex hull of $ S$. Denote by $ p$ the perimeter of $ P$. Fix some $ \varepsilon<n^{-1/3}$, which exact value will be determined later. Suppose some exterior angle $ \alpha$ of the polygon $ P$ is greater than $ n^{-1/3}.$ Then we can chose a line $ \ell$ at distance $ \varepsilon:=n^{-1/3}$ from that vertex that cuts off a very small corner from the polygon - see at figure 1. Let $ A'\in AB, C'\in BC, |A'B|=|C'B|$ and $ A'C' $ touches the circle with center $ B$ and radius $ \varepsilon.$ A straightforward calculation yields $ \displaystyle |A'B|=\frac{\varepsilon}{\sin{\frac{\alpha}{2}}}$ or $ |A'B|\le \pi/4$ which means $ \ell$ cannot meet any other circle (for sufficiently large n), and we are done. Thus, hereafter are under the following assumption. Assumption 1: Every exterior angle of $ P$ is at most $ n^{-1/3}.$ Further, we consider two cases, and start with the harder one. First case. $ p \le n^{2/3}$. According to the assumption, every exterior angle of $ P$ is less than $ p^{-1/2}.$ For any $ z\in P$ (further by $ P$ we mean the contour of the polygon) let $ z'\in P$ be the point at distance $ \frac{1}{100}p^{1/2}$ measured clockwise, along the polygon, i.e. the broken line between $ z$ and $ z'$ has length $ \frac{1}{100}p^{1/2}.$ Let $ h>0$ be the maximum distance such that translating the line $ zz'$ at distance $ h$ toward the direction outside the polygon, it still meets $ P.$ Thus, $ h$ depends on $ z\in P.$ We can parameterize $ z$ as being at distance $ x, 0\le x<p$ measured clockwise alongside the polygon, starting from some fixed point $ z_0\in P.$ Each such $ 0\le x<p$ corresponds to a point $ z\in P$ and $ h=h(x).$ Consider the region $ D\subset \mathbb{R}^2$ defined as $$ \displaystyle D:=\{(x,t)\in \mathbb{R}^2 : 0\le x<p, 0\le t\le h(x)\}.$$Each point $ (x,t)\in D$ corresponds to a line $ \ell(x,t)$ that intersects $ P,$ namely, we take $ zz'$ that corresponds to $ x$ and translate it at distance $ t$ outward $ P$ (dotted lines in the fig. 2 below). Denote by $ L$ the family of all those lines, i.e. $$ \displaystyle L:=\left\{ \ell(x,t) : (x,t)\in D\right\}$$We claim there is a line $ \ell\in L$ that does not meet any circle. In order to prove this, we establish three auxiliary facts. Claim 1. The area $ m(D)$ of $ D$ is at least $ C_1\cdot p$ for some absolute constant $ C_1.$ Claim 2. For any $ s\in S$ let $ B(s,\varepsilon)$ be the circle with center $ s$ and radius $ \varepsilon.$ Let $ D_s$ be the subset of $ D$ that corresponds to the lines intersecting $ B(s,\varepsilon).$ Then $$ \displaystyle m(D_s)\leq C_2\sqrt{p}\cdot \varepsilon$$where $ C_2$ is an absolute constant, and $ m(X)$ means the area of $ X.$ Claim 3. The lines in $ L$ intersect at most $ C_3\cdot p$ circles for some absolute constant $ C_3.$ Proofs the these 3 claims are in the given link at the beginning. Let $ S'\subset S$ be the set of those points $ s\in S$ for which some line in $ L$ intersects $ B(s,\varepsilon).$ We have $$ \displaystyle m\big(\{(x,t)\in D: \ell(x,t)\text{ intersects a circle}\}\big) \le \sum_{s\in S'} m(D_s).$$Using claims 2 and 3, we get $$ \displaystyle \sum_{s\in S'} m(D_s)\le C_3\cdot C_2\cdot p\cdot \sqrt{p}\cdot \varepsilon. $$Now, we choose $ \displaystyle \varepsilon:=\frac{C_1}{2C_2\cdot C_3}n^{-1/3}.$ Because $ \sqrt{p}n^{-1/3}\le 1$ it yields $$ \displaystyle m\big(\{(x,t)\in D: \ell(x,t)\text{ intersects a circle}\}\big) \le \frac{C_1}{2}\cdot p$$According to claim 1, it holds $ m(D)\ge C_1\cdot p,$ therefore there is a point in $ D$ which does not belong to the set of "bad" points $ \{(x,t)\in D: \ell(x,t)\text{ intersects a circle}\}$ and the result follows. Second case: $ p > n^{2/3}$ (the circles are not "tightly" packed inside $ P$). Pick a line $ \ell'$ such that the projection $ P'$ of $ P$ on $ \ell'$ is the longest possible one. Then $ |P'|\ge C\cdot p$ for some absolute constant $ C$ (in fact $ C=1/\pi$). For each $ s\in S$ construct a circle $ B(s,\varepsilon)$ with center $ s$ and radius $ \varepsilon:= \frac{C}{4}n^{-1/3}.$ The projection of $ B(s,\varepsilon)$ on the segment $ P'$ is a segment with length at most $ 2\varepsilon.$ The sum of those projections is at most $ \displaystyle 2n\varepsilon=\frac{C}{2}n^{2/3}<\frac{C}{2}p<|P'|$. Therefore, there is a point $ X\in P'$ such that the line through $ X$ and perpendicular to $ \ell'$ does not meet any circle $ B(s,\varepsilon).$

Let \(D\) be the maximum distance between two points in \(\mathcal S\). Let these two points be \(A\) and \(B\), and let \(\ell\) be the line \(AB\). If we consider the projections of the points in \(\mathcal S\) onto \(\ell\), let \(\delta\) be the maximum distance between two adjacent projections. I contend \(\delta\ge O(n^{-1/3})\). It will then suffice to take the perpendicular bisector of these two projections. Case 1: \(D\ge O(n^{2/3})\). There are \(n\) projections on a segment of length \(D\ge O(n^{2/3})\), so some two adjacent projections are \[\delta\ge\frac Dn\ge\frac{O(n^{2/3})}n=O(n^{-1/3})\]apart, as desired. Case 2: \(D\le O(n^{2/3})\). Consider the disks \(\Gamma_A\) and \(\Gamma_B\) centered at \(A\) and \(B\) with radii \(D\). Then all the points in \(\mathcal S\) lie in \(\Gamma_A\cap\Gamma_B\). Consider a chord \(XY\) of \(\Gamma_B\) a distance of \(1/2\) away from \(A\), and consider the segment \(\mathcal R\) of \(\Gamma_B\) bounded by \(\overline{XY}\) and containing \(A\). [asy][asy] size(10cm); defaultpen(fontsize(10pt)); pair A,B,X,Y; real theta=75,t=.2; A=(0,0); B=(1,0); X=(t,sqrt(1-(1-t)^2)); Y=reflect(A,B)*X; fill(X--arc(B,X,Y)--Y--cycle,cyan+white+white+white); void f(pair P) { dot(P,heavygreen); draw(P--foot(P,A,B),heavygreen); } f((.05,-.2)); f((.1,.3)); f((.15,.1)); f((.25,-.1)); f((.34,-.5)); f((.43,.4)); f((.57,-.3)); f((.66,.2)); f((.75,.4)); f((.85,-.2)); f((.95,.1)); draw(A--B,blue+linewidth(1)); draw(X--Y,lightblue+dashed); draw(arc(A,1,-theta,theta),lightblue); draw(arc(B,1,180-theta,180+theta),lightblue); draw(brace(A,B)); draw(brace(foot(X,A,B),A)); draw(brace((.57,0),(.43,0))); label("\tiny\(D\)",(A+B)/2+(0,.17)); label("\tiny\(\frac12\)",(foot(X,A,B)+A)/2-(0,.07)); label("\tiny\(\delta\)",((.43,0)+(.57,0))/2-(0,.05)); dot("\(A\)",A,W); dot("\(B\)",B,E); dot("\(X\)",X,NW); dot("\(Y\)",Y,SW); [/asy][/asy] Claim: \(\mathcal R\) contains at most \(O(\sqrt D)\) points. Proof. The Pythagorean theorem gives \(XY=O(\sqrt D)\). Since points in \(\mathcal R\) are at least 1 apart and the width of \(\mathcal R\) is \(\frac12\), their projections onto \(XY\) must be at least \(\frac{\sqrt3}2\) apart, implying there are at most \(O(\sqrt D)\) points in \(\mathcal R\). \(\blacksquare\) The projections of the points in \(\mathcal R\) onto \(\ell\) cover a segment of length at most \(\frac12\), so some two adjacent projections are \[\delta\ge\frac{1/2}{\sqrt D}\ge\frac1{O(n^{2/3})}=O(n^{-1/3})\]apart as desired.

Great! The same idea as in #68 but with much simpler implementation. The first case is when the points are "too densely" packed, i.e. when the maximum distance (or the perimeter of the convex hull) is less than $n^{2/3}.$ In this case we look for a line $ \ell$ that just chips off a small piece of the convex hull. (because there are "too many" points inside the convex hull and $\ell$ could have passed near some of them if it were allowed to penetrate deeper). This is the most complicated case. The second case is when the points are not tightly packed, they are on average too far away from one another, i.e. the maximum distance (or the perimeter of the convex hull) is greater than $n^{2/3}$. In this case we project $ P$ on an appropriate line $\ell' $ (the line on which $ P$ has the longest projection) and establish that there exists a line $ \ell$ that is perpendicular to $ \ell'$ and does not pass too close to any point. I struggled how to implement this idea, because this can be very easily done in case the convex hull has a regular shape, for example when it's close to a circle. So, in #68 the more complicated case was done via some averaging arguments, but it became comparatively lengthy solution, and the main idea was obscured by the technical details. Your approach is much easier and enjoyable! Just a small note: Do not write \(D\ge O(n^{2/3})\) or \(D\le O(n^{2/3})\), especially the former one. By definition $D=O(\cdot)$ just means $D\le c (\cdots)$ for some constant $c>0$. If you want to express $D\ge c(\cdots)$, there is another notation $D=\Omega(\cdot)$ But it's enough simply to consider the cases $D\le n^{2/3}$ and $D>n^{2/3}$ and adjust the constant inside these cases. EDIT. One may ask: where does the threshold $n^{2/3}$ come from? The motivation behind it is natural. The most common approach to this problem, in my opinion, is to try to project the points on a line $\ell$ on which the convex hull has the longest projection, say $D$. It is easily calculated that we would get the required result only if $D\ge cn^{2/3}$ where $c$ can be any constant (but fixed, not depending on $n$). So, obviously when $D<n^{2/3}$ some other approach has to be found.

From AMSP Combinatorics 3: Pick two points $A, B$ in $\mathcal S$ such that $AB$ is maximal. There are essentially two cases. The first case is when the projections of $\mathcal S$ onto $\overline{AB}$ create two consecutive projections at a distance of $d \geq n^{-\frac 13}$. In this case, taking the perpendicular bisector of these two projections, say $P'$ and $Q'$, works (take $c=\frac 12$ and any other point has greater distance to $\ell$ than either $P$ or $Q$.) Note that the projections are strictly contained inside segment $\overline{AB}$ due to maximality. Now, suppose that all consecutive projections have length less than $n^{-\frac 13} = d$. Obviously, all the points in $\mathcal S$ must lie inside the circle centered at $B$ with radius $nd$. Consider a region $\mathcal C$ bounded by a perpendicular to $\overline{AB}$ a fixed distance, say, $\frac 12$, and the arc formed by the intersection points of the line with the circle (say $C$ and $D$.) Project the points on $\mathcal S \cap \mathcal C$ onto $\overline{AE}$, where $E$ is the desired intersection. Running a similar argument, $$\frac 12 = AE \leq d |\mathcal C \cap \mathcal S|,$$which implies $$|\mathcal S \cap \mathcal C| \geq \frac 1{2d}.$$ Claim. There are at most $c(M+1)$ points of $\mathcal S$ inside any $1 \times M$ rectangle, where $c$ is a fixed constant. Proof. Draw circles of radius $\frac 12$ around every point in $\mathcal S$; as all the disks are contained within a larger rectangle with area $(1+1)(1+M) = 2(1+M)$, we have the bound $$[\text{Rectangle}] \geq \sum [\mathcal D_i],$$so the intersection has at most $\frac 8{\pi} (1+M)$ points after the computation. $\blacksquare$ Utilizing the claim, consider the rectangle with width 1 and length equal tp $$CD=2\sqrt{BC^2-BE^2} = 2\sqrt{AB-\frac 14} < 2\sqrt{AB} \leq 2\sqrt{nd}.$$Combining the bounds, $$\frac 1{2d} \leq |\mathcal C \cap \mathcal S| \leq \frac 8{\pi}(1+2\sqrt{nd}).$$Scaling $d$ down by some large constant (say, $10^6$), we achieve a contradiction.

Take the longest side length GI and draw circles centered at each other passing through the other; by the longest length this means all points are contained inside, and WLOG move them to one side of GI by reflecting (since this obviously nonincreases such c). Take the projections of the points onto GI as shown in diagram, and call them of the form $B_k$, while the original is of the form $A_k$; it's obvious that if between two consecutive points (of the form $B_i$) the distance is at least $2cn^{-\frac13}$, taking the perp. bisector finishes, so assume FTSOC not, that is, $GI\le 2cn^{\frac23}$ (otherwise by pigeonhole on n segments one of them exceeds). Henceforth this will not be specified, but we are only looking at $A_i,B_i\forall 1\le i\le\lceil n^{\frac13}\rceil$, where $B_1=G$, and let $A_1B_1<A_2B_2<...<A_kB_k$, where we henceforth refer to $k=\lceil n^{\frac13}\rceil$. Now since $A_iA_j\ge1$ and $B_iB_j\le2cn^{-\frac13}<2c$, $$|A_iB_i-A_jB_j|>1-2c\implies A_kB_k>(1-2c)A_{k-1}B_{k-1}>...>(1-2c)n^{\frac13}A_1B_1\ge(1-2c)n^{\frac13}\quad(1).$$On the other hand, $$GI-GB_k=IB_k=\sqrt{IA_k^2-A_kB_k^2}\le\sqrt{GI^2-A_kB_k^2}\implies2c\ge GB_k\ge GI-\sqrt{GI^2-A_kB_k^2}$$$$=\frac{A_kB_k^2}{GI+\sqrt{GI^2-A_kB_k^2}}>\frac{A_kB_k^2}{2GI}\stackrel{(1)}{>}\frac{(1-2c)^2n^{\frac23}}{2GI}\implies2cn^{\frac23}\ge GI\ge n^{\frac23}\frac{(1-2c)^2}{4c},$$which doesn't hold for small c, contradiction!

signifance wrote: ...it's obvious that if between two consecutive points (of the form $B_i$) the distance is at least $2cn^{-\frac13}$, taking the perp. bisector finishes, so assume FTSOC not, that is, $GI\le 2cn^{\frac23}$ (otherwise by pigeonhole on n segments one of them exceeds). Henceforth this will not be specified, but we are only looking at $A_i,B_i\forall 1\le i\le\lceil n^{\frac13}\rceil$, where $B_1=G$, and let $A_1B_1<A_2B_2<...<A_kB_k$, where we henceforth refer to $k=\lceil n^{\frac13}\rceil$. Now since $A_iA_j\ge1$ and $B_iB_j\le2cn^{-\frac13}<2c$, $$|A_iB_i-A_jB_j|>1-2c\implies A_kB_k>(1-2c)A_{k-1}B_{k-1}>...>(1-2c)n^{\frac13}A_1B_1\ge(1-2c)n^{\frac13}\quad(1).$$On the other hand, $$GI-GB_k=IB_k=\sqrt{IA_k^2-A_kB_k^2}\le\sqrt{GI^2-A_kB_k^2}\implies2c\ge GB_k\ge GI-\sqrt{GI^2-A_kB_k^2}=\frac{A_kB_k^2}{GI-\sqrt{GI^2-A_kB_k^2}}>\frac{A_kB_k^2}{2GI}\stackrel{(1)}{>}\frac{(1-2c)^2n^{\frac23}}{2GI}\implies2cn^{\frac23}\ge GI\ge n^{\frac23}\frac{(1-2c)^2}{4c},$$which doesn't hold for small c, contradiction! Why $A_iB_i$ have to be in increasing order? If you arrange them like that then the distance between $B_i$ and $B_{i+1}$ may be large. And besides, how did you get (1)? It cannot be done by only projecting the points on a line and then by some average argument, because you can arrange the points in a square $n^{2/3}\times n^{2/3}$ so that their projections on the side of the square are spaced more than $cn^{-1/3}$ from one another. So here comes the second and the crucial argument ... that if so, then near the last point - in your drawing it's $I$ - the projections are not so dense as in the middle of $GI$. This is the argument in #69. I do not see something like that here. You can also consider some average arguments, but a single direction is not enough, for example as in #68. I mean, I can put these $n$ points in your drawing so that it's ok everywhere but not very near to $I$.

dgrozev wrote:

Hi, thanks for your response. For $A_iB_i$ in increasing order, this is done WLOG. That is, in the diagram, we'd have $F=A_1,K=B_1,D=A_2,P=B_2,...$. As for (1), I'm not sure what part doesn't make sense, but for elaboration, the very first part of the first line follows from triangle inequality. as for "by some average argument", im not sure what you mean, can u provide a diagram of that such square wjhere it's contradiction? since they're projected onto the same line the distance thing still has to be preserved. can u make a diagram for your last part too then? idk why the dense thingy even matters, my argument had nothing to do with that then again, don't get too mad at me because i did not even get a score on JMO/AMO so sorry if im just not understanding, i don't want this to become like that thread with zeta_in_olympiad where he blatantly did not knwo wha'ts going on and people got angry

Take a circle $\Gamma$ of minimal radius containing all of $\mathcal{S}$ and suppose it has radius $r$. Let $P,Q$ be the points in $\mathcal{S}$ such that $PQ$ is maximal, and note that by considering a large circle centered at the midpoint of $\overline{PQ}$ we have $r \leq \sqrt{3}PQ$. If $r \geq n^{2/3}$, we have $PQ=\Omega(n^{2/3})$ as well. By maximality, the projection of every point onto line $\overline{PQ}$ lies on segment $\overline{PQ}$, which has length $\Omega(n^{2/3})$. Thus by expectation there exist some two adjacent projections $B,C$ such that $BC=\Omega(n^{-1/3})$, and taking $\ell$ to be the perpendicular bisector of $\overline{BC}$ works, since it separates the segment joining the preimages of $B$ and $C$ but has distance at least $\tfrac{BC}{2}=\Omega(n^{-1/3})$ from every point in $\mathcal{S}$. If $r \leq n^{2/3}$, then note that by maximality there exists a point $A \in \mathcal{S}$ on the circumference of $\Gamma$. Let points $S,T$ lie on $\Gamma$ such that $AS=AT$ and $d(A,\overline{ST})=1$. Let $M$ be the midpoint of $\overline{ST}$ and $A'$ the $A$-antipode. By power of a point, we have $$MS\cdot MT=MA\cdot MA'=1\cdot (2r-1)=O(n^{2/3}) \implies ST=O(n^{1/3}).$$It is clear that not every point in $\mathcal{S}$ lies in segment $\widehat{SAT}$ of $\Gamma$ (for sufficiently large $n$; small $n$ don't matter), else the circle with diameter $\overline{ST}$ is (much) smaller and still contains everything. Now consider a height-$1$ rectangle $STUV$ such that $A$ is the midpoint of $\overline{UV}$, which has area $ST=O(n^{1/3})$. Note that every point on the same side of $\overline{ST}$ as $A$ lies in $STUV$. I claim that there are $O(n^{1/3})$ points in $\mathcal{S}$ in it. Indeed, since all points in $\mathcal{S}$ have distance at least $1$ from each other, we may draw an open disc of radius $\tfrac{1}{2}$ around each, and none of these discs overlap. Every disc associated with a point in $STUV$ lies completely within the rectangle with width $ST+1$ and height $2$ with parallel sides and common center as $STUV$, whose area is also $O(n^{1/3})$, and since each disc has $\Omega(1)$ area we must have $O(n^{1/3})$ discs, as desired. Now consider projecting every point in $\mathcal{S}$, as well as $T$, onto the line through $A$ perpendicular to $ST$, and let $T'$ be the image of $T'$ under this projection. There are $O(n^{1/3})$ projected points on segment $\overline{AT'}$, which has length $1$, hence we may find two adjacent projected points $B,C$ on this segment such that $BC=\Omega(n^{-1/3})$. Then taking $\ell$ as the perpendicular bisector of $\overline{BC}$ works, since as before its distance from any point in $\mathcal{S}$ is at least $\tfrac{BC}{2}=\Omega(n^{-1/3})$, and $\ell$ separates the segment joining $A$ with some point in $\mathcal{S}$ on the other side of line $\overline{ST}$, which we previously proved exists. This finishes the problem. $\blacksquare$

Let $c$ be a sufficiently small constant. Assume $n$ is sufficiently high. Assume toward a contradiction there is no line separating $S$ such that the distance from the line to any point is at least $\frac c2 n^{-1/3}$. Let $A$ be one of the points. Claim: No point is more than $cn^{2/3}$ units from $A$. Proof: Assume toward a contradiction some point $B$ is more than $cn^{2/3}$ units away from $A$. Project all of the points onto line $AB$ to get a set $S'$ of points. Then, on this line there must be a segment of length $cn^{-1/3}$ between $A$ and $B$ with no elements of $S'$. The perpendicular bisector of that segment has distance at least $\frac c2 n^{-1/3}$ from each point in $S$. Let $P$ be the point in $S$ with the highest distance from $A$. Assume $A$ is at position $(0, 0)$ and $P$ is at position $(d, 0)$. Let $T$ be the set of points in $S$ with $x$ coordinate over $d-1$. Let $(x, y)\in T$. Then, $x^2+y^2\le d^2$, so $y^2\le x^2-d^2 \le 2d-1$. Therefore, $y\le \sqrt{2d-1}$. So, $T$ is contained in the rectangle bounded by $x>d-1$, $x\le d$, $y\le \sqrt{2d-1}$, $y\ge -\sqrt{2d-1}$. Therefore, there are at most $2\sqrt{2d-1}+1 \le 2\sqrt{2c}n^{1/3} + 1$ points in $T$. Because there is a point with $x$ coordinate exactly $d$, by pigeonhole, there is some interval of length at least $\frac{1}{2\sqrt{c}n^{1/3}+1} \ge cn^{-1/3}$ within $[d, d+1]$ such that no point in $T$ has an $x$ coordinate in that interval. Let that interval be $(a, b)$. Then, the line $x=\frac{a+b}2$ has distance at least $\frac c2 n^{-1/3}$ from each point in $S$.

Gorgeous question, once again the kind of questions I thought I would never solve in my entire life, and now I casually get it in a mock that was IMAR 2024 p3, ISL 2016 N8 (posting soon, omg I have a lot of write ups to do aaaa help), and this one as p3. I think that once again this deserves to be a solution with some motivational remarks as the journey at the beggining is kinda demotivating, and it takes a lot of time to figure out with $-1/3$ makes sense in this case. Let $d=AB$ for $A,B \in \mathcal S$ be a chord with maximal distance, now consider the area that bounds $\mathcal S$ which is $(A,AB) \cap (B,BA)$, the reason for this pick is that in order to get bounds it's ideal to have all points on $\mathcal S$ down control enclosed in a convex shape, it's not the first time I see this idea but in a previous one it ended up not being needed, unlike here where it's literaly awesome. Our idea will be that, we project the points on a line $\ell'$ and then if we get that two consecutive projections make a distance of $O(n^{-\frac{1}{3}})$ we are simply done by letting $\ell$ to be perp bisector of these two points chosen, and it makes sense to start focusing through here, as it's the best way to handle the distances condition without embracing the chaos, to simply put it all in parallel lines to measure their distance, also another reason to pick maximal $AB$ as you get that all are inside the segment and can control the projections by taking maximal, which is what we will do now. If we had that $d \ge O(n^{\frac{2}{3}})$ then let the projections to $AB$ from the points of $\mathcal S$ in consecutive order starting from $A$ be $A=P_1, P_2, \cdots, P_{n-1}, P_n=B$ then take maximal $P_iP_{i+1}$ which is at least $\frac{d}{n-1} \ge O(n^{-\frac{1}{3}})$ which wins by the observations made above. Now what if $d \le O(n^{\frac{2}{3}})$, in this case we follow the insight that if they aren't too separate then we have a couple of stacked points in one single region, but what could it be?, we want to ensure that this region also contains the projections in order for us to measure them on $AB$, therefore by parallel lines, this suggests a rectangle, from the idea of pushing points into one place if they aren't too far apart, we conclude that it would be good to have one side constant (more specifically to be $1$) as now we can do this: Claim: On a $1 \times g$ we have that there is at most $O(g)$ points from $\mathcal S$ on it. Proof: Consider from each point a circle with radius $0.5$, none of the circles intersect clearly from the condition so now since at least a quarter of their area is in $1 \times g$ we have that there can be at most $\frac{16g}{\pi}$ circles on the rectangle, so since each was from a unique point then it's just $O(g)$ points in $1 \times g$ at most, thus the claim is proven. And now the way we use this is that if we let $L$ between $A,B$ on $AB$ such that $AL=1$ and $K$ be midpoint of $AL$, then consider the perpendicular from $K$ to $AB$ to hit $(B,BA)$ at $C,D$ (clearly its inside the convex bound of $\mathcal S$ as $d \ge 1$), so by pythagorean theorem we have that $CD=2\sqrt{d^2-(d-0.5)^2}=O(\sqrt{d}) \le O(n^{\frac{1}{3}})$, so if you consider the rectangle formed by the lines $A\infty_{\perp AB}, L \infty_{\perp AB}, C\infty_{AB}, D \infty_{AB}$ then this is a $1 \times CD$ which then from the bound above and the claim contains at most $O(n^{\frac{1}{3}})$ points, if it contained zero we take $CD$ as $\ell$, and win trivially, else let $A=R_0, R_1, \cdots R_{m-1}$ be inside the rectangle and let $R_m$ be the point outside the rectangle such that its projection to $AB$ its the closest to $L$, then we apply the same insight from the beggining and consider the maximal $R_iR_{i+1}$ which is at least $\frac{1}{m}$ and oh suprice, from the $O$ bounds above this is at least $O(n^{-\frac{1}{3}})$ which completes this case. Since in both cases such line $\ell$ exists, we are done .