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

В файл $A$ записаны 1014 попарно различных положительных чисел. В файл $B$ записаны все произведения $ab$, где $a$ и $b$ — два различных числа из файла $A$ (если для нескольких пар результат совпадает, то он записывается в файл $B$ ровно один раз; таким образом, все числа в файле $B$ попарно различны). Какое наименьшее количество чисел может содержать файл $B$? ( А. Мустафа )

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

Очень похоже на область 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}$

Ответ: $2025$. Докажем по индукции.

Предположение индукции: для любого набора положительных чисел $a_1, a_2, \ldots , a_n (n \geq 2)$ не менее $1+2(n-2)$ различных чисел в файле $B$.

База индукции: $n=2$, очевидно верна.

Переход индукции: Рассмотрим набор чисел $a_1, a_2, \ldots , a_{n+1}$. Б.О.О $a_{n+1} > a_n > \ldots > a_1$. Тогда по предположению индукции для набора $a_n, a_{n-1}, \ldots, a_1$ не менее $1+2(n-2)$ различных произведений. Но при добавлении $a_{n+1}$ в файл добавятся ещё как минимум числа $a_{n+1}a_n, a_{n+1}a_{n-1}$. Тогда в файле теперь как минимум $1+2(n-1)$ чисел. Переход доказан.

Тогда при $n=1014$, ответ $2025$.

Пример $a_i = q^i, q≠1, q>0$.