Определить результат игры на графе (рисунок): выигрыш, проигрыш.

Подграф G без контуров, конечным вершинам G присвоен статус «выигрыш» или «проигрыш».

Примечание Это первоначально придуманный вариант задачи. Модификация задачи с включением ничейного исхода, как выяснилось при обсуждении с @falcao (комментарии ниже), ее не улучшила. alt text

задан 9 Фев 2:45

изменен 9 Фев 11:27

@Urt: непонятно, в каком виде надо дать ответ. Судя по сказанному, он как-то зависит от специфики G.

(9 Фев 4:19) falcao

@falcao, а можно привести пример?

(9 Фев 4:29) Urt

@Urt: пример чего? Я понял задачу так, что в рамочке может быть почти любой рисунок (без контуров). То есть это не одна задача, а целый класс задач, которые зависят от G.

(9 Фев 4:47) falcao

@falcao, я имел в виду пример зависимости от G. Зависит ли от G результат?

(9 Фев 4:53) Urt
1

@Urt: пусть в G нет ничего кроме нарисованного. Если все вершины внутри рамки дают выигранные позиции (для того, кто в них начинает), то с предыдущего уровня туда ходить не выгодно. Тогда игра идёт по кругу -- это ничья.

Допустим, что все позиции в рамке проигранные (также для того, кто в них начинает). Тогда все позиции предыдущего уровня проиграны. Из самой верхней позиции ходим вправо. Тогда наш противник идёт на уровень вниз и проигрывает.

(9 Фев 5:38) falcao

@falcao, это единственный вариант "ничьей" (первое предложение). В остальных случаях результат однозначен.

(9 Фев 5:56) Urt
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×3

задан
9 Фев 2:45

показан
87 раз

обновлен
9 Фев 11:27

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

по почте:

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

по RSS:

Ответы

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

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