Областная олимпиада по математике, 2025 год, 9 класс

$A$ файлында кез келген екі сан әртүрлі болатындай 1014 оң сан жазылған. $B$ файлына барлық $ab$ көбейтіндісі жазылады, мұнда $a$ және $b$ сандары $A$ файлындағы әртүрлі екі сан (егер бірдей көбейтінді шықса, оның тек біреуі жазылады, осылайша, $B$ файлында да барлық сандар әртүрлі). $B$ файлында ең аз дегенде неше сан бола алады? ( А. Мустафа )

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

Пусть мы имеем числа $a_1>a_2>...>a_1014$ Тогда очевидно что:

$a_1*a_2>a_1*a_3>...>a_1*a_1014>a_1014*a_2>...>a_1014*a_1013$

Значит у нас хотябы $1013+1013-1=2025$ различных чисел

Пример: $3^1;3^2;....;3^1014$

Ответ: 2025

Очень похоже на область 9 класс 2019-ого первую задачу

жиза

Докажем задачу по индукции

Наше предположение - для любого n вида 2k, если в файле A - n чисел, то в файле B, - 4k-3 числа минимум.

База вполне очевидна для 2 чисел - в файле B - 1 число

Переход

Докажем что если для 2k, все хорошо, то и для 2k+2 все хорошо.

Возьмем наши 2k+2 числа и давайте их упорядочим

$a_{2k+2}>a_{2k+1}>a_{2k}>a_{2k-1}>...>a_{1}$

Тогда для чисел $a_{2k}, ..., a_{1}$, все работает, то есть там будет $4k-3$ числа что они все разные. Причем максимальное из них = $a_{2k}a_{2k-1}$

Тогда с нашими $a_{2k+2}, a_{2k+1}$ найдем еще 4 произведения

1)$a_{2k+2}a_{2k+1}$, его точно раньше не было, так как $a_{2k+2}a_{2k+1}>a_{2k}a_{2k-1}$

2)$a_{2k+2}a_{2k}$, оно не равно первому так как все $a_{i}$ разные и также удовлетворяет неравенству $a_{2k+2}a_{2k}>a_{2k}a_{2k-1}$

3)$a_{2k+1}a_{2k}$, оно не равно первому и второму, так как все $a_{i}$ разные и также удовлетворяет неравенству $a_{2k+1}a_{2k}>a_{2k}a_{2k-1}$

4)$a_{2k+1}a_{2k-1}$, оно меньше первого второго и третьего тк

$a_{2k+2}a_{2k+1}>a_{2k+1}a_{2k-1}$

$a_{2k}a_{2k+1}>a_{2k+1}a_{2k-1}$

$a_{2k+2}a_{2k}>a_{2k+1}a_{2k-1}$

А также $a_{2k+1}a_{2k-1}>a_{2k}a_{2k-1}$

Тогда данные 4 числа будут новыми 4мя. Ну раз постоянно появляется минимум 4, то для $2k+2$, будет минимум $4k+1$ разных произведений. Ну все, просто строим пример -

${1, 2, 4..., 2^{2k-1}}$

Всего здесь произведений

${2, 4, ..., 2^{4k-3}}$

как раз $4k-3$

Тогда для 1014 ответ - 2025

А файлында $a_1$ > $a_2$ > … > $a_n$ болатындай $a_1$, $a_2$, … , $a_n$ сандары болсын. (Где $n$ = $1014$) $\Rightarrow$ $a_1a_2$ > $a_1a_3$ > $a_1a_4 > … > a_1a_n > a_2a_n > a_3a_n > … > a_{n-1}a_n$ теңсіздіктері орындалады. Поэтому в файле В есть как минимум $2n-3$ число. Мысалға А файлында {$2^0$, $2^1$, $2^2$, … $2^{n-1}$} сандары бар деп алайық. Сонда В файлында $2n-3$ сан болады олар $2^1$, $2^2$, … , $2^{2n-3}$ сандары олардан басқа жоқ значит $2025$ ответі.

Отметить множество $A_j=(a_j*a_{j+1},…,a_j*a_{1014})$. Если $j \geq 2$ тогда $a_j*a_{1014}$ больше всех элементов из $A_1$. Берем по одному элементу из всех таких множеств находим ответ.

И не забываем пример $2^1,…..,2^{1014}$