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

Проект МЦНМО
при участии
школы 57
Задача 109567
Темы:    [ Выигрышные и проигрышные позиции ]
[ Основная теорема арифметики. Разложение на простые сомножители ]
Сложность: 5-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Автор: Кохась М.

На столе лежат три кучки спичек. В первой кучке находится 100 спичек, во второй – 200, а в третьей – 300. Двое играют в такую игру. Ходят по очереди, за один ход игрок должен убрать одну из кучек, а любую из оставшихся разделить на две непустые части. Проигравшим считается тот, кто не может сделать ход. Кто выиграет при правильной игре: начинающий или его партнер?


Решение

  Пусть перед каким-то ходом начинающего количества спичек на столе имеют вид 2na, 2nb и 2mc, где 0 ≤ n < m,  а числа a, b и c нечётны (назовём такую позицию хорошей). Тогда он своим ходом убирает кучку из 2na спичек, а кучку из 2mc спичек делит на кучки из 2n и  2n(2m–n c – 1)  спичек. После этого количества спичек в кучках будут иметь вид 2na', 2nb', 2nc', где a', b' и c' – нечётные числа. Если это позиция  (1, 1, 1),  то партнер проиграл.
  В противном случае можно считать, что второй игрок своим ходом убирает кучку из 2na' спичек, а кучку из 2nb' спичек делит на две кучки – из 2ku и 2lv спичек, где u и v – нечётные числа и  k ≥ l.  Тогда  2nb' = 2ku + 2lv.  Если при этом  k < n,  то  k = l < n,  а если  k > n,  то  l = n;  случай  k = n  невозможен. Таким образом, начинающий снова окажется в хорошей позиции.
  Поскольку исходная позиция – хорошая:  100 = 2²·25,  300 = 2²·75,  200 = 2³·25,  то при такой стратегии начинающий всегда будет получать хорошую позицию, то есть у него всегда будет ход.


Ответ

Начинающий.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 1994
Этап
Вариант 5
класс
Класс 9
задача
Номер 94.5.9.3
олимпиада
Название Всероссийская олимпиада по математике
год
Год 1994
Этап
Вариант 5
класс
Класс 10
задача
Номер 94.5.10.2

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

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