Олимпиада имени Леонарда Эйлера 2018-2019 учебный год, III тур дистанционного этапа

Петя 8 әртүрлі сандарды ойластырды, сосын екі-екіден сандарды алып, үлкенін кішісіне бөле бастады. Ол 28 мүмкін бөліндінің 22-ін тапты, сонда сол 22 бөлінділердің әрқайсысы 2-нің натурал дәрежесі болып шыққан. Қалған 6 бөлінділердің де әрқайсысы 2-нің натурал дәрежесі екенін дәлелдеңіз. (2-нің натурал дәрежесі дегеніміз, $2^n$ түріндегі сан, бұл жерде $n$ — натурал сан.) ( И. Рубанов )

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

Комментарии от администратора Комментарии от администратора №1.     sol Напишем задуманные Петей числа $a_1, \ldots, a_8$ на плоскости и соединим каждые два числа линией: красной, если Петя нашел частное от деления чисел, которые она соединяет, и синей, если не нашел. Всего получится 22 красных и 6 синих линий.
   Пусть два числа, скажем, $a_1$ и $a_2$ $(a_1 > a_2),$ соединены синей линией. Тогда в шести не имеющих общих линий путях ${a_1 - a_3 - a_2,}$ ${a_1 - a_4 - a_2,}$ $\ldots,$ ${a_1 - a_8 - a_2}$ не больше пяти синих линий. Значит, хотя бы один из них — пусть ${a_1 - a_3 - a_2}$ — состоит целиком из красных линий, то есть $a_1/a_3 = 2^n$ и $a_3/a_2 = 2^m,$ где $n$ и $m$ — целые числа. Но тогда $a_1/a_2 = (a_1/a_3)(a_3/a_2) = 2^n \cdot 2^m = 2^{m+n}.$ Это целая степень двойки, а так как $a_1 > a_2,$ то натуральная степень двойки.