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

Петя мен Васяның әрқайсысы тақтаға 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$ (а знакомые с методом математической индукции сразу оформят его как индукционный переход), мы докажем утверждение задачи.