Задача 98349

Темы:    [ Теория игр (прочее) ] [ Построение треугольников по различным элементам ] [ Правильный (равносторонний) треугольник ] [ Наименьшее или наибольшее расстояние (длина) ]

Сложность: 4- Классы: 8,9,10

Условие

Автор: Канель-Белов А.Я.

Играют двое, ходят по очереди. Первый ставит на плоскости красную точку, второй в ответ ставит на свободные места 10 синих точек. Затем опять первый ставит на свободное место красную точку, второй ставит на свободные места 10 синих, и т.д. Первый считается выигравшим, если какие-то три красные точки образуют правильный треугольник. Может ли второй ему помешать?

Решение 1

  Приведём стратегию первого игрока, при которой он выигрывает на 13-м ходу. За первые 12 ходов он ставит 12 точек  A₁, ..., A₁₂,  лежащих на некоторой прямой l. Для любой точки B вне прямой l существует ровно один правильный треугольник с вершиной в этой точке и основанием, лежащим на l. При этом различным точкам B по одну сторону от l соответствуют различные основания и наоборот. Таким образом, уже имеется 6·11 "кандидатов" в основания – отрезков вида A_iA_j, то есть
12·11 = 132  различных "выигрышных" вершин. Но за свои 12 ходов второй игрок мог закрасить в синий цвет только 120 точек. Следовательно, первый может на 13-м ходу закрасить одну из 132 "выигрышных" точек и образовать правильный треугольник с красными вершинами.

Решение 2

  Приведём (чуть более сложную) стратегию первого игрока, при которой он выигрывает на 8-м ходу. Первые 6 точек он ставит произвольно. Пусть максимальное расстояние между окрашенными (неважно в какой цвет) за первые 6 ходов точками равно d. Седьмую красную точку (обозначим её A) первый игрок ставит так, чтобы расстояние от A до ближайшей к ней окрашенной точки было больше d.
  Рассмотрим всевозможные равносторонние треугольники вида AMC, где M – одна из красных точек. Точка C не окрашена, так как расстояние от окрашенной точки A до C равно  AM > d.  Отсюда также следует, что два треугольника AMC и AND такого вида совпадать не могут. Так как каждой красной точке M соответствует два треугольника указанного вида, то всего имеется 12 различных "выигрышных" вершин С. Второй игрок 7-м ходом сможет поставить только 10 синих точек. Поэтому первый может на 8-м ходу закрасить одну из 12 "выигрышных" точек и образовать равносторонний треугольник с красными вершинами.

Ответ

Не может.

Замечания

4 балла

Источники и прецеденты использования

web-сайт
задача
олимпиада
Название	Турнир городов
Турнир
Номер	18
Дата	1996/1997
вариант
Вариант	весенний тур, тренировочный вариант, 10-11 класс
Задача
Номер	5