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

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

Условие

Автор: Марачёв А.

Двое играют в следующую игру. Есть кучка камней. Первый каждым своим ходом берет 1 или 10 камней. Второй каждым своим ходом берёт m или n камней. Ходят по очереди, начинает первый. Тот, кто не может сделать хода, проигрывает. Известно, что при любом начальном количестве камней первый всегда может играть так, чтобы выиграть (при любой игре второго). Какими могут быть m и n?


Решение

  Пусть хотя бы одно из чисел m и n меньше 9 (например, m). При исходной кучке из  m + 1  камня, первый вынужден будет первым ходом взять 1 камень  (m + 1 < 10),  после чего второй возьмет m камней и выиграет. Противоречие.
  Пусть  m = n + 9.  Снова при исходной кучке из  m + 1 = n + 10  камней первый проигрывает.
  Докажем, что при остальных значениях m и n первый выигрывает. Для этого достаточно показать, что при любом количестве камней в куче первый может сделать ход так, чтобы в куче осталось число камней, отличное и от m, и от n.   Пусть в куче k камней и ход первого. Если  k ≤ 10,  то первый выигрывает одним ходом (вычитая 10, если  k = 10,  или 1, если  k ≤ 9).
  Пусть  k > 10.  Первый может оставить в куче либо  k – 1  камень, либо  k – 10.  Если бы в одном случае получалось m, а в другом – n, число  |m – n|  равнялось бы 9. Противоречие. Число камней в куче будет уменьшаться, и в итоге первый выиграет.


Ответ

m, n ≥ 9  и  |m – n| ≤ 9.

Замечания

5 баллов

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

олимпиада
Название Турнир городов
Турнир
Номер 26
Дата 2004/2005
вариант
Вариант осенний тур, основной вариант, 10-11 класс
задача
Номер 2

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

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