|
Всем здравствуйте. Помогите решить задачку с экзамена по информатике. Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой – два камня, а во второй – один камень. У каждого игрока имеется неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в три раза число камней в какой-либо кучке, или добавляет два камня в одну из куч. Выигрывает тот игрок, после хода которого в обеих кучках станет не ме- нее 14 камней. Кто выигрывает при правильной игре? У меня получилось, что выиграет 1-й игрок. Так ли это? И, если можно, поделитесь, пожалуйста, правильным решением. Заранее благодарю! задан 19 Апр '14 13:36 
PationallnoZat |
|
Тут анализ достаточно простой. От 1;2 можно перейти к 3;2. Этот ход выигрывает, так как от него можно перейти только к 9;2 3;6 5;2 3;4. Выигрыша при этом пока нет, но далее очевидным образом возможен выигрывающий ход (к 27;2 3;18 15;2 3;12 соответственно). отвечен 19 Апр '14 23:18 
falcao |
@MaximRyPI: я пока не смотрел до конца (тут, судя по всему, надо строить дерево игры -- вручную, или при помощи программы), но меня несколько смутило вот какое обстоятельство. "Классические" игры этого типа длятся конечное число ходов. Например, если число камней уменьшается, то все партии имеют конечную длительность. Здесь же возможен случай типа 3;14. Тогда увеличивать число камней в 1-й кучке никому не выгодно (это сразу влечёт проигрыш), поэтому все начинают работать со 2-й кучкой, и игра длится бесконечно долго.
@falcao Здесь идет речь о суммарном количестве камней в двух кучках. Т.е. если после хода игрок попал в позицию (m,n), где m+n>=14, то он выиграл. Я делал эту задачу именно деревом и у меня получилось, что выиграет 1-й игрок. Вот хочу проверить:)
@MaximRyPI: это другое дело! Мне кажется, для ясности надо было добавить слово "вместе", говоря о 14 камнях. Тогда всё должно считаться до конца.
Сейчас я произведу вычисления и проверю. Вариантов там немного, всё вручную легко должно считаться. Можно даже в виде таблицы оформить.