Условие
По кругу записаны n целых неотрицательных чисел. За один ход каждое число одновременно заменяют модулем разности этого числа и следующего за ним по часовой стрелке (последнее число — модулем разности с первым). а) Пусть n = 4. Могут ли записанные числа, не все из которых равны между собой, впервые стать равными нулю ровно после 6 ходов? б) При n = 5 записаны числа, не все из которых равны между собой. Может ли через несколько ходов оказаться, что все числа равны нулю? в) При n = 8 каждое из записанных чисел равно 0 или 1, и не все они нулевые. Найдите наибольшее возможное число ходов, после которого все числа впервые станут равными нулю.
Подсказка
В п. б посмотрите, какой набор мог быть непосредственно перед набором из одних нулей и перед ним.
Для чисел 0 и 1 сравните |a − b| с остатком от деления a + b на 2.
Показать ответ
а) да, например 1, 3, 8, 15; б) нет; в) 8
Пошаговое решение
- Пункт а: пример
Запишем по часовой стрелке 1, 3, 8, 15: 1, 3, 8, 15 → 2, 5, 7, 14 → 3, 2, 7, 12 → 1, 5, 5, 9 → 4, 0, 4, 8 → 4, 4, 4, 4 → 0, 0, 0, 0. Например, первое число после первого хода |1 − 3| = 2, последнее |15 − 1| = 14. Нули впервые получены ровно после 6 ходов. Ответ — да.
- Пункт б: смотрим на ход назад
Пусть нули впервые получились после t ходов. Равенства |xᵢ − xᵢ₊₁| = 0 при всех i означают, что перед этим все числа были равны одному c. Если t = 1, то равны были исходные числа — это исключено условием, так что c > 0 и у набора (c, c, c, c, c) есть предыдущий набор x₁, …, x₅ с |xᵢ − xᵢ₊₁| = c, то есть xᵢ₊₁ − xᵢ = ±c.
- Пункт б: противоречие
Сумма разностей по кругу (x₂ − x₁) + (x₃ − x₂) + … + (x₁ − x₅) = 0, но это сумма пяти слагаемых ±c, то есть c, умноженное на сумму пяти чисел ±1, которая нечётна и не равна нулю. Противоречие — ответ нет.
- Пункт в: оценка
Для чисел 0 и 1 модуль разности равен остатку суммы при делении на 2, поэтому числа остаются нулями и единицами, а после хода каждое число заменяется суммой (по модулю 2) себя и следующего. Если через T ходов каждое число превращается в сумму себя и числа, стоящего на T мест дальше по кругу, то, повторив эти T ходов, получим через 2T ходов: само число + 2·(число через T мест) + (число через 2T мест), то есть по модулю 2 сумму себя и числа через 2T мест. Так получаем это свойство для T = 1, 2, 4, 8, а через 8 ходов число на 8 мест дальше — оно само, и сумма 2aᵢ чётна, то есть равна 0. Значит, нули появятся не позже чем через 8 ходов.
- Пункт в: пример и типичная ошибка
Начнём с 1, 0, 0, 0, 0, 0, 0, 0: ходы дают 10000001, 10000010, 10000111, 10001000, 10011001, 10101010, 11111111 и только восьмой ход — 00000000. Значит, наибольшее число ходов 8. Типичная ошибка — проверять лишь несколько наборов и не доказывать, что больше 8 ходов не бывает.
Ответ: а) да, например 1, 3, 8, 15; б) нет; в) 8
Критерии оценивания (4 балла)
- 4
- Верно получены все четыре результата: приведён набор (например, 1, 3, 8, 15) и проверено, что нули впервые появляются ровно после 6 ходов (п. а); доказательство через обратный ход и нечётность числа слагаемых ±c, что при n = 5 нули не появятся (п. б); оценка «не более 8 ходов» через сложение по модулю 2 (п. в); пример набора, требующего 8 ходов (п. в).
- 3
- Верно получены три результата из четырёх: например, пункты а и б и пример набора 1, 0, 0, 0, 0, 0, 0, 0 с восемью ходами, но не доказано, что больше 8 ходов не бывает.
- 2
- Верно получены два результата из четырёх: например, приведён и проверен пример в п. а и доказан п. б, а в п. в нет ни оценки, ни примера.
- 1
- Верно получен один результат из четырёх: например, только верный пример набора 1, 3, 8, 15 с моделированием шести ходов в п. а без решения остальных пунктов.
- 0
- Не выполнены условия начисления баллов по этой учебной рубрике.