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

Числитель каждой из 48 дробей равен одному из чисел 2, 3, $\dots$, 49, знаменатель — тоже, причём каждое из этих 48 чисел встречается как среди числителей, так и среди знаменателей. Докажите, что либо одна из этих дробей равна целому числу, либо из них можно выбрать не более 25 дробей, произведение которых — целое число.

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

Комментарии от администратора Комментарии от администратора №1.    
Решение. Рассмотрим дробь $a_1/2$ со знаменателем 2. Если $a_1$ четно, то мы уже получили целое число. В противном случае умножим $a_1/2$ на дробь $a_2/a_1$, результат — на дробь $a_3/a_2$ и так до тех пор, пока очередной числитель $a_n$ не станет чётным (такое когда-то случится, потому что числители не могут повторяться). После этого в произведении получится целое число $a_n/2$. Поскольку различных нечётных знаменателей у нас 24, мы перемножили не больше 25 дробей.