Олимпиада имени Леонарда Эйлера 2020-2021 учебный год, II тур регионального этапа

В квадратной таблице $2021 \times 2021$ стоят натуральные числа. Можно выбрать любой столбец или любую строку в таблице и выполнить одно из следующих действий: 1) Прибавить к каждому выбранному числу 1. 2) Разделить каждое из выбранных чисел на какое-нибудь натуральное число. Можно ли за несколько таких действий добиться того, чтобы каждое число в таблице было равно 1? ( М. Дидин )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     В квадратной таблице $2021 \times 2021$ стоят натуральные числа. Можно выбрать любой столбец или любую строку в таблице и выполнить одно из следующих действий: 1) Прибавить к каждому выбранному числу 1. 2) Разделить каждое из выбранных чисел на какое-нибудь натуральное число. Можно ли за несколько таких действий добиться того, чтобы каждое число в таблице было равно 1? (М. Дидин)
Ответ. Можно.
Решение. Докажем, что можно сделать первые $k$ столбцов одинаковыми, индукцией по $k.$ База — $k = 1.$ Переход. Пусть первые $k$ столбцов одинаковы. Будем прибавлять к ${(k+1)}$-ому столбцу 1 до тех пор, пока каждое число в нём не станет больше, чем соседнее число в $k$-ом столбце. Теперь рассмотрим $m$-ую строку. Пусть на пересечении её с $k$-ым столбцом стоит $a$, а на пересечении с ${(k+1)}$-ым столбцом — $b > a.$ Пусть $a$ при делении на $b-a$ дает остаток $r.$ Прибавим к $m$-ой строке $b-a-r$ единиц. Теперь первые $k+1$ чисел в ней делятся на $b-a.$ Далее прибавим к каждому из столбцов, начиная с ${(k+2)}$-го, по нескольку единиц так, чтобы все оставшиеся числа $m$-ой строки тоже стали делиться на $b-a,$ после чего разделим $m$-ую строку на $b-a.$ Заметим, что в итоге первые $k$ чисел $m$-ой строки остались равными, а ${(k+1)}$-ое ее число стало на единицу больше каждого из них. Проделаем такую операцию с каждой строкой таблицы. Поскольку к первым $k+1$ столбцам на каждом этапе 1 добавляется одинаковое количество раз, окажется, что первые $k$ столбцов, по-прежнему равны, а ${(k+1)}$-ый — на 1 больше. Прибавив по 1 к первым $k$ столбцам, завершим переход индукции. Когда все столбцы таблицы равны и в каждой строке все элементы одинаковы, завершаем решение делением каждой строки на её элемент.