Processing math: 100%

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


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

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

Комментарии от администратора Комментарии от администратора №1.     sol Напишем задуманные Петей числа a1,,a8 на плоскости и соединим каждые два числа линией: красной, если Петя нашел частное от деления чисел, которые она соединяет, и синей, если не нашел. Всего получится 22 красных и 6 синих линий.
   Пусть два числа, скажем, a1 и a2 (a1>a2), соединены синей линией. Тогда в шести не имеющих общих линий путях a1a3a2, a1a4a2, , a1a8a2 не больше пяти синих линий. Значит, хотя бы один из них — пусть a1a3a2 — состоит целиком из красных линий, то есть a1/a3=2n и a3/a2=2m, где n и m — целые числа. Но тогда a1/a2=(a1/a3)(a3/a2)=2n2m=2m+n. Это целая степень двойки, а так как a1>a2, то натуральная степень двойки.