ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 60919
Темы:    [ Теория игр (прочее) ]
[ Ним-сумма ]
[ Симметричная стратегия ]
Сложность: 6
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

Имеется несколько кучек камней. Двое по очереди берут из них камни. За один ход разрешается взять из одной кучки от 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. Если это невозможно, то первый игрок проигрывает.

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .