62nd Ukrainian National Mathematical Olympiad

We will prove that there are at most $n-1$ different degrees with induction by $n$. The base case for $n=2$ is obvious, let's prove the transition. Let the statement be proved for $k\le n-1$, let us prove it for $n$ numbers. Suppose that all numbers are divisible by the same power of $2$: $2^k$. If $k>0$, then we divide these numbers by $2^k$, it is clear that the degree of occurrence of two in all differences has decreased by $k$, so the number of distinct among them has not changed. If all the numbers are odd, then we can add 1, then none of the differences will change, and the numbers will all become even. We will repeat this operation. It is clear that the only odd number that does not decrease after the operations of addition 1 and division by the maximum degree of occurrence of two is 1. Since there are more than one number, the sum of these numbers will decrease after each pair of operations, so sooner or later we will get a set of numbers that are divisible by different degrees of twos.

Let's divide the numbers into groups $A_1,A_2,\dots ,A_m$, according to the degree of occurrence of two (the degrees are equal to ${\alpha }_1<{\alpha }_2<\cdots <{\alpha }_m$). It is clear that the difference $a_i-a_j$ for $a_i\in A_i,a_j\in A_j$ ($i\ne j$) is divisible by $2^{\min (a_i,a_j)}$, therefore, among the differences between different groups there are only $m-1$ different degrees. For each of these groups, the induction assumption can be applied, so the number of different powers of the differences of numbers from $A_i$ does not exceed $|A_i|-1$. Thus, the number of different degrees of occurrence is no more than $$|A_1|-1+|A_2|-1+\cdots +|A_m|-1+m-1=|A_1|+|A_2|+\cdots +|A_m|-1=n-1.$$

It remains to show that $n-1$ different degrees are possible for any $n\ge 2$. Indeed, let us choose $a_1=1,a_2=2^2+1,a_3=2^3+1,...,a_n=2^n+1$. Then, the pairs $(a_1,a_i)$ for $i=2,n$ have different degrees.

An alternative solution. We prove that there are at most $n-1$ different degrees of occurrence. Indeed, let there be $n$ pairs in which the degrees of occurrence of 2 in the difference of the pair's numbers are pairwise different. Then consider the following graph with $n$ vertices. Each number is assigned a vertex, and two vertices are connected by an edge if their corresponding numbers form one of the considered $n$ pairs. It is clear that the total number of edges $n$, so the graph in question has a cycle. Then let the numbers corresponding to the vertices of this cycle be $a_1,a_2,...,a_m$. Then the degrees of occurrence of the two in the difference $a_1-a_2,a_2-a_3,...,a_m-a_1$ are pairwise different. Without loss of generality, let the degree of occurrence of the twos, $k$, in the number $a_m-a_1$ be the smallest of them. Then all other differences are divisible by $2^{k+1}$, so $a_1\equiv a_2\equiv \cdots \equiv a_m(\text{mod }{2}^{k+1})$, so $a_m-a_1$ is divisible by $2^{k+1}$, which contradicts the assumption. Example is the same as in previous solution.