Леонард Эйлер атындағы олимпиада, 2018-2019 оқу жылы, қорытынды кезеңнің 2-ші туры

Тақтада 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. Противоречие.