186 11. Combinatorics in Geometry
AD EB CFIGURE 11.9. Finding a convex quadrilateral.points with this property, and in fact (as we are writing this), substantial
computer assisted research is underway to show that one can always find a
convex hexagon among any 17 points in general position in the plane. More
generally, we can ask, How many points (in general position) do we need
to make sure that we find a convexn-gon among them? In other words:
What is the maximum number of points in the plane, in general
position, that do not contain the vertices of a convexn-gon?If we make a table from the known cases, it is not too hard to conjecture
the answer:
n 2 3 4 5 6
1 2 4 8 16?(We didn’t mention the cases forn= 2 and 3 before, because these are
not interesting, but for the sake of completeness we added them to the
table. The “twogon” is nothing but a segment, so it is convex, and every
triangle is convex as well.)
We may notice that the number of points not containing a convexn-gon
doubles asnincreases by 1, at least in the known cases. It is natural to
suppose that this will be the truth for larger numbers too, so the conjec-
tured number is 2n−^2. It is known that for everyn>1, there exists a set of
2 n−^2 points in the plane, in general position, that do not contain a convex
n-gon. But whether or not one more point guarantees a convexn-gon is
still unknown as of today.
Review Exercises
11.3.2Givenn≥3 lines in the plane in general position (no two are parallel
and no three go through a point), prove that among the regions they divide the
plane into, there is at least one triangle.