ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98349
Темы:    [ Теория игр (прочее) ]
[ Построение треугольников по различным элементам ]
[ Правильный (равносторонний) треугольник ]
[ Наименьшее или наибольшее расстояние (длина) ]
Сложность: 4-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

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


Решение 1

  Приведём стратегию первого игрока, при которой он выигрывает на 13-м ходу. За первые 12 ходов он ставит 12 точек  A1, ..., A12,  лежащих на некоторой прямой l. Для любой точки B вне прямой l существует ровно один правильный треугольник с вершиной в этой точке и основанием, лежащим на l. При этом различным точкам B по одну сторону от l соответствуют различные основания и наоборот. Таким образом, уже имеется 6·11 "кандидатов" в основания – отрезков вида AiAj, то есть
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

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .