Олимпиада имени Леонарда Эйлера 2022-2023 учебный год, I тур регионального этапа

Пусть $p_1$, $p_2$, $\ldots$, $p_{100}$ — сто простых чисел, среди которых нет одинаковых. Натуральные числа $a_1$, $\ldots$, $a_k,$ большие 1, таковы, что каждое из чисел $p_1p_2^3$, $p_2p_3^3$, $\ldots$, $p_{99}p_{100}^3$, ${p_{100}}p_1^3$ равно произведению каких-то двух из чисел $a_1$, $\ldots$, $a_k.$ Докажите, что $k \ge 150$. ( И. Рубанов )

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

Решение: заметим что если взять $$a_m*a_n=p_i*p_j^3$$ , то один из $a_m и a_n$ не будет использоваться в будущем, так как

$(p_i )* (p_j^3)$ только $p_i$

$(p_i*p_j)*(p_j^2)$ никто

$(p_i*p_j^2)*(p_j)$ только $p_j$

Значит с каждой пары произведений вылазит хотя бы одно число не встретившееся в будущем

+100 чисел как минимум.

Теперь, с каждого произведения при минимуме, выйдет ещё и одно простое число которое мы можем использовать максимум в двух произведениях а значит +50 чисел ещё. А значит чисел как минимум 150. Доказано