Прибавить 11, стереть 3...

[Ktina]

Одной операцией к числу можно либо прибавить 11, либо стереть в нём в любом месте цифру 3.
Докажите, что с помощью конечного числа таких операций из любого натурального числа можно получить любое другое натуральное число.
(Если стирается тройка в самом начале числа, а за ней сразу идут нули, то эти нули тоже стираются.)

[waxtep]

Достаточно доказать, что все остатки по модулю $11$ могут быть получены друг из друга. Из $0$ последовательно получаются $3,6,9,1,4,7$ прибавлением $3\cdot11$ ($2\cdot11$ для девятки) и стиранием тройки. А дальше: $7\rightarrow337\rightarrow37\rightarrow103$ и $10,2,5,8$ и снова ноль в замыкание

[kotenok gav]

waxtep в сообщении #1302573 писал(а):

Достаточно доказать, что все остатки по модулю $11$ могут быть получены друг из друга.

Не достаточно, мы не можем вычитать 11.

[waxtep]

kotenok gav в сообщении #1302599 писал(а):

Не достаточно, мы не можем вычитать 11.

Тут так: $\forall n\in \mathbb N\,\exists m,a\in\mathbb N: x=3\cdot10^m+a\ge n,0\le a\le10,11|(x-n)$ и можно сделать $n\rightarrow x\rightarrow a$. Т.е. любое натуральное $n$ можно "загнать" в диапазон $[0;10]$ многократным прибавлением $11$ и стиранием $3$ в получившемся числе $300\ldots0a$

[Ktina]

waxtep
kotenok gav
Большое спасибо!

[kotenok gav]

waxtep в сообщении #1302603 писал(а):

Т.е. любое натуральное $n$ можно "загнать" в диапазон $[0;10]$ многократным прибавлением $11$ и стиранием $3$ в получившемся числе $300\ldots0a$

А как доказать?

[waxtep]

kotenok gav в сообщении #1302702 писал(а):

А как доказать?

Таких пар $(m,a)$ бесконечно много, по одной для каждого $m\ge m_0(n)$. Можно найти $m_0(n)$ прямым построением, как округленный вверх десятичный логарифм от соответствующего выражения, $\frac{n}3$

[kotenok gav]

Хорошо, пусть $m=n$. Тогда сколько раз нужно прибавлять 11?

[waxtep]

Можно взять $m=n$, почему нет. Прибавлять $11$ придется около $\frac{3\cdot10^n-n}{11}$ раз.
В моем рассуждении для $m_0$ есть неточность, на самом деле: числа $11\le n\le29$ требуют отдельного рассмотрения, для некоторых из них $m_0=2$, а не $1$. Ну, например $18$ придется гнать до $304$, потому что раньше будут только $29$ и $40$