, 2024

Solution:
Let $n=100$. The answer is $\frac{1}{2} n\left(12 n^{2}+3 n-1\right)=6014950$.
A construction for an $8 \times 8$ grid instead (so $n=4$ ):

Label the rows and columns from 1 to $2 n$, and let $(r, c)$ denote the cell at row $r$, column $c$. The cars can be cleared in the following order:
- Remove all cars in row $n$.
- For each row $k=n-1, \ldots, 1$, move the $n$ upward-facing cars in row $k$ once, then remove all remaining cars in row $k$.
- Now all cars in the upper-left quarter of the grid can be removed, then those in the upper-right, then those in the lower-right.

Moreover, this starting configuration indeed requires
$$4 \cdot \frac{n^{2}(3 n+1)}{2}-\frac{n(n+1)}{2}=\frac{1}{2} n\left(12 n^{2}+3 n-1\right)$$
moves to clear.

Now we show this is the best possible. Take some starting configuration for which it is possible for all cars to leave. For each car $c$, let $d(c)$ denote the number of moves $c$ makes before it exits. Partition the grid into concentric square "rings" $S_{1}, \ldots, S_{n}$, such that $S_{1}$ consists of all cells on the border of the grid, $\ldots, S_{n}$ consists of the four central cells:

Since all cars can be removed, each $S_{k}$ contains some car $c$ which points away from the ring, so that $d(c)=k$. Now fix some ring $S_{k}$. Then:
- If car $c$ is at a corner of $S_{k}$, we have $d(c) \leq 2 n+1-k$.
- Each car $c$ on the bottom edge of $S_{k}$, say at $(x, k)$ for $k<x<2 n+1-k$, can be paired with the opposing car $c^{\prime}$ at $(x, 2 n+1-k)$. As $c, c^{\prime}$ cannot point toward each other, we have
$$d(c)+d\left(c^{\prime}\right) \leq(2 n+1-k)+\max \{x, 2 n+1-x\} .$$
Likewise, we can pair each car $c$ at $(k, x)$ with the opposing car $c^{\prime}$ at $(2 n+1-k, x)$, getting the same bound.
- If $d(c)=k$, then pairing it with the opposing car $c^{\prime}$ gives $d(c)+d\left(c^{\prime}\right) \leq 2 n+1$. Note that this is less than the previous bound, by at least
$$\max \{x, 2 n+1-x\}-k \geq n+1-k>0$$
Summing the contributions $d(c)$ from the four corners, each pair among the non-corner cars, and a pair involving an outward-facing car gives
$$\sum_{c \in S_{k}} d(c) \leq 4(2 n+1-k)+4\left(\sum_{x=k+1}^{n}[(2 n+1-k)+(2 n+1-x)]\right)-(n+1-k)$$
One can verify that this evaluates to $\frac{1}{2} n\left(12 n^{2}+3 n-1\right)$; alternatively, note that equality holds in our construction, so summing over all $1 \leq k \leq n$ must yield the desired tight upper bound.