Очередная хорошая задача на алгоритмы. Предыдущие задачи по теме: Задача 78, Задача 17.
Условие:
Робот загадал число от 1 до 2019. По нашей просьбе он может проделывать следующие операции: 1) Увеличивать число в памяти на 1; 2) Уменьшать число в памяти на 1; 3) Сказать, является ли число в памяти полным квадратом. Докажите, что не более чем за 300 операций мы можем определить какое число загадал робот.
Решение:
Пусть робот загадал число A (мы пока не знаем какое). Тогда будем спрашивать является ли число точным квадратом и если нет то просить увеличить число в память на 1. Так мы будем делать пока не найдем первый полный квадрат. Назовем это число N² (так же пока неизвестное). Сделаем несколько операций уменьшения на 1, пока не получим число A-1. Теперь будем проводить следующие операции: сначала проверяем является ли число в памяти полным квадратом, если нет то уменьшаем его на 1, и т.д. до тех пор, пока число в памяти робота не станет точным квадратом. Заметим, что это число равняется (N-1)².
Пусть мы сделали t операций уменьшения на 1, тогда t=N²-(N-1)²=2N-1. Это означает, что мы можем узнать число N: оно равно (t+1)/2. Зная, сколько операций увеличения на 1 мы выполнили, можно определить изначально число A. Посчитаем теперь количество операций. Операций уменьшения на 1 мы сделали ровно t. Операций увеличения на 1 мы сделали не больше чем t. Операций проверки на точный квадрат мы сделали ровно t+1. Так как 44²<2019<45², то N≤45, t≤91, т.е. мы сделали не более 274 операций, что меньше 300.
Всем кто дочитал, спасибо за внимание! Удачных вам вычислений!