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

   Решение

Темы:    [ Теория игр (прочее) ] [ Разные задачи на разрезания ] [ Алгоритм Евклида ] [ Простые числа и их свойства ]

Сложность: 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 баллов

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