Задача 60919

Темы:    [ Теория игр (прочее) ] [ Ним-сумма ] [ Симметричная стратегия ]

Сложность: 6 Классы: 8,9,10,11

Условие

Имеется несколько кучек камней. Двое по очереди берут из них камни. За один ход разрешается взять из одной кучки от 1 до 5 камней. Определите выигрышную стратегию в этой игре, если тот, кто взял последний камень а) выигрывает; б) проыигрывает.

Решение

б) Пусть в кучках m₁, m₂, ..., m_l камней, и r₁, r₂, ..., r_l — остатки от деления чисел m₁, m₂, ..., m_l на 6. Положим

n = r₁ r₂ ... r_l  —

ним-сумма по модулю 6. Если в начальной позиции n = 0, то выигрывает второй игрок; во всех остальных случаях — первый. Исключение составляет случай

m1 = m2 =...= ml - 1 = 1,        ml — любое.

(13.6)

(Рассмотрите этот случай отдельно.) Стратегия выигрыша первого игрока: если перед ходом первого игрока набор камней удовлетворяет равенствам 13.6 , причем l нечетно, то ход надо делать так, чтобы новая ним-сумма n' равнялась 1; если l четно и r_l = 1, то забирается любой из камней, лежащих отдельно. Во всех остальных случаях ход надо делать так, чтобы n' = 0. Если это невозможно, то первый игрок проигрывает.

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	5
Название	Числа, дроби, системы счисления
Тема	Системы счисления
параграф
Номер	3
Название	Двоичная и троичная системы счисления
Тема	Двоичная система счисления
задача
Номер	05.081