11.5. Let $M$ be some set of pairs of natural numbers $(i, j), 1 \leq i<j \leq n$ for a fixed $n \geq 2$. If a pair $(i, j)$ belongs to $M$, then no pair $(j, k)$ belongs to it. What is the largest set of pairs that can be in the set $M$?
Answer: $\frac{n^{2}}{4}$ for even $n$, $\frac{n^{2}-1}{4}$ for odd $n$.

Solution. Let's call a natural number $k$ from the interval from 1 to $n$ initial if it is the smaller number in some pair $(k, j)$ from $M$, and a natural number $l$ from the interval from 1 to $n$ final if it is the larger number in some pair $(i, l)$ from $M$. No number $m$ from the interval from 1 to $n$ can be both initial and final at the same time; otherwise, $M$ would contain pairs $(i, m)$ and $(m, j)$ for some $i$ and $j$, which is impossible by the condition. Each pair $(i, l)$ from $M$ is completely determined by its initial number $i$ and final number $j$, so $M$ contains no more than $ab$ pairs, where $a$ and $b$ are the numbers of its initial and final numbers, respectively. Then $ab \leq a(n-a) = an - a^2$ is a quadratic function of the integer variable $a$. For even $n$, it achieves its maximum value $\frac{n^{2}}{4}$ at $a = \frac{n}{2}$, and for odd $n$, it achieves its maximum value $\frac{n^{2}-1}{4}$ at $a = \frac{n-1}{2}$ and $a = \frac{n+1}{2}$.

An example of a set $M$ for which these maximum values are achieved is constructed as follows: declare all numbers from 1 to $\frac{n}{2}$ initial for even $n$, and all numbers from 1 to $\frac{n-1}{2}$ initial for odd $n$, and declare the remaining numbers final. Place in $M$ all possible pairs of initial and final numbers. There will be exactly as many as in the answer.

Grading criteria. Answers with a proof of maximality: 5 points. Examples where the answers are achieved: 2 points.