Problem 1780

1. Define Efficient and Inefficient Moves:
- Call a move efficient if the frog lands outside of the initial $n \times n$ square.
- Call a move inefficient if the frog lands inside the initial $n \times n$ square.

2. Initial and Final Configuration:
- Initially, there are $n^2$ frogs in the $n \times n$ square.
- In the end, there must be at most $\left\lfloor \frac{n^2}{2} \right\rfloor$ frogs in the $n \times n$ square, as otherwise, there would be two adjacent frogs, which would allow for another move.

3. Inequality for Moves:
- Let $x$ be the number of efficient moves.
- Let $y$ be the number of inefficient moves.
- Since each move removes one frog, we have:
$$x + 2y \ge \left\lceil \frac{n^2}{2} \right\rceil. \qquad (1)$$

4. **Case 1: $n$ is even**
- Partition the $n \times n$ square into $2 \times 2$ squares. There are $\frac{n^2}{4}$ such squares.
- Define a move to operate on a $2 \times 2$ square if the number of frogs in the $2 \times 2$ square strictly decreases as a result of the move.
- An efficient move operates on at most one $2 \times 2$ square.
- An inefficient move operates on at most two $2 \times 2$ squares.
- Each $2 \times 2$ square must be operated on at least twice to ensure no two adjacent frogs remain.
- This implies:
$$2x + y \ge \frac{n^2}{2}. \qquad (2)$$
- Adding inequalities (1) and (2):
$$x + 2y + 2x + y \ge \left\lceil \frac{n^2}{2} \right\rceil + \frac{n^2}{2}$$
$$3x + 3y \ge n^2$$
$$x + y \ge \frac{n^2}{3}$$

5. **Case 2: $n$ is odd**
- For $n = 3$, it is easy to verify the result.
- For $n > 3$, label the squares of the grid as $\{1, 2, \cdots, n\} \times \{1, 2, \cdots, n\}$.
- Partition the $n \times n$ grid as follows:
- The square $(3, 3)$ is its own $1 \times 1$.
- The remaining squares of the third row and column are paired, e.g., $(3, 1)$ and $(3, 2)$, $(3, 4)$ and $(3, 5)$, etc.
- The remaining squares are partitioned into $2 \times 2$ squares.
- Define operates similarly as before.
- Each $2 \times 2$ square must be operated on at least twice, and each $1 \times 2$ pair at least once.
- Each inefficient move operates on at most two shapes, and each efficient move at most one.
- This implies:
$$x + 2y \ge \frac{n^2 - 1}{2}. \qquad (3)$$
- Adding inequalities (1) and (3):
$$x + 2y + x + 2y \ge \left\lceil \frac{n^2}{2} \right\rceil + \frac{n^2 - 1}{2}$$
$$2x + 4y \ge n^2$$
$$x + 2y \ge \frac{n^2}{2}$$
$$x + y \ge \frac{n^2}{3}$$

Thus, in both cases, we have shown that at least $\left\lfloor \frac{n^2}{3} \right\rfloor$ moves are needed to reach a configuration where no more moves are possible.

The final answer is $\boxed{ \left\lfloor \frac{n^2}{3} \right\rfloor }$