|
|
 |
Условие
Петя и Вася по очереди красят рёбра $N$-угольной пирамиды: Петя – в красный цвет, а Вася – в зелёный (ребро нельзя красить дважды). Начинает Петя. Выигрывает Вася, если после того, как все рёбра окрашены, из любой вершины пирамиды в любую другую вершину ведёт ломаная, состоящая из зелёных рёбер. В противном случае выигрывает Петя. Кто из игроков может действовать так, чтобы всегда выигрывать, как бы ни играл его соперник?Решение
Пусть $O$ – вершина пирамиды, $A_1A_2\dots A_N$ – её основание. Разобьём все рёбра пирамиды на пары смежных, одно из которых боковое, а другое лежит в основании: $(OA_1, A_1A_2)$, $(OA_2, A_2A_3), \dots, (OA_N, A_NA_1)$. На каждый ход Пети Вася может отвечать в ту же пару, то есть красить в зелёный цвет ребро из той пары, в которой Петя только что покрасил второе ребро в красный.Если Петя покрасит хотя бы одно ребро в основании пирамиды, то в ответ Вася покрасит боковое ребро из той же пары, пусть это, например, ребро $OA_N$. Так как в конце игры вершина $A_{N-1}$ соединена зелёным ребром либо с $O$, либо с $A_N$, то из неё можно дойти по зелёным рёбрам до $O$. Далее, вершина $A_{N-2}$ соединена либо с $O$, либо c $A_{N-1}$, из которой есть путь по зелёным рёбрам до $O$. Следовательно, и из вершины $A_{N-2}$ можно добраться до $O$ по зелёным рёбрам. Продолжая эти рассуждения, получим, что из всех вершин можно дойти по зелёным рёбрам до вершины $O$, а это значит, что Вася победил.
Таким образом, чтобы не проиграть, Петя должен красить только боковые рёбра. После его предпоследнего хода неокрашенными останутся ребро из пары, в которую он только что сходил, и два ребра ещё из одной пары. Тогда в ответ Вася может покрасить в зелёный цвет последнее неокрашенное боковое ребро, после чего они покрасят ещё по одному ребру в основании. В итоге зелёным цветом будут покрашены все рёбра в основании пирамиды, кроме одного, а также одно боковое ребро, поэтому каждые две вершины будут соединены путём из зелёных рёбер. Значит, и в этом случае Вася победит.
