$\textbf{Eel}$
An eel is a polyomino formed by a path of unit squares that makes two turns in opposite directions. (Note that this means the smallest eel has four cells.) For example, the polyomino shown below is an eel. What is the maximum area of a $1000\times 1000$ grid of unit squares that can be covered by eels without overlap?
$\textbf{Solution}$
The answer is $\boxed{999998} = 1000\times 1000 - 2$
$\textbf{Analysis}$.
First, let's show that it is possible to cover all the cells in a $(1000\times 1000)$ grid except the two opposite corners. To demonstrate this, we first present a solution to cover all the cells but the two opposite corners in a $(8\times 8)$ grid. This is shown in the below.
Next, we present a "stretchable" ring as shown below. If we place the above $(8\times 8)$ grid in the middle, the combined grid will be $(12\times 12)$ without the two opposite corners. Note that this ring can be stretched to a similar shape measuring $(16\times 16)$ outside and $(12\times 12)$ inside. This means that it is possible to put the previously constructed $(12\times 12)$ grid into such a new ring to make a $(16\times 16)$ grid without the two opposite corners.
This process can be repeated infinitely. Each iteration will increase the side length of a grid by $4$. Therefore, we can cover all the cells except $2$ in a grid with side length of $(8+4k)$ where $k$ is a non-negative integer. Clearly $1000$ meets this criteria by setting $k=248$.
Next, let's show that it is impossible to cover all the cells on any side of a grid. Because we can have at most two sides to share one cell, we must have at least two cells in total cannot be covered. It follows that we can at most cover $(1000\times 1000 - 2)$ cells which has already been proved possible.
If all the cells on one side can be covered, then let's start considering one of its corner cells. In order to cover this cell, an eel must be placed either horizontally or vertically, Regardless of how this eel is placed, the cell next to this eel's vertical turn must be uncovered. This is true because an eel must make two opposite turns.
Now, in order to cover this cell, another eel is required. However, by placing this new eel, we will find at least another cell is not covered by the same reasoning. Because the number of cells on one side is limited (in this case, $1000$), there must be a time when an eel will reach the other side of the grid. At this point, no more eel can be placed to cover the last uncovered cell. Therefore, it is impossible to have all the cells covered on any side.