Problem 1360

1. Define the Problem in Graph Theory Terms:
We are given $n \ge 2$ distinct positive integers. We need to find the largest possible number of pairs whose sum is a power of 2. We can represent this problem using a graph $G$ with $n$ vertices, where each vertex represents one of the integers. An edge is drawn between two vertices if and only if their sum is a power of 2.

2. **Claim 1: The Graph $G$ has no cycles.
- Proof:**
Suppose, for contradiction, that $G$ contains a cycle. Let the cycle be $a_1, a_2, \ldots, a_k, a_1$ with $k \geq 3$. Assume $a_1 + a_2$ is the largest sum among all $a_i + a_{i+1}$. Since $a_1 + a_2$ is a power of 2, let it be $2^x$. Similarly, let $a_2 + a_3 = 2^y$ and $a_k + a_1 = 2^z$ with $x > y$ and $x > z$.
- If $y > z$, then $2^x \geq 2^{y+1} > 2^y + 2^z$, which is a contradiction.
- If $y < z$, then $2^x \geq 2^{z+1} > 2^y + 2^z$, which is also a contradiction.
Therefore, $G$ cannot contain any cycles. $\blacksquare$

3. **Claim 2: Any acyclic simple undirected graph $G$ on $n$ vertices has at most $n-1$ edges.
- Proof:**
We proceed by induction on $n$.
- Base Case: For $n = 2$, the graph can have at most 1 edge, which is $n-1$. The base case holds.
- Inductive Step: Assume the statement is true for graphs with $n$ vertices. Consider a graph with $n+1$ vertices. We need to show that this graph has at most $n$ edges.
- Take a maximal path $v_1, v_2, \ldots, v_t$ in the graph. Vertex $v_1$ has no neighbors among $v_i$ (for $i > 2$) since otherwise, it would form a cycle, contradicting the acyclic property. Therefore, $v_1$ can only have $v_2$ as a neighbor, implying $\deg(v_1) \leq 1$.
- Remove $v_1$ and its edge (if it exists). The remaining subgraph on $n$ vertices has at most $n-1$ edges by the inductive hypothesis. Adding back $v_1$ and its edge gives at most $n$ edges in total.
Thus, any acyclic graph on $n+1$ vertices has at most $n$ edges. $\blacksquare$

4. Conclusion:
From Claims 1 and 2, the graph $G$ has at most $n-1$ edges. This means the maximum number of elegant pairs is $n-1$.

5. **Constructing a Graph with $n-1$ Elegant Pairs:**
To show that $n-1$ elegant pairs are attainable, consider the following construction:
- Let $a_1 = 1$ and $a_i = 2^n - i$ for $i = 2, 3, \ldots, n$.
- For each $i \neq 1$, $a_1 + a_i = 1 + (2^n - i) = 2^n - (i - 1)$, which is a power of 2.
- This construction ensures that there are $n-1$ elegant pairs.

The final answer is $\boxed{ n-1 }$.