Loading [MathJax]/jax/output/SVG/jax.js

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


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

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

  3
2 месяца 26 дней назад #

Пусть мы имеем числа a1>a2>...>a1014 Тогда очевидно что:

a1a2>a1a3>...>a1a1014>a1014a2>...>a1014a1013

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

Пример: 31;32;....;31014

Ответ: 2025

  0
2 месяца 26 дней назад #

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

  0
2 месяца 26 дней назад #

жиза

  2
2 месяца 26 дней назад #

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

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

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

Переход

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

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

a2k+2>a2k+1>a2k>a2k1>...>a1

Тогда для чисел a2k,...,a1, все работает, то есть там будет 4k3 числа что они все разные. Причем максимальное из них = a2ka2k1

Тогда с нашими a2k+2,a2k+1 найдем еще 4 произведения

1)a2k+2a2k+1, его точно раньше не было, так как a2k+2a2k+1>a2ka2k1

2)a2k+2a2k, оно не равно первому так как все ai разные и также удовлетворяет неравенству a2k+2a2k>a2ka2k1

3)a2k+1a2k, оно не равно первому и второму, так как все ai разные и также удовлетворяет неравенству a2k+1a2k>a2ka2k1

4)a2k+1a2k1, оно меньше первого второго и третьего тк

a2k+2a2k+1>a2k+1a2k1

a2ka2k+1>a2k+1a2k1

a2k+2a2k>a2k+1a2k1

А также a2k+1a2k1>a2ka2k1

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

1,2,4...,22k1

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

2,4,...,24k3

как раз 4k3

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

пред. Правка 2   0
2 месяца 24 дней назад #

А файлында a1 > a2 > … > an болатындай a1, a2, … , an сандары болсын. (Где n = 1014) a1a2 > a1a3 > a1a4>>a1an>a2an>a3an>>an1an теңсіздіктері орындалады. Поэтому в файле В есть как минимум 2n3 число. Мысалға А файлында {20, 21, 22, … 2n1} сандары бар деп алайық. Сонда В файлында 2n3 сан болады олар 21, 22, … , 22n3 сандары олардан басқа жоқ значит 2025 ответі.

  0
2 месяца 22 дней назад #

Отметить множество Aj=(ajaj+1,,aja1014). Если j2 тогда aja1014 больше всех элементов из A1. Берем по одному элементу из всех таких множеств находим ответ.

И не забываем пример 21,..,21014