Maths Olympiad Prep

Library / /20 of 57

Combinatorics Difficulty 6.3 National olympiad Prove it Russia

A point XX is chosen inside a convex 100-gon (XX does not lie on sides or diagonals of the 100-gon). Initially, the vertices of the polygon are not marked. Pete and Bazil mark the vertices in turn. Pete starts and marks two vertices by his first move; after that, by any move a player marks one vertex. If after someone's move the point XX appears to lie inside a polygon whose vertices are all marked, the player who made this move loses the game. Prove that Pete has a winning strategy.

Впутри выпуклого 100-угольника выбрана точка XX, не лежащая ни на одной его стороне или диагонали. Исходно вершины многоугольника не отмечены. Петя и Вася по очереди отмечают ещё не отмеченные вершины 100-угольника, причём Петя начинает и первым ходом отмечает сразу две вершины, а далее каждый своим очередным ходом отмечает по одной вершине. Проигрывает тот, после чьего хода точка XX будет лежать впутри многоугольника с отмеченными вершинами. Докажите, что Петя может выиграть, как бы ни ходил Вася.

Solutions — 2

Solution 1

Paint the sides of the polygon alternately in black and white. Consider some convex quadrilateral ABCDABCD where ABAB and CDCD are sides of the same color; let KK be the meeting point of its diagonals. If XX lies in the triangle KBCKBC (see Fig. 17), then Pete can mark BB and CC by his first move and win (no succeeding moves can be made at the same half-plane of BCBC as XX). It remains to prove that there exists such quadrilateral.

Assume the contrary. Let TT be a vertex of the 100-gon, let the ray TXTX intersect a black side PQPQ, and let TRTR be a black side adjacent to TT (see Fig. 18). Then the ray RXRX should also meet the segment PQPQ. Next, if SS is the other vertex adjacent to RR, then the ray SXSX also should cross a black side (otherwise the ray RXRX would meet a white side). Proceeding similarly, we get that for every black side MNMN, the rays MXMX and NXNX should both cross one black side; but this fails for the black side PQPQ.

Solution 2

Раскрасим стороны 100-угольника в чёрный и белый цвета так, чтобы любые две соседних стороны имели разные цвета. Рассмотрим две одноцветных стороны ABAB и CDCD, образующие выпуклый четырёхугольник ABCDABCD; пусть его диагонали ACAC и BDBD пересекаются в точке KK. Предположим, что точка XX лежит в треугольнике KBCKBC (см. рис. 17). Покажем, как Петя может играть в этом случае.
Пусть он выберет первым ходом вершины BB и CC. После этого оба игрока могут выбирать только вершины, лежащие в другой полуплоскости от прямой BCBC, нежели точка XX. Этих вершин чётное число, поскольку они разбиваются на пары вершин, образующих стороны того же цвета, что и ABAB. Поэтому последний ход будет за Петей.

Осталось показать, что такие стороны ABAB и CDCD найдутся. Пусть это не так. Рассмотрим любую вершину TT. Предположим, что луч TXTX пересекает чёрную сторону PQPQ (см. рис. 18). Пусть TRTR — чёрная сторона, выходящая из TT; можно считать, что TRPQTRPQ — выпуклый четырёхугольник. Если точка XX лежит внутри треугольника TRQTRQ, то требуемый четырёхугольник RTQPRTQP найден; в противном случае луч RXRX также должен пересекать отрезок PQPQ.

Пусть RSRS — следующая за TRTR сторона 100-угольника. Если луч SXSX пересекает белую сторону, то аналогично доказывается, что луч RXRX также должен её пересекать, что не так. Значит, SXSX пересекает какую-то чёрную сторону, и можно повторить предыдущие рассуждения для вершины SS. Рассуждая так и дальше, мы получим, что для каждой чёрной стороны TRT'R' найдётся чёрная сторона PQP'Q', которую пересекают оба луча TXT'X и RXR'X. Однако это неверно для чёрной стороны PQPQ (лучи PXPX и QXQX пересекают участки контура QTQT и RPRP соответственно) — противоречие.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.