2014 dxdy logo

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

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




 
 Кривой калькулятор (задача К. Сухова)
Сообщение01.08.2016, 10:46 
Аватара пользователя
На экране кривого калькулятора написано число 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 
Обозначим $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 
Аватара пользователя
NSKuber в сообщении #1141351 писал(а):
как звучит-то!

Симфония.

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

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

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group