62nd Ukrainian National Mathematical Olympiad

Answer: $n-1$

We prove that there exist at most $n-1$ elegant pairs by induction by $n$. The base case for $n=2$ is obvious, we prove the transition. Let the statement be proved for $n-1$, let us prove it for $n$ numbers. Let us denote by $a$ the largest of them, suppose that the number $a$ is contained in some two elegant pairs. Then $a+b$ and $a+c$ are powers of two. Let us denote by $m$ a number such that $2^m\le a<2^{m+1}$. Then $a+b$ and $a+c$ are greater than $2^m$, but less than $2a<2^{m+2}$, because $a+b=a+c=2^{m+1}$, which contradicts the fact that the numbers are pairwise distinct. By induction, among other $n-1$ integers there are no more than $n-2$ elegant pairs, so there are no more than $n-1$ in total, which completes the proof of the transition.

It remains to show that there can be $n-1$ elegant pairs for any $n\ge 2$. Indeed, let us choose $a_1=1$, $a_2=2^2-1$, $a_3=2^3-1$, $\dots$, $a_n=2^n-1$. Then the pairs $(a_1,a_i)$ are elegant for $i=\underline{2,n}$.

---

Alternative solution.

Alternative solution. Consider the following graph with $n$ vertices. Each number corresponds to a vertex, and two vertices are connected by an edge if their corresponding numbers form an elegant pair. Suppose that the graph in question has a cycle. Then let the numbers corresponding to the vertices of this cycle be $a_1,a_2,\dots ,a_t$. This means that the numbers $a_1+a_2,a_2+a_3,\dots ,a_t+a_1$ are powers of two. Without loss of generality, let $a_1$ be the largest of these numbers. Let us denote by $m$ a number such that $2^m\le a_1<2^{m+1}$. Then $a_1+a_2$ and $a_1+a_t$ are greater than $2^m$, but less than $2a_1<2^{m+2}$, because $a_1+a_2=a_1+a_t=2^{m+1}$, which contradicts the fact that the numbers are pairwise distinct. Thus, this graph has no cycles, i.e. it has no more than $n-1$ edge.

It remains to show that $n-1$ there can be an elegant pair for any $n\ge 2$. Indeed, let us choose $a_1=1$, $a_2=2^2-1$, $a_3=2^3-1$, $\dots$, $a_n=2^n-1$. Then the pairs $(a_1,a_i)$ are elegant for $i=\underline{2,n}$.