Problem 1430

1. **Case 1: $n = k$**
- If $n = k$, the board is $k \times k$. The pigeon wins if and only if every grid on the board has an egg. Since the seagull can eat all the eggs in a $k \times k$ grid, the pigeon must lay at least $n^2 = k^2$ eggs to ensure that after the seagull's turn, the pigeon can still fill the board. Therefore, the pigeon wins if $m \geq k^2$.

2. **Case 2: $n \geq k+1$
- Subcase 2.1: $m \leq k^2 - 1$**
- If $m \leq k^2 - 1$, the seagull can always choose a fixed $k \times k$ rectangle and eat all the eggs inside it. Since $m < n^2$, the pigeon cannot win in one move. To fill the $k \times k$ gap created by the seagull, the pigeon needs at least $k^2$ eggs, which is impossible since $m \leq k^2 - 1$. Therefore, the seagull wins.

- **Subcase 2.2: $m \geq k^2 + 1$**
- If $m \geq k^2 + 1$, consider the configuration where the number of eggs is maximized, say $t$. If $t = n^2$, the pigeon wins. Otherwise, the seagull eats the eggs in a $k \times k$ rectangle. If there is a grid not in this rectangle that does not contain an egg, the pigeon can lay an egg in each grid inside the $k \times k$ rectangle and then lay an egg on the empty grid. This results in one more egg than before, contradicting the choice of configuration. Hence, all grids outside the $k \times k$ rectangle contain at least one egg, and the pigeon can lay an egg in each grid inside the $k \times k$ rectangle and win. Therefore, the pigeon wins if $m \geq k^2 + 1$.

3. **Case 3: $m = k^2$
- Subcase 3.1: $n \leq 2k - 1$**
- If $n \leq 2k - 1$, the pigeon wins. For $n = 2k - 1$, there is a unique grid (in the center of the board) that belongs to all $k \times k$ rectangles. The pigeon colors this grid black and starts laying eggs in the grids but not in the black one. After each seagull's turn, at most $k^2 - 1$ grids are empty, and the pigeon can eventually fill all the grids except the black one. Then, the seagull removes eggs from at most $k^2 - 1$ grids, and the pigeon lays one egg in each of them and also in the black grid, winning the game.

- **Subcase 3.2: $n \geq 2k$**
- If $n \geq 2k$, the pigeon loses. Suppose that after a pigeon's turn, there are $a \leq n^2 - 1$ grids that contain at least one egg. The seagull can remove the eggs from at least $a/4$ grids, and the pigeon can lay eggs in at most $k^2$ more grids. The new number of grids that contain at least one egg is $b \leq a - a/4 + k^2 = 3/4a + k^2 \leq 3/4(n^2 - 1) + n^2/4 < n^2$, so $b \leq n^2 - 1$. Inductively, the pigeon can never fill all the grids.

The final answer is: If $\boxed{ k \leq n \leq 2k - 1 }$, the pigeon wins for $m \geq k^2$. If $n \geq 2k$, the pigeon wins for $m \geq k^2 + 1$.