Игроки по очереди красят ребра полного графа на n больше 2 вершинах в красный (первый игрок) и синий (второй игрок) цвета. Красить ребро, которое уже покрашено в другой цвет, запрещено. Игрок выигрывает, если ребра его цвета задают на n вершинах связный граф. При каких n у первого игрока есть выигрышная стратегия?

задан 20 Фев 11:52

изменен 20 Фев 12:17

@Thankyoufalcao: в задачах такого типа возможно решение без явного предъявления выигрышной стратегии. Прежде всего, легко доказать индукцией по числу вершин графа, что в этой игре не бывает ничьих, даже если оба игрока хотят "кооперативно" добиться ничьей. При любой раскраске рёбер полного графа в 2 цвета, хотя бы один из подграфов окажется связным на n вершинах. Такая задача была на форуме. Тогда у первого есть "преимущество первого хода". А именно, если допустить, что выигрывает второй, то этой же стратегией пользуется первый, с одним "лишним" ребром. Это даёт противоречие.

(20 Фев 20:16) falcao
10|600 символов нужно символов осталось
1

Первым ходом первый создаст красный связный граф из двух вершин. Второй за один ход не сможет изолировать никакую вершину синими ребрами от имеющегося красного графа, значит на следующий ход первый создаст красный связный граф из трех вершин. Данное рассуждение верно и при переходе от k к k+1 ходу. Вывод, за n - 1 ход первый всегда сможет построить красное дерево, значит первый всегда имеет выигрышную стратегию.

ссылка

отвечен 20 Фев 14:30

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×77
×69

задан
20 Фев 11:52

показан
148 раз

обновлен
20 Фев 20:16

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru