2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Прибавить 11, стереть 3...
Сообщение08.04.2018, 09:45 
Аватара пользователя


01/12/11

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

 Профиль  
                  
 
 Re: Прибавить 11, стереть 3...
Сообщение08.04.2018, 16:04 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Прибавить 11, стереть 3...
Сообщение08.04.2018, 18:36 


21/05/16
4292
Аделаида
waxtep в сообщении #1302573 писал(а):
Достаточно доказать, что все остатки по модулю $11$ могут быть получены друг из друга.

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

 Профиль  
                  
 
 Re: Прибавить 11, стереть 3...
Сообщение08.04.2018, 19:04 
Аватара пользователя


07/01/16
1426
Аязьма
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$

 Профиль  
                  
 
 Re: Прибавить 11, стереть 3...
Сообщение09.04.2018, 01:35 
Аватара пользователя


01/12/11

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

 Профиль  
                  
 
 Re: Прибавить 11, стереть 3...
Сообщение09.04.2018, 06:53 


21/05/16
4292
Аделаида
waxtep в сообщении #1302603 писал(а):
Т.е. любое натуральное $n$ можно "загнать" в диапазон $[0;10]$ многократным прибавлением $11$ и стиранием $3$ в получившемся числе $300\ldots0a$

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

 Профиль  
                  
 
 Re: Прибавить 11, стереть 3...
Сообщение09.04.2018, 08:16 
Аватара пользователя


07/01/16
1426
Аязьма
kotenok gav в сообщении #1302702 писал(а):
А как доказать?
Таких пар $(m,a)$ бесконечно много, по одной для каждого $m\ge m_0(n)$. Можно найти $m_0(n)$ прямым построением, как округленный вверх десятичный логарифм от соответствующего выражения, $\frac{n}3$

 Профиль  
                  
 
 Re: Прибавить 11, стереть 3...
Сообщение09.04.2018, 08:52 


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

 Профиль  
                  
 
 Re: Прибавить 11, стереть 3...
Сообщение09.04.2018, 09:17 
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модератор: Модераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group