Задача
Имеется несколько кучек камней. Двое по очереди берут из них камни. За один ход разрешается взять из одной кучки от 1 до 5 камней. Определите выигрышную стратегию в этой игре, если тот, кто взял последний камень а) выигрывает; б) проыигрывает.
Решение
б) Пусть в кучкахm1,m2, ...,mlкамней, иr1,r2, ...,rl — остатки от деления чиселm1,m2, ...,mlна 6. Положим
n = r1 $\displaystyle \oplus$ r2 $\displaystyle \oplus$...$\displaystyle \oplus$ rl —
ним-сумма по модулю 6. Если в
начальной позицииn= 0, то выигрывает второй игрок; во всех
остальных случаях — первый. Исключение составляет случай| m1 = m2 =...= ml - 1 = 1, ml — любое. | (13.6) |
(Рассмотрите этот случай отдельно.) Стратегия выигрыша первого игрока: если перед ходом первого игрока набор камней удовлетворяет равенствам 13.6, причемlнечетно, то ход надо делать так, чтобы новая ним-суммаn'равнялась 1; еслиlчетно иrl= 1, то забирается любой из камней, лежащих отдельно. Во всех остальных случаях ход надо делать так, чтобыn'= 0. Если это невозможно, то первый игрок проигрывает.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет