Consider $4n$ points in the plane, with no three points collinear.
Using these points as vertices, we form $\binom{4n}{3}$ triangles.
Show that there exists a point $X$ of the plane that belongs to the
interior of at least $2n^3$ of these triangles.
Let $S$ be the set of $4n$ points.
Let $T$ be the set of all lines through the origin. For each $\ell \in T$, let $f(\ell)$ be a line parallel to $\ell$ that does not pass through any point in $S$ and has $2n$ points of $S$ on each side. Such an $f(\ell)$ exists for each $\ell$ since we can move the line continuously in the plane and have the number of points on each side of the line vary continuously in the discrete sense
Any solution?
Best Answer
Consider a line not parallel to any line between two points in our set $S$. Clearly there is some line $\ell$ parallel to this line which bisects $S$. Then by the discrete version of the Ham Sandwich Theorem, there is a line which bisects each of these two sets, with the added constraint that we may have points on our line, such that there are at most $n$ points in each set on each side not counting these. Note that by translating this line by a small amount or if there are two points on the line rotating it by a small angle around their midpoint, we can make it such that these two lines split our set into 4 quadrants with $n$ points in each. We can also translate these lines by a small amount such that their intersection does not pass through any lines containing two points in $S$. Call the intersection of these two lines $X$. We claim that $X$ is contained in at least $2n^3$ triangles.
Now consider two points $A,B$ in opposite quadrants. Say first that their intersection does not pass through $X$. Note then that in one of the two remaining quadrants, every triangle passing through $A,B$, and one of these points will contain $X$. Thus for every pair of points in opposite quadrants, there are at least $n$ triangles whose vertices these points along with a point from another quadrant such that this triangle contains $X$. Note also that each such triangle will not be counted multiple times, since for each such triangle exactly two points are in opposite quadrants. Then there are $2n^2$ choices for these pairs of points, and $n$ choices from here for a third point, so $X$ is contained in at least $2n^3$ triangles.