1. let $n$ be a natural number. We call a pair of numbers incompatible if their greatest common divisor is 1. What is the minimum number of incompatible pairs that occur when the numbers $\{1,2, \ldots, 2 n\}$ are divided into $n$ pairs?
Solution (Viviane): We call a non-incompatible pair compatible. It is clear that prime numbers strictly greater than $n$ are part of an incompatible pair, and 1 is also part of an incompatible pair. So because of these numbers there is at least

$$
\left\lceil\frac{(\text { number of prime numbers between } n \text { and } 2 n)+1}{2}\right\rceil
$$

incompatible pairs. We divide this set into incompatible pairs. If this set has an odd number of numbers, we divide the last number with 2 into an incompatible pair.

We show that we can divide the remaining numbers into compatible pairs. To do this, consider the odd prime numbers $p_{1}<p_{2}<\ldots<p_{r} \leq n$. Now consider the set of remaining numbers that are divisible by $p_{i}$. If this set has an even number of elements, divide it into pairs that are compatible by construction. If this set has an odd number of elements, choose an even element in the set. This exists because $2 p_{i}$ is surely in the set. Split the remaining elements of the set into pairs. If we have considered all prime numbers, we are left with an even number of numbers, since we have always taken away numbers in pairs. These are all even, so we can split them into compatible pairs.

## Marking Scheme:

- Finding and correctly justifying the lower bound

$$
\left\lceil\frac{(\text { number of prime numbers between } n \text { and } 2 n)+1}{2}\right\rceil
$$

gives 2 points.

- A correct construction that actually realizes this barrier is worth 5 points.
- If the design contains an error that can be easily rectified with the ideas already available, partial points can be awarded according to the severity of the error.