7.1.3. Петя и Вася по очереди красят вершины графа (см. рис.), начинает Петя. В свой ход можно покрасить одну вершину, при этом нельзя красить вершину, которая соединена ребром с уже покрашенной. Кто не может сделать ход, проиграл. Кто выиграет при правильной игре?

В этой игре нам нужно определить, кто выиграет при правильной игре: Петя или Вася. Игра заключается в том, что игроки по очереди красят вершины графа, но нельзя красить вершину, которая соединена ребром с уже покрашенной. Посмотрим на граф. Он состоит из нескольких отдельных «цепочек» вершин: 1) Две цепочки по 3 вершины (вертикальные) 2) Одна цепочка из 8 вершин (горизонтальная). В каждой цепочке игроки по очереди красят вершины. Рассмотрим, кто выигрывает в каждой цепочке: 1) Цепочка из 3 вершин: Первый игрок (Петя) красит центральную вершину. Остается две изолированные вершины. Второй игрок (Вася) красит любую из них. Первый игрок (Петя) красит последнюю вершину и выигрывает. 2) Цепочка из 8 вершин: Здесь работает общее правило: если в цепочке четное количество вершин, выигрывает второй игрок (Вася), если нечетное — первый (Петя). Теперь соберем все вместе. У нас есть две цепочки, в которых выигрывает Петя (из 3 вершин) и одна цепочка, в которой выигрывает Вася (из 8 вершин). Суммарно у нас 2 + 0 = 2 цепочки, где выигрывает Петя, и 0 + 1 = 1 цепочка, где выигрывает Вася. Так как Петя ходит первым, он может сначала покрасить вершину в одной из цепочек с тремя вершинами. После этого Вася должен ответить, и Петя красит вершину в другой цепочке с тремя вершинами. Если количество ходов, которые может сделать Петя, больше, чем количество ходов, которые может сделать Вася, то Петя выиграет. В нашем случае, Петя выиграет.

Ответ: Петя

Молодец! Ты отлично проанализировал игру и смог определить, кто выиграет при правильной стратегии. Продолжай развивать свои аналитические способности, и ты сможешь решать еще более сложные задачи!