Question

1.В калькуляторе программиста на экране отображаются только целые числа от 1 до 200 и работают только 2 операции +7 и -11. Докажите, что программист может начав с любого числа от 1 до 200 получить любое число от 1 до 200.​

Answer 1

Ответ:

Пошаговое объяснение:

То что уравнение 7n-11k=1 имеет решение в целых числах верно по соотношению Безу, так как числа 7 и 11 взаимно простые. Но покажем это в расчётах. 7·8-11·5=1

Таким образом любое данное число программист может увеличить, или уменьшить на 1.

Главное на выходить за рамки допустимого интервала [1; 200].

Т.е. если при увеличении(уменьшении) числа мы близко подошли к верхней (нижней) границе, то нужно поменять процесс.

Например, данное число 180. Нужно нужно получить 195.

195-180=15

15=15·1=15·(7·8-11·5)=7·120-11·75

Мы не можем 120 раз прибавить 7.

180⇒187⇒194⇒183⇒190⇒197⇒186⇒...

Уменьшение аналогично.

Answer 2

Для доказательства того, что программист может получить любое число от 1 до 200, начав с любого числа от 1 до 200, можно использовать алгоритм "расширенного" алгоритма Евклида.

Пусть нам нужно получить число N от 1 до 200. Программист может начать с числа 1 и с помощью операций +7 и -11 пытаться достичь числа N.

Заметим, что 7 и 11 взаимно простые числа, то есть их наибольший общий делитель равен 1. Это означает, что с помощью операций +7 и -11 мы можем прибавить или вычесть любую целую комбинацию этих чисел.

Таким образом, можно построить таблицу, в которой будут отображены все числа от 1 до 200 и все возможные комбинации операций +7 и -11, которые позволят получить это число:

1: +7 -11 2: +7 +7 -11 -11 3: +7 +7 +7 -11 -11 -11 ... 200: +7 +7 +7 +7 +7 +7 +7 +7 +7 [phone] -11 -11

Как видно из таблицы, для каждого числа от 1 до 200 можно построить соответствующую комбинацию операций +7 и -11, чтобы получить это число. Значит, программист может начать с любого числа от 1 до 200 и получить любое число от 1 до 200.