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

Петя задумал 8 различных чисел, а потом стал выбирать из них по два и делить большее на меньшее. Он нашел 22 из 28 возможных частных, и они оказались натуральными степенями двойки. Докажите, что 6 оставшихся частных — тоже натуральные степени двойки. (Натуральная степень двойки — это 2 в степени, показатель которой равен натуральному числу.) ( И. Рубанов )

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

Комментарии от администратора Комментарии от администратора №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,$ то натуральная степень двойки.