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

Проект МЦНМО
при участии
школы 57
Задача 105153
Темы:    [ Теория игр (прочее) ]
[ Разные задачи на разрезания ]
[ Алгоритм Евклида ]
[ Простые числа и их свойства ]
Сложность: 4
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

Есть шоколадка в форме равностороннего треугольника со стороной n, разделённая бороздками на равносторонние треугольники со стороной 1. Играют двое. За ход можно отломать от шоколадки треугольный кусок вдоль бороздки, съесть его, а остаток передать противнику. Тот, кто получит последний кусок – треугольник со стороной 1, – победитель. Для каждого n выясните, кто из играющих может всегда выигрывать, как бы не играл противник?

Решение

  Отломленный или образующийся треугольник (очевидно, правильный) со стороной длины m будем называть m-треугольником.
  Случаи  n = 1, 2  очевидны. Разберём два случая при  n > 2.
  1) n простое. Пусть первым ходом отламывается k-треугольник. Остается трапеция со сторонами k,  n – k,  n,  n – k.  Пусть a – большее из чисел k,  n – k,  а b – меньшее (они не равны:  НОД(a, b) = НОД(n, n – k) = 1).  Второй отламывает кусок так, чтобы остался параллелограмм со сторонами a и b. Первому придётся отломить b-треугольник (иначе второй досрочно выиграет, отломив от оставшегося острого угла 1-треугольник и оставив первому шестиугольник, у которого все углы тупые). Получится трапеция со сторонами  a – b,  b, a, b, где  НОД(a – b, b) = НОД(a, b) = 1,  то есть игра придёт к той же ситуации, что и ход назад, но трапеция уменьшится. Так игра будет продолжаться, пока a и b не станут равны 1 (“трапеция” со сторонами 0, 1, 1, 1 – это 1-треугольник!), что означает победу второго.
  2) n составное. Первый фиксирует p – один из простых делителей числа n – и отламывает p-треугольник. Второй обязан отломить (n–p)-треугольник (иначе первый отломит от оставшегося острого угла 1-треугольник и досрочно выиграет). Получится параллелограмм со сторонами p и  n – p  (это число кратно p). Первый снова отламывает p-треугольник, и т. д. В конце концов, после хода первого останется p-треугольник. Поскольку ход второго, то согласно 1) он проиграет.


Ответ

Если число n является простым, то выигрывает второй игрок, в противном случае – первый.

Замечания

7 баллов

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

олимпиада
Название Московская математическая олимпиада
год
Номер 66
Год 2003
вариант
Класс 9
задача
Номер 4
олимпиада
Название Турнир городов
Турнир
Дата 2002/2003
Номер 24
вариант
Вариант весенний тур, основной вариант, 8-9 класс
Задача
Номер 4

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

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