Задачки

Условие

Существует ли степень двойки, из которой перестановкой цифр можно получить другую степень двойки (рассматриваются только перестановки без ведущих нулей)?

Подсказка

Воспользуйтесь тем фактом, что разность любого числа и числа, полученного перестановкой цифр исходного, делится на 9.

Решение

Докажем сначала, что разность исходного числа и числа, полученного перестановкой цифр, делится на 9. Это легко сделать, рассмотрев, для начала, перестановку двух соседних цифр А и В в числе. Разность чисел (...АВ...) - (...ВА...) = 9*(А - В)*10^m, где m - соответствующая степень. Видно, что эта разность делится на 9. Так как любую перестановку цифр можно получить последовательными перестановками соседних цифр, то разность чисел, полученных путем любой перестановки цифр, будет делиться на девять.
Теперь рассмотрим разность 2-х чисел являющихся степенями двойки: 2ⁿ - 2^k = (2^{n - k}-1)* 2^k. Разность степеней двойки n - k не должна превышать 3, так как иначе изменится количество цифр в числе (2⁴ = 16 > 10), а числа (2¹ - 1)* 2^k,  (2² - 1)* 2^k,  (2³ - 1)* 2^k на 9 не делятся. Противоречие.

MMOnline