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

$p_1$, $p_2$, $\ldots$, $p_{100}$ жай сандарының ешқандай екеуі тең емес. 1-ден үлкен натурал $a_1$, $\ldots$, $a_k,$ сандары үшін, $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. Доказано