At least $\frac12(\pi(2n)-\pi(n))$ pairs And I got a construction for about $ \frac12(\pi(2n)-\pi(n)+\pi(\sqrt{2n})+1)$ pairs. Where $\pi(x)$ donates the number of primes less than $x$ The construction may be improved by detailed analysis.

The answer is $x=\left\lceil \dfrac{\pi (2n) - \pi (n) +1}{2} \right\rceil$. To see why this is a lower bound, note that every prime between $n+1$ and $2n$ will always be part of an unsociable pair, and the number $1$ will also always be part of an unsociable pair. Therefore, since there are $\pi(2n)-\pi (n)+1$ such numbers, the number of such pairs will be at least $x$. Now, let $S_0 \subseteq \{1,2,...2n\}$ consist of every number which is not equal to $1$ and which is not a prime between $n+1$ and $2n$. To get a construction with only $x$ unsociable pairs, it's enough to group the elements of $S$ into pairs $(i,j)$ with $\gcd (i,j)>1$, such that there is at most one element of $S$ left over (depending on the parity of $|S|$). We will perform an algorithm. Let $p_1<p_2<...<p_k$ be the primes in $S_0$. Define $X=\emptyset$. At each step $0\le i\le k-1$ we will do the following: First, define $T_i$ as the set of numbers in $S_i$ which are divisible by $p_{k-i}$. Note that $T_i$ contains $p_{k-i}, 2p_{k-i}$. If $|T_i|$ is even, we pair its elements arbitrarily and remove them all from $S_i$. Otherwise, pair all the elements except for $2p_{k-i}$ arbitrarily. Let $S_{i+1}=S_i\backslash T_i$, and add $2p_{k-i}$ to $X$ iff it is not part of a pair. After step $k-1$, since every number in $S_0$ was part of some $T_i$, the only numbers which are not in any pair are the elements of $X$. But all the elements of $X$ are of the form $2p_i$, hence they are all even, so we can pair them up arbitrarily until there is at most one number left, and we're done.

Well this looks pretty tricky to be a P1, are Swiss math olympiad so tough that the difficulty increases in upcoming problems?!

ank 1729 wrote: Well this looks pretty tricky to be a P1, are Swiss math olympiad so tough that the difficulty increases in upcoming problems?! It is tricky but not hard. Other problems are more interesting (some from IMO Shortlist).