Олимпиада имени Леонарда Эйлера 2018-2019 учебный год, II тур заключительного этапа

На доске написаны числа 1, 2, $\ldots,$ 1000. Разрешается стереть любые два числа $a$ и $b$ и записать вместо них числа $ab$ и $a^2+b^2.$ Можно ли такими операциями добиться, чтобы среди чисел, написанных на доске, было хотя бы 700 одинаковых? ( М. Антипов )

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

Комментарии от администратора Комментарии от администратора №1.    
Ответ. Нельзя.
Решение. Проследим за количеством чисел на доске, кратных трём. Заметим, что если оба числа $a$, $b$ делились на 3, то и оба новых числа — тоже, если ровно одно из чисел $a,$ $b$ было кратно трём, то $ab$ кратно трём, а $a^2+b^2$ — нет. Наконец, если оба числа $a$, $b$ не делились на 3, то и $a^2+b^2$ даёт остаток 2 при делении на 3, т. е. чисел, кратных трём, и не появляется. Таким образом, общее количество чисел, кратных трём, не меняется. Теперь заметим, что исходно таких чисел было 333 (3, 6, $\ldots$, 999), а если бы после нескольких операций на доске оказалось хотя бы 700 равных чисел, то чисел, кратных трём, было бы либо не менее 700, либо не более 300. Противоречие.