Задачка про таракана и истину
Задачка про таракана и истинуМудрый таракан, который видит не дальше, чем на 1 см, решил отыскать ИСТИНУ. Находится она в точке, расстояние до которой D см. Таракан может делать шаги, каждый не более 1 см, и после этого ему говорят, приблизился ли он к ИСТИНЕ. Таракан может помнить все, в том числе и направление своих шагов. Доказать, что он может отыскать ИСТИНУ, сделав не более 3*D/2+7 шагов.
Ответ(ы) на вопрос:
Ну с Богом на поиски Истины) ) Для начала таракан вводит на плоскости систему координат с началом координат в точке, где он находится, и произвольно направленными осями, при этом тут же фиксирует направления этих осей, пока отложив на время вопрос о направлениях этих осей. Далее первый шаг по одной из новорожденных осей. Приблизился - эта ось получает положительное направление в эту сторону. Не приблизился - возвращается в исходную точку - всего 2 шага - и назначает положительным направлением оси противоположное. Аналогично - истратив еще в худшем случае 2 шага - определяет положительное направление второй оси. Теперь он знает квадрант, в котором находится истина, причем ее координаты при выбранных направлениях осей положительны. Пусть они равны х и у. Докажем, что таракан может достигнуть точки х1,у1, где х1 и у1 - целые части х и у соответственно, не более чем за р = 3D/2 + 2 шагов. Он бежит по оси х х1 шагов, и на х1+1-ом шаге получает сообщение, что на этом шаге он к истине не приблизился. Делает шаг назад (х1 + 2 шага) и тем самым находится по координате х на расстоянии не более 1 см от истины, то есть его х-координата равна х1. Теперь он бежит по оси у, Легко видеть, что самое большее через у1 + 1 шаг он увидит наконец заветную истину. Суммируем все шаги: х1 + у1 + 7 шагов. Осталось показать, что х1 + у1 < 3D/2 Докажем более сильное утверждение, а именно, что х1 + у1 <= x + y <= DV2 Дело сводится к лемме: В прямоугольном треугольнике сумма катетов не превышает гипотенузу, умноженную на корень квадратный из двух. Доказательство достаточно простое, я оставляю его Вам. Уффф, кажись все?
Так вопрос к задаче какой????
сама придумала?
Не нашли ответ?
Похожие вопросы