You are given $n \ge 2$ distinct positive integers. Let's call a pair of these integers elegant if their sum is an integer power of $2$. For every $n$ find the largest possible number of elegant pairs. Proposed by Oleksiy Masalitin
Problem
Source: Ukrainian Mathematical Olympiad 2023. Day 2, Problem 9.7
Tags: number theory
06.04.2023 20:48
The answer is $n-1$. Consider a graph $G$ on $n$ vertices, where the vertices are the $n$ numbers, and we draw an edge between two numbers if and only if their sum is a power of $2$. Claim 1: The graph $G$ has no cycles. Proof: Suppose a cycle existed, and WLOG let $a_1,a_2,\ldots,a_k,a_1$ be its vertices, with $k \geq 3$. Assume that $a_1+a_2$ is the largest among all $a_i+a_{i+1}$. Then, $(a_1+a_2)<(a_2+a_3)+(a_k+a_1),$ and so $2^x<2^y+2^z$ for some $x,y,z$ such that $x>y$ and $x>z$. If $y>z$, then $2^x \geq 2^{y+1} >2^y+2^z,$ a contradiction. If $y<z$, then $2^x \geq 2^{z+1}>2^y+2^z,$ a contradiction. $\blacksquare$ Claim 2: Any acyclic simple undirected graph $G$ on $n$ vertices has at most $n-1$ edges. Proof: We proceed inductively. For $n=2$ we have nothing to prove. Assume the statement is true for graphs on $n$ vertices, and consider a graph on $n+1$ vertices. First, we prove there exist a vertex with at most degree $1$. Indeed, take a maximal path $v_1v_2 \ldots v_t$ of this graph $G$ (if no path exists, the graph has no edges and then we are triviall done). Vertex $v_1$ has no neighbors among the $v_i$ since otherwise we would obtain a cycle. However, since our path is maximal, it can have no neighbor other than $v_2$. Therefore, $\deg v_1=1$, as desired. Now, take a vertex $v$ with degree at most $1$. The remaining subgraph on $n$ vertices has at most $n-1$ edges, and so in total we have at most $n-1+1=n$ edges, as desired $\blacksquare$ To the problem, Claims 1 and 2 imply that graph $G$ has at most $n-1$ edges. To show that $n-1$ is attainable, we may take $a_1=1$ and $a_i=2^n-i$ for all $i$. Then, $a_1+a_i$ is a power of two for all $i \neq 1$.
07.04.2023 10:08
@above how are you sure that the cycle is with numbers in increasing order. Much easier. Consider the pair with maximal $k$ where $a_i + a_j = 2^k$, $a_i > a_j$, and note that $a_i > 2^{k-1}$, so $a_i + a_s < 2^k$ for any $s\neq j$. In particular, the vertex $a_i$ has degree at most $1$ and so by induction the graph has at most $n-1$ edges.
07.04.2023 10:23
@above, I think the solution in #2 is easily fixable? Take WLOG $a_k$ to be the largest number in the cycle and let $2^x \leq a_k <2^{x+1}$. Then $a_k+a_1=a_k+a_{k-1}=2^{x+1}$, so $a_1=a_{k-1}$, contradiction (these two numbers are bounded by $2^x$ and $2^{x+2}$).
07.04.2023 10:25
Yeah, I fixed my solution. Thanks @2above