Олимпиадная задача: 10 последовательных чисел и замены на доске (Агаханов Н. Х.)
Задача
Изначально на доске записаны 10 последовательных натуральных чисел. За одну операцию разрешается выбрать любые два числа на доске (обозначим их a и b) и заменить их на числа a² – 2011b² и ab. После нескольких таких операций на доске не осталось ни одного из исходных чисел. Могли ли там опять оказаться 10 последовательных натуральных чисел (записанных в некотором порядке)?
Решение
Лемма. Для любого натурального k, количество чисел на доске, кратных k, не уменьшается.
Доказательство. Если в операции участвовали числа a и b, одно из которых кратно k, то их произведение также кратно k. Более того, если оба исходных числа были кратны k, то и число a² – 2011b² кратно k. Предположим, что после нескольких операций снова получились десять последовательных натуральных чисел, причём каждое из исходных чисел участвовало хотя бы в одной операции.
И в начальной и конечной ситуациях есть по пять чётных чисел, и по одному числу, кратному 10. Значит, и в любой промежуточный момент на доске было ровно пять чётных чисел и одно число, кратное 10.
Среди исходных 10 чисел было число a, оканчивающееся на 5. Рассмотрим первую операцию, в которой оно участвовало; пусть b – второе число, участвовавшее в этой операции. Если b нечётно, то число a² – 2011b² чётно, и количество чётных чисел увеличилось. Если b чётно, но не кратно 10, то на доске появилось новое число (ab), кратное 10. Если b делится на 10, то в операции участвовали два числа, кратных 5. В её результате на доске появились два числа, кратных 25. Но в конечной ситуации (10 последовательных натуральных чисел) двух таких чисел нет.
Итак, во всех случаях мы пришли кротиворечию.
Ответ
Не могли.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь