2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Кривой калькулятор (задача К. Сухова)
Сообщение01.08.2016, 10:46 
Аватара пользователя


01/12/11

8634
На экране кривого калькулятора написано число 20. Время от времени кальку-
лятор умножает число на экране на 2 и тут же вычитает из результата какое-нибудь
число от 1 до 10. Может ли на экране получиться число 2016? (К. Сухов)

Прежде всего, два замечания по поводу корректности условия задачи:
1. «Какое-нибудь число от 1 до 10» - автор, скорее всего, подразумевал именно целое число, причём от 1 до 10 включительно. Хотя, как знать.
2. Было бы неплохо добавить, что после выполнения двух указанных в условии задачи операций кривой калькулятор выводит полученный результат на экран. А то найдутся умники, которые напишут, что на экране так и останется одно лишь число 20, ведь мы же не дали команду вывести результат.

Теперь к решению.
2016 получить как раз легко. Например, 20; - 40 - 36; - 72 - 70; - 140 - 135; - 270 - 260; - 520 - 510; - 1020 - 1010; - 2020 - 2016.
Зато, скажем, 2500 получить не удастся, как бы не действовал кривой калькулятор.
И вот этот-то момент как раз и вызывает небезынтегральный и небесфакториальный интерес.
Ведь после первой пары операций можно получить любое число от 30 до 39.
После второй - от 50 до 77, после третьей - от 90 до 153, и т. д.
А это означает, что существует бесконечно много натуральных чисел, которые нельзя будет получить с помощью описанных в условии задачи операций.
Иными словами, на протяжении всего натурального ряда будут встречаться «дырки» из таких чисел, причём размер дырки будет расти в геометрической прогрессии по мере нашего путешествия по натуральному ряду.

Хотелось бы найти общую формулу, по которой о каждом натуральном числе можно однозначно сказать, сможет ли оно получиться на экране в результате указанных в условии задачи операций.

Пожалуйста, помогите решить.
Заранее спасибо!

 Профиль  
                  
 
 Re: Кривой калькулятор (задача К. Сухова)
Сообщение01.08.2016, 12:26 
Заслуженный участник


26/10/14
380
Новосибирск
Обозначим $x_0=y_0=20$, и построим последовательности: $x_{k+1}=2x_k - 10$, $y_{k+1}=2y_k - 1$.
Легко видеть, что после $k$-ой операции мы можем получить любое число от $x_k$ до $y_k$. Соответственно, число $x$ можно получить на экране тогда и только тогда, когда существует $k$ такое, что $x_k\leqslant x \leqslant y_k$.
С помощью рекуррентных соотношений нетрудно найти явные формулу для $x_k,y_k$, а с помощью них построить простой в выполнении алгоритм проверки выводимости (как звучит-то!).

 Профиль  
                  
 
 Re: Кривой калькулятор (задача К. Сухова)
Сообщение01.08.2016, 12:41 
Аватара пользователя


07/01/15
1145
NSKuber в сообщении #1141351 писал(а):
как звучит-то!

Симфония.

Последние штрихи:
$$x_k = 2^{k}\cdot 10 + 10$$
$$y_k = 2^{k}\cdot 19 + 1$$

 Профиль  
                  
 
 Re: Кривой калькулятор (задача К. Сухова)
Сообщение01.08.2016, 16:20 
Аватара пользователя


01/12/11

8634
NSKuber
SomePupil
Большое спасибо!

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

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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