|
|
 |
Условие
На плоскости даны 2005 точек (никакие три из которых не лежат на одной прямой). Каждые две точки соединены отрезком. Тигр и Осёл играют в следующую игру. Осёл помечает каждый отрезок одной из цифр, а затем Тигр помечает каждую точку одной из цифр. Осёл выигрывает, если найдутся две точки, помеченные той же цифрой, что и соединяющий их отрезок, и проигрывает в противном случае. Доказать, что при правильной игре Осёл выиграет.
Решение
Выделим из данных точек какие-нибудь 1024. Разобьём выделенные точки на 512 пар и пометим нулём отрезки, соединяющие точки из одной пары. Далее, объединим получившиеся пары по две. Получим 256 четвёрок. Пометим цифрой 1 ещё не помеченные отрезки, соединяющие точки одной четвёрки. После этого объединим получившиеся четвёрки по две. Получим 128 восьмёрок. Пометим цифрой 2 ещё не помеченные отрезки, соединяющие точки из одной восьмёрки, и так далее. На последнем шаге мы объединим получившиеся две группы по 512 точек в одну и пометим ещё не помеченные отрезки цифрой 9.
Предположим, что Тигр раскрасил точки так, что не нашлось отрезка, помеченного той же цифрой, что и оба его конца. В каждой из 512 исходных пар найдётся точка, помеченная ненулевой цифрой, иначе эти две точки образовывали бы хорошую (дающую выигрыш Ослу) пару. Рассмотрим какую-нибудь из 256 четвёрок. В каждой из двух пар, из которых она образована, найдётся точка, помеченная не нулём. Если бы обе эти точки были помечены единицей, они бы бы образовывали хорошую пару. Следовательно, в каждой из 256 четвёрок найдётся точка, помеченная не нулём и не единицей. Продолжая это рассуждение, получаем, что в каждой из 128 восьмёрок найдётся точка, помеченная не нулём, не единицей и не двойкой, и т. д.; в каждой из двух групп по 512 найдётся точка,
помеченная не нулём, не единицей, не двойкой, …, не восьмёркой. Следовательно, эти точки помечены цифрой 9. Но они соединены отрезком, помеченным цифрой 9, что противоречит предположению.
Следовательно, Осёл выигрывает независимо от игры Тигра.
Замечания
Немного другой взгляд на эту игру - в задаче 86117. Можно доказать, что Осёл выигрывает даже для 121 точки (см. решение задачи 86117 б).
