Любое число из четвёрки

[Xenia1996]

С натуральным числом разрешается производить любую из трёх операций:
1) умножить на 10
2) умножить на 10 и прибавить 4
3) разделить на 2 (только если исходное число чётно)

Доказать, что из числа 4 можно получить любое натуральное число за конечное количество таких операций.

[Xenia1996]

Может, условие задачи не совсем понятно?
Или сама задача слишком лёгкая?

[myra_panama]

Xenia1996 , уже я 2- дня жду нет никаких сообщении в моем теме , поэтому ждите устойчиво , (может не кто не просматривает форум)

[Lunatik]

Xenia1996 в сообщении #459869 писал(а):

Может, условие задачи не совсем понятно?
Или сама задача слишком лёгкая?

Просто я не пришёл)))... А если серьёзно, то второе...

[arseniiv]

А для меня решение не напишете? Как понимаю, можно попробовать получить из произвольного числа $n$ следующее, потому что $1$ легко представляется. Только не сообразил, какой алгоритм получения.

[Xenia1996]

arseniiv в сообщении #459910 писал(а):

А для меня решение не напишете? Как понимаю, можно попробовать получить из произвольного числа $n$ следующее, потому что $1$ легко представляется. Только не сообразил, какой алгоритм получения.

Там индукцию можно попробовать применить.
Числа 1, 2, 3 и 4 получить из четвётки можно.
Предположим, можно получить $n$.

Теперь нетрудно доказать, что можно получить и $n+1$:
Умножайте $n$ на 2, пока не получите на конце 0 или 4. Вам понадобится не более трёх таких умножений и Вы получите число $k$ вида $10m$ или $10m+4$, которое будет не более, чем в 8 раз превышать $n$. Значит, число $k$ можно получить путём умножения на 10 (или умножения на 10 и прибавления четвёрки) из числа, меньшего $n$.

[Руст]

Решение получается просто, если из $n_0=n$ получать 4 обратными операциями. Если последняя цифра 4, то вычитаем 4 и делим на 4 и получим $n_1<n_0$. Если последняя цифра 0 сразу делим на 10. Для четных цифр 2,6,8 умножаем на 2,4,8 вычитаем 4 и делим на 10 и получим $n_1<n_0$. Для четных последних цифр надо заметить, что умножая на степень двойки, вычитая 4 получим число делящееся на 4. Поэтому после деления на 10 так же получим четную последнюю цифру.
Если последняя цифра 5, умножаем на 2 и делим на 10. Если последняя цифра 7 то умножаем на 2, вычтем 4 и делим на 10. Последняя цифра 1, умножаем на 4, вычтем 4 и делим на 10. Последняя цифра 3, умножаем на 8, вычтем 4 и делим на 10.
Единственный случай, когда приходится увеличить, это в случае последней цифры 9. Приходится вначале умножать на 16. Однако вычитая 4 и деля получим пусть и большее число, но с четной в конце цифрой и поэтому в дальнейшем $n_i$ будет уменьшаться.
Это показывает, что количество шагов ограничено величиной $C\ln n$.

[Xenia1996]

Руст в сообщении #460126 писал(а):

Решение получается просто, если из $n_0=n$ получать 4 обратными операциями. Если последняя цифра 4, то вычитаем 4 и делим на 4 и получим $n_1<n_0$. Если последняя цифра 0 сразу делим на 10. Для четных цифр 2,6,8 умножаем на 2,4,8 вычитаем 4 и делим на 10 и получим $n_1<n_0$. Для четных последних цифр надо заметить, что умножая на степень двойки, вычитая 4 получим число делящееся на 4. Поэтому после деления на 10 так же получим четную последнюю цифру.
Если последняя цифра 5, умножаем на 2 и делим на 10. Если последняя цифра 7 то умножаем на 2, вычтем 4 и делим на 10. Последняя цифра 1, умножаем на 4, вычтем 4 и делим на 10. Последняя цифра 3, умножаем на 8, вычтем 4 и делим на 10.
Единственный случай, когда приходится увеличить, это в случае последней цифры 9. Приходится вначале умножать на 16. Однако вычитая 4 и деля получим пусть и большее число, но с четной в конце цифрой и поэтому в дальнейшем $n_i$ будет уменьшаться.
Это показывает, что количество шагов ограничено величиной $C\ln n$.

А что у меня не так? Единственная ошибка - это с цифрой 9? Или моё решение принципиально ошибочно?

[Lunatik]

Xenia1996 в сообщении #460044 писал(а):

Умножайте $n$ на 2, пока не получите на конце 0 или 4. Вам понадобится не более трёх таких умножений

Вот этот кусок неверен! 9 --> 8 --> 6 --> 2 --> 4 (4 умножения)

[Xenia1996]

Lunatik в сообщении #460401 писал(а):

Xenia1996 в сообщении #460044 писал(а):

Умножайте $n$ на 2, пока не получите на конце 0 или 4. Вам понадобится не более трёх таких умножений

Вот этот кусок неверен! 9 --> 8 --> 6 --> 2 --> 4 (4 умножения)

Это я поняла, но Руст показал, что и оттуда разрулить можно.

[Lunatik]

Всего-то добавить:

Руст в сообщении #460126 писал(а):

Однако вычитая 4 и деля получим пусть и большее число, но с четной в конце цифрой и поэтому в дальнейшем $n_i$ будет уменьшаться.

и доказательство будет полным (только пару слов поменять )