Домашние задания: Другие предметы
Задачка про таракана и истину
Мудрый таракан, который видит не дальше, чем на 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
Дело сводится к лемме:
В прямоугольном треугольнике сумма катетов не превышает гипотенузу, умноженную на корень квадратный из двух.
Доказательство достаточно простое, я оставляю его Вам.
Уффф, кажись все?
Для начала таракан вводит на плоскости систему координат с началом координат в точке, где он находится, и произвольно направленными осями, при этом тут же фиксирует направления этих осей, пока отложив на время вопрос о направлениях этих осей.
Далее первый шаг по одной из новорожденных осей. Приблизился - эта ось получает положительное направление в эту сторону. Не приблизился - возвращается в исходную точку - всего 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
Дело сводится к лемме:
В прямоугольном треугольнике сумма катетов не превышает гипотенузу, умноженную на корень квадратный из двух.
Доказательство достаточно простое, я оставляю его Вам.
Уффф, кажись все?
сама придумала?
Так вопрос к задаче какой????
Похожие вопросы
- Как решить эти две задачки?
- Задачка...=)))
- Помогите решить задачки по алгебре (только прошу ногами не пинать что я типо туп)
- решите плиз хотяб одну из двух задачек ПО ФИЗИКЕ, они легкие, на уровне оценки "3"....я в ней просто вапще непонимаю((
- ПОжалуйста, помогите с задачкой. У меня то есть ответ. Но хочется понять и вникнуть, а не просто скатать
- с задачками очень большая просьба помочь. буду благодарен.
- Задачка для первого класса
- помогите решить задачку по физике, оч нужно!!))
- Слушайте что делать: я не могу задачку решить 6класс! Помогите!
- Задачка! 5-й класс =)