3
1

Всем здравствуйте. Помогите решить задачку с экзамена по информатике.

Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой – два камня, а во второй – один камень.

У каждого игрока имеется неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в три раза число камней в какой-либо кучке, или добавляет два камня в одну из куч. Выигрывает тот игрок, после хода которого в обеих кучках станет не ме- нее 14 камней. Кто выигрывает при правильной игре?

У меня получилось, что выиграет 1-й игрок. Так ли это? И, если можно, поделитесь, пожалуйста, правильным решением.

Заранее благодарю!

задан 19 Апр '14 13:36

1

@MaximRyPI: я пока не смотрел до конца (тут, судя по всему, надо строить дерево игры -- вручную, или при помощи программы), но меня несколько смутило вот какое обстоятельство. "Классические" игры этого типа длятся конечное число ходов. Например, если число камней уменьшается, то все партии имеют конечную длительность. Здесь же возможен случай типа 3;14. Тогда увеличивать число камней в 1-й кучке никому не выгодно (это сразу влечёт проигрыш), поэтому все начинают работать со 2-й кучкой, и игра длится бесконечно долго.

(19 Апр '14 18:28) falcao
1

@falcao Здесь идет речь о суммарном количестве камней в двух кучках. Т.е. если после хода игрок попал в позицию (m,n), где m+n>=14, то он выиграл. Я делал эту задачу именно деревом и у меня получилось, что выиграет 1-й игрок. Вот хочу проверить:)

(19 Апр '14 22:19) PationallnoZat

@MaximRyPI: это другое дело! Мне кажется, для ясности надо было добавить слово "вместе", говоря о 14 камнях. Тогда всё должно считаться до конца.

Сейчас я произведу вычисления и проверю. Вариантов там немного, всё вручную легко должно считаться. Можно даже в виде таблицы оформить.

(19 Апр '14 22:28) falcao
10|600 символов нужно символов осталось
1

Тут анализ достаточно простой. От 1;2 можно перейти к 3;2. Этот ход выигрывает, так как от него можно перейти только к 9;2 3;6 5;2 3;4. Выигрыша при этом пока нет, но далее очевидным образом возможен выигрывающий ход (к 27;2 3;18 15;2 3;12 соответственно).

ссылка

отвечен 19 Апр '14 23:18

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

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

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

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

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

отмечен:

×88
×73

задан
19 Апр '14 13:36

показан
2444 раза

обновлен
19 Апр '14 23:18

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

по почте:

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

по RSS:

Ответы

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

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