Олимпиадная задача Хачатуряна А.В. про шоколадку и треугольники для 7-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 является простым, то выигрывает второй игрок, в противном случае – первый.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь