You are given $n \ge 2$ distinct positive integers. For every pair $a<b$ of them, Vlada writes on the board the largest power of $2$ that divides $b-a$. At most how many distinct powers of $2$ could Vlada have written? Proposed by Oleksiy Masalitin
Problem
Source: Ukrainian Mathematical Olympiad 2023. Day 2, Problem 10.7
Tags: number theory
07.04.2023 09:12
The idea is similar to this problem. The answer is $n-1$. Let $a_1<a_2<\ldots<a_n$ be the $n$ numbers. Consider a graph $G$ on $n$ vertices, where the vertices are the $n$ numbers, and initially draw an edge between every two vertices. Define the weight of an edge to be the greatest power of $2$ that divides the difference of its vertices. Now, consider a subgraph $G'$ of $G$ such that $G'$ has as many vertices as $G$ and the maximum number of edges with distinct weights (if there are many such subgraphs, randomly pick one). We shall prove that $G'$ has at most $n-1$ edges. 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$. Suppose that the edge between $a_1$ and $a_2$ has the minimal weight. Then $a_k-a_1=(a_2-a_1)+\ldots +(a_k-a_{k-1}),$ and since all weights are different, $v_2(a_k-a_1)=v_2(a_2-a_1),$ which is 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^{i}+1$ for all $i \neq 1$. Then, $v_2(a_i-a_1)=i$ for all $i \neq 1$, and so there are $n-1$ distinct powers of $2$, as desired.
07.04.2023 17:06
Maybe an easier solution: Let $S$ be the set of these distinct integers, and denote $f(S)$ the number of distinct powers of $2$ that Vlada could write. The function $f$ is invariant by a "positive" translation and by division by $2$ (if all elements of $S$ are even). WLOG assume $S$ has at least one odd number and one even number, we can write $S = X \cup Y$ where $X$ (resp $Y$) are odds (resp evens), then it is clear that $f(S) \le 1+f(X)+f(Y)$ because $v_2(x-y)=0$ for $x>y \in (X,Y)$, so by induction we can easily prove $f(S) \le |S|-1$ the equality may occur for $S=\{2^i+a | 1\le i\le n\}$