Задача на планарные графы На плоскости отмечены 2 точки и из каждой торчит
по 3 хвостика. Играют двое. За один ход игрок соединяет два
хвостика линией, не пересекающей уже проведенных линий, ставит
на ней точку и выпускает из этой точки два хвостика по разные
стороны от линии.
Докажите что игра закончится через t+x-2 ходов, если t - изначальное количество точек, а х - изначальное количество хвостиков
Задача на планарные графы На плоскости отмечены 2 точки и из каждой торчит
по 3 хвостика. Играют двое. За один ход игрок соединяет два
хвостика линией, не пересекающей уже проведенных линий, ставит
на ней точку и выпускает из этой точки два хвостика по разные
стороны от линии.
Докажите что игра закончится через t+x-2 ходов, если t - изначальное количество точек, а х - изначальное количество хвостиков
по 3 хвостика. Играют двое. За один ход игрок соединяет два
хвостика линией, не пересекающей уже проведенных линий, ставит
на ней точку и выпускает из этой точки два хвостика по разные
стороны от линии.
Докажите что игра закончится через t+x-2 ходов, если t - изначальное количество точек, а х - изначальное количество хвостиков
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Доказательство:
Изначально у нас есть 2 точки и 6 хвостиков. Давайте рассмотрим, что происходит на каждом ходу:
На каждом ходу один хвостик исчезает, а количество точек увеличивается на 1.Каждый ход у нас добавляется еще одна линия, которая соединяет две точки.Таким образом, каждый ход у нас уменьшается количество хвостиков на 1 (потому что они соединяются), и увеличивается количество точек на 1. Таким образом, после t-2 ходов у нас останется t точек и 0 хвостиков.
Следовательно, игра закончится через t-2 хода.