## Task 2.

Ante wrote down a sequence $a_{1}, a_{2}, \ldots, a_{2020}$ in which each of the numbers $1,2, \ldots, 2020$ appears exactly once. Barbara wants to find out this sequence, and Ante gives her information through a series of exchanges.

In one exchange, Barbara writes down the numbers from 1 to 2020 on a piece of paper and connects some of them with lines, ensuring that each number is connected to at most one other number, and then hands the paper to Ante. Ante then writes down the numbers from 1 to 2020 on another piece of paper and for each pair of numbers $i$ and $j$ that Barbara connected with a line, he connects the numbers $a_{i}$ and $a_{j}$ with a line, and finally hands the paper to Barbara.

How many exchanges are needed at minimum for Barbara to determine Ante's sequence with certainty?
## Solution.

After one exchange, Barbara cannot determine the Antin sequence with certainty. Indeed, if the numbers $a_{i}$ and $a_{j}$ are connected on Antin's paper, Barbara cannot know which number is $a_{i}$ and which is $a_{j}$.

We will show that Barbara can always determine the Antin sequence with certainty after two exchanges, so the minimum number of required exchanges is exactly 2.

In the first exchange, Barbara pairs 3-4, 5-6, ..., 2019-2020.

In the second exchange, Barbara pairs 2-3, 4-5, ..., 2018-2019.

After these exchanges, Barbara knows the numbers $a_{1}$, $a_{2}$, and $a_{2020}$. Indeed, the number $a_{1}$ is the only one that was not connected to any other number in either the first or the second exchange. The number $a_{2}$ is the only number that was connected to another number only in the second exchange, and the number $a_{2020}$ is the only number that was connected to another number only in the first exchange.

Barbara now knows $a_{3}$ because it is connected to $a_{2}$ after the second exchange. Furthermore, the number $a_{4}$ was connected to $a_{3}$ in the first exchange, so Barbara knows $a_{4}$. Continuing this reasoning, Barbara determines all the other numbers from $a_{1}$ to $a_{n}$. In the $(n+1)$-th step, she determines $a_{n+1}$ because it was connected to $a_{n}$ in exactly one exchange, and depending on the parity of the number $n$, she knows in which one.