Натуральное число можно умножать на 4 и произвольным образом переставлять в нем цифры. Докажите что превратить число 1 в число 613 с помощью таких операций невозможно

Задача: из числа 1 можно ли получить число 613, если в ходе операции каждый раз можно умножать текущее число на 4 и затем произвольно переставлять цифры полученного результата?

Краткое решение по шагам:

1. Что происходит за одну операцию

• Пусть текущее число равно n.
• Вычисляем 4n.
• Далее переставляем цифры числа 4n произвольно. Получаем новое число, которое называется n_next.
• Важное свойство: цифры у n_next равны цифрам числа 4n (это та же самая мульти-set цифр).

2. Необходимый предшественник для 613

• Чтобы получить 613 на шаге, после умножения на 4 цифры следующего числа должны быть переставлены в 613. Значит 4n должен иметь точно такие же цифры, как у 613, то есть 4n должен быть одной из перестановок цифр 613.
• Перестановки цифр 613: 613, 631, 163, 136, 316, 361.
• Из них число 4n должно делиться на 4 (в силу того, что 4n = 4·n). Среди перечисленных шести чисел делятся на 4 только 136 и 316 (последние две цифры образуют кратные 4: 36 и 16 соответственно).
• Следовательно, если 613 возможно получить, то предыдущее число n должно быть либо n = 136/4 = 34, либо n = 316/4 = 79.

3. Проверка возможности получить 34 или 79 ранее

• Рассмотрим 34: чтобы получить 34 на некотором шаге, после предыдущего шага 4·m должен быть перестановкой цифр 34, то есть равен 34 или 43. Но оба числа 34 и 43 не делятся на 4, значит их не может быть равным 4m. Поэтому число 34 невозможно получить как результат перестановки цифр после умножения на 4.
• Аналогично для 79: предыдущий шаг требовал, чтобы 4m было перестановкой цифр 79, то есть 79 или 97. Ни одно из них не делится на 4, значит 79 also невозможно получить.

4. Заключение

• Чтобы получить 613, предшествующее число должно быть 34 или 79, но ни 34, ни 79 не могут быть получены на любом предыдущем шаге из числа 1 (как показано в пункте 3).
• Следовательно, из числа 1 получить число 613 с помощью таких операций невозможно.

Дополнительные пояснения

• Ваша операция всегда включает умножение на 4, поэтому 4n обязательно кратно 4. После перестановки цифр это свойство может исчезнуть в виде самой цифрированной формы (перестановка не сохраняет кратность 4), но сама цифры 4n остаются теми же. Именно из этого следуетclusion выше: для 613 возможны только предшественники 34 или 79, и они не достижимы.

Если хотите, могу привести аналогичный разбор для других целевых чисел или привести общую схему поиска предшественников для любого заданного целевого числа.