HMIC 2013 Problem 5

(a) Given a finite set $X$ of points in the plane, let $f_{X}(n)$ be the largest possible area of a polygon with at most $n$ vertices, all of which are points of $X$. Prove that if $m, n$ are integers with $m \geq n>2$, then $f_{X}(m)+f_{X}(n) \geq f_{X}(m+1)+f_{X}(n-1)$. (b) Let $P_{0}$ be a 1-by-2 rectangle (including its interior), and inductively define the polygon $P_{i}$ to be the result of folding $P_{i-1}$ over some line that cuts $P_{i-1}$ into two connected parts. The diameter of a polygon $P_{i}$ is the maximum distance between two points of $P_{i}$. Determine the smallest possible diameter of $P_{2013}$. (In other words, given a polygon $P_{i-1}$, a fold of $P_{i-1}$ consists of a line $l$ dividing $P_{i-1}$ into two connected parts $A$ and $B$, and the folded polygon $P_{i}=A \cup B_{l}$, where $B_{l}$ is the reflection of $B$ over the line l.)