На квадратной пластинке со стороной 1 см сидит вирус-невидимка Вася. Он и доктор Петя ходят по очереди. Очередным $%n$%-м ходом Петя рисует вакциной, как чернилами, отрезок длиной 1 микрон, а затем Вася должен выбрать направление и проползти в этом направлении по прямой расстояние $%1/n$% микрона (не выходя за край пластинки). Если Вася проползёт через любую из точек с вакциной или коснётся её, он погибнет. Петя может действовать с любой точностью. Может ли он за конечное число ходов наверняка погубить вирус?

задан 7 Сен '14 22:05

изменен 8 Сен '14 8:47

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

10|600 символов нужно символов осталось
1

Можно предложить стратегию "деления пополам". За число ходов, равное $%d=10^4$%, можно разделить квадрат полоской на две равные части. Если вирус ещё жив, то он находится в одной из образовавшихся половинок. После этого за $%d/2$% шагов мы поделим эту половинку на две равные части, и вирус (если он остался жить) окажется в квадратике со стороной $%1/2$% см.

Далее продолжаем ту же процедуру, на которую нам теперь потребуется $%d/2+d/4$% шагов, чтобы вирус оказался в квадратике со стороной $%1/4$%, и так далее. Сумма величин такого вида ограничена: $%d+2(d/2+d/4+\cdots+d/2^m) < 3d$%, а сторона квадратика, в котором расположен вирус, уменьшается при этом до $%d/2^m$%. Ясно, что в пределах такой области вирус сможет продвинуться по прямой на расстояние, не превосходящее длины диагонали такого квадратика, что меньше $%2d/2^m$%. Количество же ходов, сделанное на данный момент, составляет порядка $%3d$%, и путь перемещения вируса должен быть равен обратной величине, которая при достаточно большом $%m$% заведомо больше, чем $%2d/2^m$%.

Здесь есть такая тонкость: когда длина стороны квадратика в микронах станет измеряться нечётным числом (например, $%625$%), то для проведения линии потребуется один дополнительный ход, и такое в худшем случае может встретиться не более, чем в $%2m$% случаях. Поэтому нашу предыдущую оценку $%3d$% следует увеличить до $%2m+3d$%. Но линейная функция растёт медленнее экспоненты, поэтому при некотором $%m$% (по-моему, подходит что-то типа $%m=30$%) длина пути, проходимого вирусом, обратная $%2m+3d$%, превысит длину диагонали квадратика, которая равна $%2d/2^m$%.

ссылка

отвечен 8 Сен '14 13:40

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,879
×370

задан
7 Сен '14 22:05

показан
809 раз

обновлен
8 Сен '14 13:40

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru