## Task 2.

Let $n$ be a natural number. On a lake, there are $2 n$ lily pads marked with the numbers $1,2, \ldots, 2 n$. Frogs jump from lily pad to lily pad such that each frog starts from the lily pad marked with the number 1, at each jump it jumps to a lily pad with a higher number than the one it is currently on, and ends on the lily pad marked with the number $2 n$. Determine the smallest number of frogs for which it is possible that for every pair $(i, j)$ such that $1 \leqslant i<j \leqslant 2 n$, there is a frog that has jumped directly from the lily pad marked with $i$ to the lily pad marked with $j$.
## First Solution.

We will prove that the answer is $n^{2}$.

Consider pairs of lily pads $(i, j)$, where $1 \leqslant i \leqslant n < j \leqslant 2 n$. We will call such pairs valid. There are $n^{2}$ valid pairs.

Notice that if $\left(i_{1}, j_{1}\right)$ and $\left(i_{2}, j_{2}\right)$ are different valid pairs of lily pads, it is not possible for a frog to jump directly from $i_{1}$ to $j_{1}$ and also directly from $i_{2}$ to $j_{2}$. We conclude that the number of required frogs is at least $n^{2}$ because we can associate a frog that jumped directly from one to the other vertex of each valid pair.

Now, by mathematical induction, we will construct jumps for $n^{2}$ frogs for every natural number $n$ such that the condition of the problem is satisfied.

For $n=1$, we take one frog that jumps from lily pad 1 to 2.

Assume that for some natural number $n$, $n^{2}$ frogs are sufficient.

Now consider the lily pads $1,2, \ldots, 2 n+2$. Let $2 n+1$ frogs, numbered $1,2, \ldots, 2 n+1$, jump on them as follows:

Frog 1 jumps directly from lily pad 1 to $2 n+2$.

For $j \in\{2, \ldots, 2 n+1\}$, frog $j$ jumps from lily pad 1 to lily pad $j$, and then from lily pad $j$ to lily pad $2 n+2$.

This covers all pairs $(i, j)$ for which $i=1$ or $j=2 n+2$, so we can ignore these lily pads and assume that the first jump of the remaining frogs is from lily pad 1 to lily pad 2, and the last jump is from lily pad $2 n+1$ to lily pad $2 n+2$.

Notice that there are $2 n$ remaining lily pads numbered $2,3, \ldots, 2 n+1$. By the induction hypothesis, for this sequence of lily pads, it is possible to find $n^{2}$ frogs that start their jumping at point 2, end their jumping at point $2 n+1$, and for every pair $(i, j)$ for which $2 \leqslant i < j \leqslant 2 n+1$, there is a frog that jumped directly from $i$ to $j$.

If we take these $n^{2}$ frogs together with the $2 n+1$ frogs whose jumps we described earlier, we get $n^{2}+2 n+1=(n+1)^{2}$ frogs, thus completing the induction step.