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

Петя и Вася написали на доске по 100 различных натуральных чисел. Петя поделил все свои числа на Васины с остатком и выписал все 10000 получившихся остатков себе в тетрадь. Вася поделил все свои числа на Петины с остатком и выписал все 10000 получившихся остатков себе в тетрадь. Оказалось, что наборы выписанных Васей и Петей остатков совпадают. Докажите, что тогда и наборы их исходных чисел совпадают. ( С. Берлов )

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

Комментарии от администратора Комментарии от администратора №1.    
Решение. Пусть Петя записал числа $a_1 > a_2 > \ldots > a_{100},$ а Вася — $b_1 > b_2 > \ldots > b_{100}.$ Если $a_1 > b_1,$ то у Васи один из остатков будет $b_1,$ а у Пети все остатки будут меньше $b_1$ — противоречие. Аналогично приводит к противоречию предположение, что $a_1 < b_1.$ Значит, $a_1 = b_1.$
   Допустим, мы уже доказали, что $a_1 = b_1,$ $\ldots,$ $a_k = b_k$ для некоторого $k \ge 1.$ Наборы остатков от деления друг на друга чисел $a_1, \ldots, a_k$ у Пети и Васи совпадают, вычеркнем все эти остатки. Если $a_{k+1} > b_{k+1},$ то у Пети среди невычеркнутых остатков есть $k$ чисел $a_{k+1}$ — остатки от деления Петиного числа $a_{k+1}$ на все большие Васины числа, а у Васи все невычеркнутые остатки меньше $a_{k+1},$ так как там либо делимое меньше $a_{k+1},$ либо делитель не превосходит $a_{k+1}.$ Аналогично разбирается случай, когда $a_{k+1} < b_{k+1}.$ Поэтому $a_{k+1} = b_{k+1}.$ Последовательно проводя это рассуждение для $k = 1, 2, \ldots, 99$ (а знакомые с методом математической индукции сразу оформят его как индукционный переход), мы докажем утверждение задачи.