Разделы 
Дополнительно
Задача по математике - 3432
2019-06-03 
На плоскости даны 2005 точек (никакие три из которых не лежат на одной прямой). Каждые две точки соединены отрезком. Тигр и Осёл играют в следующую игру. Осёл помечает каждый отрезок одной из цифр, а затем Тигр помечает каждую точку одной из цифр. Осёл выигрывает, если найдутся две точки, помеченные той же цифрой, что и соединяющий их отрезок, и проигрывает в противном случае. Доказать, что при правильной игре Осёл выиграет.
Решение:
Изложим сначала решение, если точек всего 8, и можно использовать только три цифры: 0, 1 и 2 (заметим, что $8 = 2^3$). Осел должен пометить отрезки как на рис. (16 отрезков на рисунке не изображены, их Осел должен пометить цифрой 2).
Докажем, что Тигр проиграет. Ясно, что в каждой из четырех вертикальных пар точек он должен использовать цифру, отличную от нуля. Рассмотрим верхнюю четверку, одну из 0 двух верхних вершин Тигр должен пометить не нулем и одну из двух нижних он должен пометить не нулем. Если бы он обе эти вершины пометил единицей, то проиграл бы. Значит, 0 одну из них он вынужден пометить двойкой.
Аналогично доказывается, что одну из вершин в нижней четверке Тигр должен пометить двойкой, но эти вершины соединены ребром, помеченным двойкой, так что Тигр проиграет.
Теперь мы изложим доказательство для нашего случая, т. е. вместо трех цифр можно использовать все 10, а вместо $8 = 2^3$ точек мы используем $1024 = 2^{10}$ точек.
Итак, выделим из данных точек какие-нибудь $10^24$. Докажем, что Осел может так пометить отрезки, что независимо от того, как пометит точки Тигр, среди выделенных 1024 точек найдутся две точки, помеченные той же цифрой, что и соединяющий их отрезок.
Разобьем выделенные точки на 512 пар, и пусть Осел пометит нулем отрезки, соединяющие точки из одной пары. Далее, объединим получившиеся пары по две. Получим 256 четверок. Осел пометит цифрой 1 еще не помеченные отрезки, соединяющие точки одной четверки. После этого объединим получившиеся четверки по две. Получим 128 восьмерок. Осел пометит цифрой 2 еще не помеченные отрезки, соединяющие точки из одной восьмерки, и так далее. На последнем шаге объединим получившиеся две группы по 512 точек в одну, и пусть Осел пометит еще не помеченные отрезки цифрой 9.
Предположим, что теперь Тигр может пометить точки так, чтобы не нашлось отрезка, помеченного той же цифрой, что и оба его конца. Заметим, что в каждой из 512 исходных пар найдется точка, помеченная ненулевой цифрой. Действительно, иначе нашлись бы две точки, помеченные цифрой 0, ко¬торые соединены отрезком, помеченным цифрой 0.
Докажем теперь, что в каждой из 256 четверок найдется точка, помеченная не нулем и не единицей. Рассмотрим произвольную из 256 четверок. В каждой из двух пар, из которых она образована, найдется точка, помеченная не нулем. Если бы обе эти точки были помечены единицей, они образовывали бы пару, дающую победу Ослу (поскольку они соединены отрезком, помеченным цифрой 1). Следовательно, в каждой из 256 четверок найдется точка, помеченная не нулем и не единицей.
Продолжая это рассуждение, получаем, что в каждой из 128 восьмерок найдется точка, помеченная не нулем, не единицей и не двойкой, в каждой из 64 групп по 16 точек найдется точка, помеченная не нулем, не единицей, не двойкой и не тройкой и т. д.; наконец, в каждой из двух групп по 512 точек найдется точка, помеченная не нулем, не единицей, не двойкой, . . . , не восьмеркой. Следовательно, эти точки помечены цифрой 9. Но они соединены отрезком, помеченным цифрой 9, что противоречит предположению. Итак, Осел выигрывает независимо от игры Тигра.
На плоскости даны 2005 точек (никакие три из которых не лежат на одной прямой). Каждые две точки соединены отрезком. Тигр и Осёл играют в следующую игру. Осёл помечает каждый отрезок одной из цифр, а затем Тигр помечает каждую точку одной из цифр. Осёл выигрывает, если найдутся две точки, помеченные той же цифрой, что и соединяющий их отрезок, и проигрывает в противном случае. Доказать, что при правильной игре Осёл выиграет.
Решение:
Изложим сначала решение, если точек всего 8, и можно использовать только три цифры: 0, 1 и 2 (заметим, что $8 = 2^3$). Осел должен пометить отрезки как на рис. (16 отрезков на рисунке не изображены, их Осел должен пометить цифрой 2).
Докажем, что Тигр проиграет. Ясно, что в каждой из четырех вертикальных пар точек он должен использовать цифру, отличную от нуля. Рассмотрим верхнюю четверку, одну из 0 двух верхних вершин Тигр должен пометить не нулем и одну из двух нижних он должен пометить не нулем. Если бы он обе эти вершины пометил единицей, то проиграл бы. Значит, 0 одну из них он вынужден пометить двойкой.
Аналогично доказывается, что одну из вершин в нижней четверке Тигр должен пометить двойкой, но эти вершины соединены ребром, помеченным двойкой, так что Тигр проиграет.
Теперь мы изложим доказательство для нашего случая, т. е. вместо трех цифр можно использовать все 10, а вместо $8 = 2^3$ точек мы используем $1024 = 2^{10}$ точек.
Итак, выделим из данных точек какие-нибудь $10^24$. Докажем, что Осел может так пометить отрезки, что независимо от того, как пометит точки Тигр, среди выделенных 1024 точек найдутся две точки, помеченные той же цифрой, что и соединяющий их отрезок.
Разобьем выделенные точки на 512 пар, и пусть Осел пометит нулем отрезки, соединяющие точки из одной пары. Далее, объединим получившиеся пары по две. Получим 256 четверок. Осел пометит цифрой 1 еще не помеченные отрезки, соединяющие точки одной четверки. После этого объединим получившиеся четверки по две. Получим 128 восьмерок. Осел пометит цифрой 2 еще не помеченные отрезки, соединяющие точки из одной восьмерки, и так далее. На последнем шаге объединим получившиеся две группы по 512 точек в одну, и пусть Осел пометит еще не помеченные отрезки цифрой 9.
Предположим, что теперь Тигр может пометить точки так, чтобы не нашлось отрезка, помеченного той же цифрой, что и оба его конца. Заметим, что в каждой из 512 исходных пар найдется точка, помеченная ненулевой цифрой. Действительно, иначе нашлись бы две точки, помеченные цифрой 0, ко¬торые соединены отрезком, помеченным цифрой 0.
Докажем теперь, что в каждой из 256 четверок найдется точка, помеченная не нулем и не единицей. Рассмотрим произвольную из 256 четверок. В каждой из двух пар, из которых она образована, найдется точка, помеченная не нулем. Если бы обе эти точки были помечены единицей, они образовывали бы пару, дающую победу Ослу (поскольку они соединены отрезком, помеченным цифрой 1). Следовательно, в каждой из 256 четверок найдется точка, помеченная не нулем и не единицей.
Продолжая это рассуждение, получаем, что в каждой из 128 восьмерок найдется точка, помеченная не нулем, не единицей и не двойкой, в каждой из 64 групп по 16 точек найдется точка, помеченная не нулем, не единицей, не двойкой и не тройкой и т. д.; наконец, в каждой из двух групп по 512 точек найдется точка, помеченная не нулем, не единицей, не двойкой, . . . , не восьмеркой. Следовательно, эти точки помечены цифрой 9. Но они соединены отрезком, помеченным цифрой 9, что противоречит предположению. Итак, Осел выигрывает независимо от игры Тигра.
