Convex $k$-gon containing $k+1$ points must contain $k+2$ points

64 Views Asked by At

Let $\{a_1,a_2,\cdots, a_{2k+2}\}$ be vertices of a convex $(2k+2)$-gon, labelled counterclockwise. Let $A = \{a_1,a_3, \cdots, a_{2k+1}\}$ be the subset labelled by odd integers. Intuitively, any convex $k$-gon $P$ containing $A$ also contains a point $a_{2i}$ for some $i$. I want to know how to prove it rigorously but I don't have much combinatorics or convex geometry (or other "convex theory") background. However, I still believe that I need to use the convexity, of course, some "convex theory", to address it.

1

There are 1 best solutions below

0
On BEST ANSWER

This is easy when you notice the following claim:

A line intersect at a convex polygon at most two points.

(We don't count about the case when the line totally contains an edge. We will see why we assume this soon.)

Now we go back to the original problem. Let the convex $k$-gon be $P$. Suppose all the even-index points are outside. Then we know that, since $a_{2i}$ is outside, $a_{2i-1},a_{2i_2}$ are inside, we can see that, $a_{2i}a_{2i-1}$ and $a_{2i}a_{2i+1}$ both intersects $P$. And further $P$ does not contain any edges of the $2k+2$-gon. So we know that $P$ and $2k+2$-gon are having $2k+2$ intersections. But every edge of $P$ We have at most two intersections with the $2k+2$-gon, so the total number of intersections is at most $2k$. Contradiction.

(By the way, I don't really care about the edge cases, for example, some cases of some vertices is on the edge of another polygon. I assume they're in general positions. If we're considering that, we may need to define "contain" rigorously and they are chores and I'm too lazy...)