Высшая проба 2021, 10 класс, задача 6
( баллов) В вершине правильного треугольника со стороной метров (где – натуральное число), стоит невидимый точечный робот, а в точке пересечения медиан треугольника лежит мина. Роботу можно отдавать команду с двинуться на метр в любом из направлений, параллельных сторонам треугольника. Любую команду робот может проигнорировать, но тогда обязан исполнить следующую за ней, если она приказывает двигаться в том же направлении. Кроме того, если команда приказывает выйти за границы треугольника – робот стоит на месте и это не считается игнорированием команды. При каких можно заставить робота наехать на мину?
Решение
Ответ: При .
При подойдет следующая последовательность команд: сдвинуться дважды вдоль , потом дважды вдоль , потом дважды вдоль .
Пусть . Разделим треугольник на маленьких треугольников прямыми, каждая из которых параллельна одной из сторон треугольника и делит две другие в отношении . Назовем точки на этих прямых опасными.
Разобьем все команды на серии одинаковых. Если в серии команда, то робот может ее проигнорировать, так что можно считать, что таких серий не было.
Решение :
Утверждение: Выполняя текущую серию, робот может сделать так, чтобы не попасть на опасную прямую, сонаправленную следующей серии. Докажем это по индукции.
База индукции очевидна.
Переход: по предположению индукции робот сейчас стоит не на опасной прямой, сонаправленной текущей серии команд. Поскольку серия состоит из как минимум двух команд, некоторые из которых робот может проигнорировать, в общем случае у него есть как минимум две возможные позиции, в которые он может попасть после выполнения текущей серии. Расстояние между соседними возможными позициями робота равно одному его шагу, то есть метру. Значит, хотя бы одна из этих позиций не лежит на опасной прямой, сонаправленной следующей серии, так как расстояние между ними равно .
Возможен случай, что у робота есть только одна возможная позиция, в которую он может попасть при выполнении текущей серии команд: если после первого же шага в нужном направлении он окажется на границе треугольника. Но эта позиция, очевидно, является безопасной, так как по предположению индукции робот сейчас сдвигается не вдоль опасной прямой. Следовательно, переход доказан.
Поскольку робот может сделать так, чтобы ни в какой момент времени не сдвигаться вдоль опасной прямой, мы не сможем заставить его наехать на мину.
Решение :
Позволим роботу размножаться: из каждого существовавшего на каком-то ходе робота будут получаться роботы во всех позициях, в которых робот может быть сейчас. Будем рассматривать множества позиций, занятых роботами после серии команд двигаться в одном направлении, далее будем называть их просто Множествами Позиций. Назовем точку мертвой, если в ней пересекаются две проведенные прямые, полуживой, если она принадлежит ровно одной проведенной прямой, и живой в остальных случаях.
Докажем индукцией по числу серий команд, что множество позиций всегда содержит или одну живую точку, или две полуживые, принадлежащие прямым разных направлений. Это очевидно. И это означает, что робота нельзя гарантированно загнать на мину
А0 Разобран случай.
А1 Считается, что робот видимый.
А2 Идея избегания 6 прямых.
А3 Идея раздвоения/идея избегать только прямых, сонаправленных следующему ходу.