Version 1. Let $n$ be a fixed positive integer, and let $\mathrm{S}$ be the set of points $(x, y)$ on the Cartesian plane such that both coordinates $x$ and $y$ are nonnegative integers smaller than $2 n$ (thus $|S|=4 n^{2}$ ). Assume that $\mathcal{F}$ is a set consisting of $n^{2}$ quadrilaterals such that all their vertices lie in $S$, and each point in $S$ is a vertex of exactly one of the quadrilaterals in $\mathcal{F}$.
Determine the largest possible sum of areas of all $n^{2}$ quadrilaterals in $\mathcal{F}$.

Version 2. Let $n$ be a fixed positive integer, and let $S$ be the set of points $(x, y)$ on the Cartesian plane such that both coordinates $x$ and $y$ are nonnegative integers smaller than $2 n$ (thus $|S|=4 n^{2}$ ). Assume that $\mathcal{F}$ is a set of polygons such that all vertices of polygons in $\mathcal{F}$ lie in $S$, and each point in $S$ is a vertex of exactly one of the polygons in $\mathcal{F}$.
Determine the largest possible sum of areas of all polygons in $\mathcal{F}$.
Answer for both Versions: The largest possible sum of areas is $\Sigma(n):=\frac{1}{3} n^{2}(2 n+1)(2 n-1)$.
Common remarks. Throughout all solutions, the area of a polygon $P$ will be denoted by $[P]$ We say that a polygon is legal if all its vertices belong to $\mathrm{S}$. Let $O=\left(n-\frac{1}{2}, n-\frac{1}{2}\right)$ be the centre of $\mathrm{S}$. We say that a legal square is central if its centre is situated at $O$. Finally, say that in $\mathcal{F}$ are legal, and each point in $S$ is a vertex of exactly one polygon in $\mathcal{F}$. For an acceptable set $\mathcal{F}$, we denote by $\Sigma(\mathcal{F})$ the sum of areas of polygons in $\mathcal{F}$.
Solution 1, for both Versions. Each point in $S$ is a vertex of a unique central square. Thus the set $\mathcal{G}$ of central squares is acceptable. We will show that
$$
\Sigma(\mathcal{F}) \leqslant \Sigma(\mathcal{G})=\Sigma(n),
$$
thus establishing the answer.
We will use the following key lemma.

Lemma 1. Let $P=A_{1} A_{2} \ldots A_{m}$ be a polygon, and let $O$ be an arbitrary point in the plane. Then
$$
[P] \leqslant \frac{1}{2} \sum_{i=1}^{m} O A_{i}^{2} ;
$$
moreover, if $P$ is a square centred at $O$, then the inequality (2) turns into an equality. Proof. Put $A_{n+1}=A_{1}$. For each $i=1,2, \ldots, m$, we have

Therefore,
$$
\begin{array}{c}
{\left[O A_{i} A_{i+1}\right] \leqslant \frac{O A_{i} \cdot O A_{i+1}}{2} \leqslant \frac{O A_{i}^{2}+O A_{i+1}^{2}}{4} .} \\
{[P] \leqslant \sum_{i=1}^{m}\left[O A_{i} A_{i+1}\right] \leqslant \frac{1}{4} \sum_{i=1}^{m}\left(O A_{i}^{2}+O A_{i+1}^{2}\right)=\frac{1}{2} \sum_{i=1}^{m} O A_{i}^{2},}
\end{array}
$$
which proves (2). Finally, all the above inequalities turn into equalities when $P$ is a square centred at $O$.

Back to the problem, consider an arbitrary acceptable set $\mathcal{F}$. Applying Lemma 1 to each element in $\mathcal{F}$ and to each element in $\mathcal{G}$ (achieving equality in the latter case), we obtain
$$
\Sigma(\mathcal{F}) \leqslant \frac{1}{2} \sum_{\operatorname{M} S} O A^{2}-\Sigma(\mathcal{G}),
$$
which establishes the left inequality in (1)
It remains to compute $\Sigma(\mathcal{G})$. We have
$$
\begin{aligned}
\Sigma(\mathcal{G})= & \frac{1}{2} \sum_{\text {AЄS }} O A^{2}=\frac{1}{2} \sum_{i=0}^{2 n-1} \sum_{j=0}^{2 n-1}\left(\left(n-\frac{1}{2}-i\right)^{2}+\left(n-\frac{1}{2}-j\right)^{2}\right) \\
& =\frac{1}{8} \cdot 4 \cdot 2 n \sum_{i=0}^{n-1}(2 n-2 i-1)^{2}=n \sum_{j=1}^{n-1}(2 j+1)^{2}=n\left(\sum_{j=1}^{2 n} j^{2}-\sum_{j=1}^{n}(2 j)^{2}\right) \\
& =n\left(\frac{2 n(2 n+1)(4 n+1)}{6}-4 \cdot \frac{n(n+1)(2 n+1)}{6}\right)=\frac{n^{2}(2 n+1)(2 n-1)}{3}=\Sigma(n) .
\end{aligned}
$$

Comment. There are several variations of the above solution, also working for both versions of the problem. E.g., one may implement only the inequality $\left[O A_{i} A_{i+1}\right] \leqslant \frac{1}{2} O A_{i} \cdot O A_{i+1}$ to obtain
$$
\Sigma(\mathcal{F}) \leqslant \frac{1}{2} \sum_{i=1}^{4 n^{2}} O K_{i} \cdot O L_{i},
$$
where both $\left(K_{i}\right)$ and $\left(L_{i}\right)$ are permutations of all points in $\mathrm{S}$. The right hand side can then be bounded from above by means of the rearrangement inequality; the bound is also achieved on the collection $\mathcal{G}$. However, Version 2 seems to be more difficult than Version 1. First of all, the optimal model for this version is much less easy to guess, until one finds an idea for proving the upper bound. Moreover, Version 1 allows different solutions which do not seem to be generalized easily - such as Solution 2 below.

Solution 2, for Version 1. Let $\mathcal{F}$ be an accessible set of quadrilaterals. For every quadrilateral $A B C D$ in $\mathcal{F}$ write
$$
[A B C D]=\frac{A C \cdot B D}{2} \sin \phi \leqslant \frac{A C^{2}+B D^{2}}{4}
$$
where $\phi$ is the angle between $A C$ and $B D$. Applying this estimate to all members in $\mathcal{F}$ we obtain
$$
\Sigma(\mathcal{F}) \leqslant \frac{1}{4} \sum_{i=1}^{2 n^{2}} A_{i} B_{i}^{2},
$$
where $A_{1}, A_{2}, \ldots, A_{2 \mathrm{n}^{2}}, B_{1}, B_{2}, \ldots, B_{2 \mathrm{n}^{2}}$ is some permutation of $\mathrm{S}$. For brevity, denote
$$
f\left(\left(A_{i}\right),\left(B_{i}\right)\right):=\sum_{i=1}^{2 n^{2}} A_{i} B_{i}^{2}
$$

The rest of the solution is based on the following lemma.
Lemma 2. The maximal value of $f\left(\left(A_{i}\right),\left(B_{i}\right)\right)$ over all permutations of $S$ equals $\frac{4}{3} n^{2}\left(4 n^{2}-1\right)$ and is achieved when $A_{i}$ is symmetric to $B_{i}$ with respect to $O$, for every $i=1,2, \ldots, 2 n^{2}$. Proof. Let $A_{i}=\left(p_{i}, q_{i}\right)$ and $B_{i}=\left(r_{i}, s_{i}\right)$, for $i=1,2, \ldots, 2 n^{2}$. We have
$$
f\left(\left(A_{i}\right),\left(B_{i}\right)\right)=\sum_{i=1}^{2 n^{2}}\left(p_{i}-r_{i}\right)^{2}+\sum_{i=1}^{2 n^{2}}\left(q_{i}-s_{i}\right)^{2}
$$
it suffices to bound the first sum, the second is bounded similarly. This can be done, e.g., by means of the QM-AM inequality as follows:
$$
\begin{array}{l} 
\sum_{i=1}^{2 n^{2}}\left(p_{i}-r_{i}\right)^{2}=\sum_{i=1}^{2 n^{2}}\left(2 p_{i}^{2}+2 r_{i}^{2}-\left(p_{i}+r_{i}\right)^{2}\right)=4 n \sum_{j=0}^{2 n-1} j^{2}-\sum_{i=1}^{2 n^{2}}\left(p_{i}+r_{i}\right)^{2} \\
\leqslant 4 n \sum_{j=0}^{2 n-1} j^{2}-\frac{1}{2 n^{2}}\left(\sum_{i=1}^{2 n^{2}}\left(p_{i}+r_{i}\right)\right)^{2}=4 n \sum_{j=0}^{2 n-1} j^{2}-\frac{1}{2 n^{2}}\left(2 n \cdot \sum_{j=0}^{2 n-1} j\right)^{2} \\
=4 n \cdot \frac{2 n(2 n-1)(4 n-1)}{6}-2 n^{2}(2 n-1)^{2}=\frac{2 n^{2}(2 n-1)(2 n+1)}{3} .
\end{array}
$$

All the estimates are sharp if $p_{i}+r_{i}=2 n-1$ for all $i$. Thus,
$$
f\left(\left(A_{i}\right),\left(B_{i}\right)\right) \leqslant \frac{4 n^{2}\left(4 n^{2}-1\right)}{3},
$$
and the estimate is sharp when $p_{i}+r_{i}=q_{i}+s_{i}=2 n-1$ for all $i$, i.e. when $A_{i}$ and $B_{i}$ are symmetric with respect to $O$.
Lemma 2 yields
$$
\Sigma(\mathcal{F}) \leqslant \frac{1}{4} \cdot \frac{4 n^{2}\left(4 n^{2}-1\right)}{3}=\frac{n^{2}(2 n-1)(2 n+1)}{3} .
$$

Finally, all estimates are achieved simultaneously on the set $\mathcal{G}$ of central squares.
Comment 2. Lemma 2 also allows different proofs. E.g., one may optimize the sum $\sum_{i} p_{i} r_{i}$ step by step: if $p_{i}<p_{j}$ and $r_{i}<r_{j}$, then a swap $r_{i} \leftrightarrow r_{j}$ increases the sum. By applying a proper chain of such replacements (possibly swapping elements in some pairs ( $\left.p_{i}, r_{i}\right)$ ), one eventually comes to a permutation where $p_{i}+r_{i}=2 n-1$ for all $i$. $\qquad$ side. If we allow a polygon consisting of one point, then Solution 1 is applied verbatim, providing an