[This is a solution to the Separating Circle, geometry puzzle posted earlier]
The problem:
Given $2n+3$ points in the general position (no three collinear, no four concyclic) in the 2D plane, show that there are three points among those, such that the circle through those points has exactly $n$ of the remaining $2n$ points inside the circle (and exactly $n$ outside).
Solution
We use the following property of circles:
If $AB$ is a chord of a circle, and $P$ and $Q$ are any two points on the major (or minor) arc of a circle, then $\angle{APB} = \angle{AQB}$, i.e. the arc of the circle is the locus of points $X$ such that the angle subtended by $AB$ at $X$ is constant.
We won't use this other fact, but just mentioning it for clarity: if $R$ is a point on the opposite arc as $P$ and $Q$ then $\angle{ARB} = 180^{\circ} - \angle{APB}$.
We won't prove these facts here, as they are easily available in textbooks/online.
Now, we can show that, if $S$ is a point inside the circle, on the same side of $A,B$ as $P$ and $Q$, then $\angle{ASB} \gt \angle{APB}$.
Proof: Line through $A$ and $S$ cuts the circle at S'. If $S$ is inside, then $\angle{ASB} = \angle{AS'B} + \angle{SBS'} = \angle{APB} + \angle{SBS'}$
Similarly, if $S$ is outside, on the same side of $AB$ as $P$ and $Q$, then $\angle{ASB} \lt \angle{APB}$.
So, if we have a circle through $A,B,C$ which separates the points, and say all the points lie to the same side of $A,B$, then the angles of the other points will be such that exactly $n$ are smaller than $\angle{ACB}$ and exactly $n$ are bigger.
This gives us a constructive proof:
Take the convex hull of all the points. Since they are not all collinear, the convex hull will have at least three sides. Pick one side, say $AB$. Now all the other points lie on the same side as $AB$.
Now, for each of the remaining $2n+1$ points, $P_i$, compute the angle $\angle{AP_{i}B}$. Since no four are concyclic, all these angles will be distinct, and we can sort them in ascending order, say: $\angle{AP_1B} \lt \angle{AP_2B} \lt \dots \lt \angle{AP_nB} \lt \angle{AP_{n+1}B} \lt \dots \lt \angle{AP_{2n+1}B}$.
Pick $C = P_{n+1}$.
The circle through $A,B,C$ will have $P_1, P_2, \dots, P_n$ outside, and $P_{n+2}, \dots, P_{2n+1}$ inside.
This generalizes to any combination of $n\pm k$ and $ n \mp k$ inside/outside.
The problem:
Given $2n+3$ points in the general position (no three collinear, no four concyclic) in the 2D plane, show that there are three points among those, such that the circle through those points has exactly $n$ of the remaining $2n$ points inside the circle (and exactly $n$ outside).
Solution
We use the following property of circles:
If $AB$ is a chord of a circle, and $P$ and $Q$ are any two points on the major (or minor) arc of a circle, then $\angle{APB} = \angle{AQB}$, i.e. the arc of the circle is the locus of points $X$ such that the angle subtended by $AB$ at $X$ is constant.
We won't use this other fact, but just mentioning it for clarity: if $R$ is a point on the opposite arc as $P$ and $Q$ then $\angle{ARB} = 180^{\circ} - \angle{APB}$.
We won't prove these facts here, as they are easily available in textbooks/online.
Now, we can show that, if $S$ is a point inside the circle, on the same side of $A,B$ as $P$ and $Q$, then $\angle{ASB} \gt \angle{APB}$.
Proof: Line through $A$ and $S$ cuts the circle at S'. If $S$ is inside, then $\angle{ASB} = \angle{AS'B} + \angle{SBS'} = \angle{APB} + \angle{SBS'}$
Similarly, if $S$ is outside, on the same side of $AB$ as $P$ and $Q$, then $\angle{ASB} \lt \angle{APB}$.
So, if we have a circle through $A,B,C$ which separates the points, and say all the points lie to the same side of $A,B$, then the angles of the other points will be such that exactly $n$ are smaller than $\angle{ACB}$ and exactly $n$ are bigger.
This gives us a constructive proof:
Take the convex hull of all the points. Since they are not all collinear, the convex hull will have at least three sides. Pick one side, say $AB$. Now all the other points lie on the same side as $AB$.
Now, for each of the remaining $2n+1$ points, $P_i$, compute the angle $\angle{AP_{i}B}$. Since no four are concyclic, all these angles will be distinct, and we can sort them in ascending order, say: $\angle{AP_1B} \lt \angle{AP_2B} \lt \dots \lt \angle{AP_nB} \lt \angle{AP_{n+1}B} \lt \dots \lt \angle{AP_{2n+1}B}$.
Pick $C = P_{n+1}$.
The circle through $A,B,C$ will have $P_1, P_2, \dots, P_n$ outside, and $P_{n+2}, \dots, P_{2n+1}$ inside.
This generalizes to any combination of $n\pm k$ and $ n \mp k$ inside/outside.
No comments:
Post a Comment