62nd Ukrainian National Mathematical Olympiad

Let us consider the numbers $1234$ and $6789$. For them, we see that the following equation holds: $$6^1+7^1+8^1+9^1=30=1^2+2^2+3^2+4^2.$$ Thus, this pair of numbers is $4$-similar.

Obviously, for $k>5$ there are no $k$-similar numbers, because there are only $10$ different digits. Let us assume that there is a pair of $5$-similar numbers $\overline{a_1{a}_2{a}_3{a}_4{a}_5}$ and $\overline{b_1{b}_2{b}_3{b}_4{b}_5}$, for which the following equation holds: $$a_1^m+a_2^m+a_3^m+a_4^m+a_5^m=b_1^n+b_2^n+b_3^n+b_4^n+b_5^n.$$

The parity of the numbers on both sides of the equation is the same, and therefore their sum is an even number. Since these numbers are all the $10$ digits, their sum must also be even, because the parity of a number does not change when it is raised to a natural power. But the sum of all digits $0+1+2+\cdots +9=45$ is odd. The resulting contradiction shows that the maximum value of $k$ is $4$.