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
1244
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 ] 

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



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

Сейчас этот форум просматривают: mihaild


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

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