Given $n>3$ points in the plane such that no three of the points are collinear. Does there exist a circle passing through (at least) $3$ of the given points and not containing any other of the $n$ points in its interior ?
Problem
Source: IMO LongList 1959-1966 Problem 1
Tags: combinatorial geometry, geometry, circle, IMO Longlist
grobber
02.09.2004 00:21
Yes, but it's a bit hard to explain in a rigorous manner. Take a variable circle through two adjacent points which are also on the convex hull of the set. First take the circle s.t. it contains no points. Clearly, this is possible by taking its center as "far away" from the set as possible. When the center $\to\infty$, the circle tends to degenerate to the line connecting the two points, and since there are no points inside the segment connecting the two we have chosen, the conclusion follows. Now start "pushing" the circle towards the set of points and stop when we have reached the first points. This is the desired circle.
Boy Soprano II
28.07.2006 19:30
Yes. We take two adjacent points $A$ and $B$ on the convex hull. Now we select the point $C$ such that the angle $ACB$ is maximized, and we say that these three points satisfy the condition. The reason is that if a point $D$ is inside this circle, then since it must be on the same side of the line $AB$, the angle $ADB$ must be greater than $ACB$, which is a contradiction. Q.E.D.
quantumbyte
26.03.2011 03:36
@BoySoprano why does D have to be on the same side of line AB can't be on the other side and still work.
mavropnevma
26.03.2011 14:15
$A$ and $B$ are adjacent vertices on the convex hull, so the whole polygonal convex hull, hence all other $n-2$ points, are on the same side of the line $AB$.
MADharm
16.11.2018 10:33
Boy Soprano II wrote:
Yes. We take two adjacent points $A$ and $B$ on the convex hull. Now we select the point $C$ such that the angle $ACB$ is maximized, and we say that these three points satisfy the condition. The reason is that if a point $D$ is inside this circle, then since it must be on the same side of the line $AB$, the angle $ADB$ must be greater than $ACB$, which is a contradiction. Q.E.D.
Why does if $D$ inside the circle then angle $ADB$ must be greater than $ACB$?