Solution:

## 1 Convexity of the largest area of a polygon function

a.
Let $V$ be a finite set of points in the plane. Let $f_{V}$ be a function that takes integers $\geq 3$ as input, and outputs a polygon of largest area with vertices in $V$.

Lemma 1.1. $\left[f_{V}(a+1)\right] + \left[f_{V}(a-1)\right] \leq 2\left[f_{V}(a)\right]$, where $[P]$ represents the area of polygon $P$.

Proof. Let the vertices of $f_{V}(a+1)$ be $1_{a+1}, 2_{a+1}, \ldots, (a+1)_{a+1}$, and let the vertices of $f_{V}(a-1)$ be $1_{a-1}, 2_{a-1}, \ldots, (a-1)_{a-1}$.

Lemma 1.2. The collection of vertices
$$W = \left(1_{a-1}, 2_{a-1}, \ldots, (a-1)_{a-1}, 1_{a+1}, \ldots, (a+1)_{a+1}\right)$$
are in convex configuration.

Proof. Suppose that the vertex $s_{x} \in W$ (for some integers $x \in \{a-1, a+1\}, s$) is inside the convex hull of $W$. Then there exists a vertex $k$ on the convex hull of $W$ such that replacing vertex $s_{x}$ in $f_{V}(x)$ with $k$ increases the area of the polygon $f_{V}(x)$. However, $f_{V}(x)$ is defined to be the polygon with $x$ sides with maximum area. Contradiction. This proves Lemma 2.

Therefore the vertices in $W$ are in convex configuration. Label them with $1, 2, \ldots, 2a$ in clockwise order, starting from an arbitrary vertex. Let $(2a)$ denote the vertex labeled $(2a)$. (The vertex $(1)$ will be shorthanded as 1 when there is no ambiguity).

Lemma 1.3. We have the inequality
$$\left[f_{V}(a+1)\right] + \left[f_{V}(a-1)\right] \leq [\mathcal{P} 1357 \ldots (2a-1)] + [\mathcal{P} 2468 \ldots (2a)] .$$
(Throughout, the symbol $\mathcal{P}$ denotes an arbitrary polygon.)

Proof. It suffices to show that
$$\begin{aligned} & 2[\mathcal{P} 1234 \ldots (2a)] - \left[f_{V}(a+1)\right] - \left[f_{V}(a-1)\right] \\ & \geq 2[\mathcal{P} 1234 \ldots (2a)] - [\mathcal{P} 1357 \ldots (2a-1)] - [\mathcal{P} 2468 \ldots (2a)] . \end{aligned}$$
We will do this using the next few lemmas.

Lemma 1.4. Let $x$ and $y$ be integers $\leq 2a$. If ray $\overrightarrow{(x)(x+1)}$ intersects (or is parallel to) ray $\overrightarrow{(y)(y-1)}$. Then $[\mathcal{P}(x)(x+1)(x+2) \ldots (y-1)(y)] \geq [\Delta(x)(x+1)(x+2)] + [\Delta(x+1)(x+2)(x+3)] + \ldots + [\Delta(y-2)(y-1)(y)]$ (where $(2a+k)$ is equivalent to $(k)$ for all $k$).

Proof. $[\mathcal{P}(x)(x+1)(x+2) \ldots (y-1)(y)] = [\triangle(x)(x+1)(x+2)] + [\triangle(x)(x+2)(x+3)] + \ldots + [\Delta(x)(y-1)(y)]$. Suppose ray $\overline{(x)(x+1)}$ intersects ray $\overline{(y)(y-1)}$ at point $D$, the convexity of $W$ tells us that all vertices in between $x$ and $y$ exclusive going clockwise from $x$ are contained inside triangle $(x) D (y)$. It follows that for any $x'$ between $x$ and $y$ exclusive going clockwise from $x$, that $(x)$ is farther from line $\overline{(x')(x'+1)}$ than $(x'-1)$. Therefore
$$[\Delta(x)(x')(x'+1)] \leq [\triangle(x'-1)(x')(x'+1)] .$$
Summing these relations over all $x$ in between $x$ and $y$ exclusive going clockwise from $x$ gives the statement of Lemma 4, as desired.

An identical argument works if ray $\overline{(x)(x+1)}$ and ray $\overline{(y)(y-1)}$ are parallel, except instead of $D$, all the points between $x$ and $y$ are bounded by the two rays and the line $\overline{(x)(y)}$.

This proves Lemma 4.

Let $z$ and $s$ be integers such that $z \in \{a-1, a+1\}$ and both vertices $s_{z}$ and $(s+1)_{z}$ are adjacent vertices of $f_{V}(z)$. $u$ and $v$ are positive integers defined such that $s_{z}$ has label $(u)$ and $s_{z+1}$ has label $(v)$.

Lemma 1.5. Rays $\overrightarrow{(u)(u+1)}$ and $\overrightarrow{(v)(v-1)}$ intersect or are parallel to each other.

Proof. Since $(u), (u+1), (v-1), (v)$ are in convex formation, then either $\overrightarrow{(u)(u+1)}$ and $\overrightarrow{(v)(v-1)}$ intersect or are parallel to each other, or else $\overrightarrow{(u+1)(u)}$ and $\overrightarrow{(v-1)(v)}$ intersect. If we suppose that the lemma statement does not hold for the sake of contradiction, then it follows that rays $\overrightarrow{(u+1)(u)}$ and $\overrightarrow{(v-1)(v)}$ must intersect. Let $Q$ be the collection of vertices between $v$ and $u$ in $W$, going clockwise, inclusive. Since $Q$ is in convex formation (it's a subset of $W$), and $\overrightarrow{(u+1)(u)}$ and $\overrightarrow{(v+1)(v)}$ intersect, it follows that $u+1$ is farther than $u$ from any line joining two vertices of $Q$. Therefore removing $s_{z}$ (which is the same vertex as $(u)$) from $f_{V}(z)$ and replacing it with vertex $(u+1)$ increases the area of $f_{V}(z)$, contradicting the assertion that $f_{V}(z)$ was the polygon of $z$ vertices with maximal area on the set $V$. Therefore Lemma 5 is proven.

Lemma 5 allows us to apply Lemma 4 to the polygons formed by taking $(\mathcal{P} 1234 \ldots (2a))$ and subtracting out $\left[f_{V}(a+1)\right]$, as well as the polygons formed by taking $(\mathcal{P} 1234 \ldots (2a))$ and subtracting out $f_{V}(a-1)$. Adding the results tells us that
$$\begin{aligned} & 2[\mathcal{P} 1234 \ldots (2a)] - \left[f_{V}(a+1)\right] - \left[f_{V}(a-1)\right] \\ & \geq 2[\mathcal{P} 1234 \ldots (2a)] - [\mathcal{P} 1357 \ldots (2a-1)] - [\mathcal{P} 2468 \ldots (2a)] \end{aligned}$$
which is sufficient to prove Lemma 3.

Since $[\mathcal{P} 135 \ldots (2a-1)]$, $[\mathcal{P} 246 \ldots (2a)] \leq f_{V}(a)$ since $(1), (2), \ldots, (2a) \in V$. Using this fact with Lemma 3, we have proven Lemma 1 as desired.

Lemma 1.6. Any function $g$ from integers to real numbers that satisfies $g(x+1) + g(x-1) \leq 2g(x)$ satisfies the inequality $g(x) + g(y) \leq g(x+1) + g(y-1)$ for $y-1 \geq x+1$, and is thus a convex function.

Proof. We proceed by induction on $y-x$. When $y-x=2$, the problem is trivial.

For $y-x>2$, note that $g(x) + g(x+2) + g(y) + g(y-2) \leq 2g(x+1) + 2g(y-1)$, but the inductive statement shows that $g(x+2) + g(y-2) \geq g(x+1) + g(y-1)$. It follows that $g(x) + g(y) \leq g(x+1) + g(y-1)$, which completes our induction as desired.

It follows from the preceding lemma that $f_{V}(a)$ is a convex function, as desired.

## 2 Folding a paper

Let the smallest diameter be $M$. We claim that $M$ is $\frac{\sqrt{2}}{2^{1006}}$. Let the $P_{0}$ be a 1 by 2 rectangle. For $0 \leq i \leq 2012$, polygon $P_{i+1}$ is polygon $P_{i}$ folded across line $l_{i}$. Line $l_{i}$ splits $P_{i}$ into $P_{i}^{\prime}$ and $P_{i}^{\prime\prime}$, and $P_{i}^{\prime\prime}$ is reflected to $P_{i}^{\prime\prime\prime}$, and $P_{i+1} = P_{i}^{\prime} \cup P_{i}^{\prime\prime\prime}$.

Claim 1. For $1 \leq i \leq 2013$, $P_{i}$ can be expressed as the union of no more than $2^{i}$ convex polygons, and the average number of sides of these polygons is not more than 4.

Proof. We proceed by induction. $P_{0}$ clearly satisfies the inductive hypothesis. Suppose that $P_{i}$ is the union of convex polygons $A_{1}, A_{2}, \ldots, A_{n}$. Folding $A_{1}, A_{2}, \ldots, A_{n}$ across $l_{i}$ and taking the union of the resulting polygons yields $P_{i+1}$.

Let $S(P)$ be the number of sides of polygon $P$.

Lemma. A convex polygon $Z$ is folded once. $Z^{\prime}$ and $Z^{\prime\prime\prime}$ are convex, and $S\left(Z^{\prime}\right) + S\left(Z^{\prime\prime\prime}\right) \leq S(Z) + 4$.

Proof. Any line $l$ through $Z$ splits $Z$ into two convex polygons, and four new vertices are formed by $l$. The number of vertices in a convex polygon equals the number of sides, proving our lemma.

Thus $P_{i+1}$ can be expressed as the union of no more than $2^{i+1}$ convex polygons, and the average number of sides of these convex polygons does not exceed 4. Claim 1 is proven.

Claim 2. For a quadrilateral of area $A$, the diameter has length less than $\sqrt{2A}$.

Proof. Without loss of generality, let the fixed area be 1. The diagonal is not longer than the diameter of the quadrilateral. Half of the product of the diagonals is not less than the area, and Claim 2 follows.

Claim 1 tells us that $P_{2013}$ is the union of no more than $2^{2013}$ convex polygons, whose average number of sides is no more than 4. Part (a) of the problem tells us that there is some quadrilateral with area $\geq \frac{1}{2^{2012}}$, with vertices at the vertices of the final folded figure. Claim 2 tells us that the diameter of this quadrilateral, and thus of $P_{2013}$, is $\geq \frac{\sqrt{2}}{2^{1006}}$.