ИТМО-2024. Красивая задача на делители
ฝัง
- เผยแพร่เมื่อ 29 ก.ย. 2024
- Уже в эту субботу запустим Перезапуск курса Перечень, Открытая неделя по комбинаторике и ТЧ: pereche... -- присоединяйтесь бесплатно!
Курс Перечень 24/25, подготовка к технике (Физтех, ПВГ, Ломоносов, Росатом): 3.shkolkovo.on...
Курсы ВсОШ (подготовка к классическим олимпиадам, ММО, Высшая Проба и тд):
shkolkovo.onlin... -- 8-9 класс
shkolkovo.onlin... -- 10-11 класс
Телеграм Дмитрия Алексеевича со всеми анонсами: t.me/DA_shkolkovo
Все наши текущие акции и скидки👉🏻 3.shkolkovo.on...
Отзывы наших учеников👉🏻 3.shkolkovo.on...
Группа ВК по олимпиадной математике 👉🏻 pereche...
Наши каналы:
✔️Олимпиадная математика с ДА: shkolkovo.info...
✔️ Физика с АВ: shkolkovo.info...
✔️ Подготовка к ОГЭ ко всем предметам: shkolkovo.info...
✔️ Обществознание с МВ: shkolkovo.info...
✔️ Биология с ЕВ: shkolkovo.info...
✔️ Биология и химия Мутаген: shkolkovo.info...
✔️ Обществознание и история Histructor: shkolkovo.info...
✔️ Изи-ЕГЭ Математика с Али: shkolkovo.info...
✔️Математика с МО и русский язык с ТА (Основной канал Школково):
shkolkovo.info...
✔️Максим Коваль. Влог учителя математики: shkolkovo.info...
✔️Экономика. Школково Олимпиады: shkolkovo.info...
✔️Физика ОГЭ с ГК : shkolkovo.info...
✔️История с АВ: shkolkovo.info/pf
✔️Английский язык с СС: shkolkovo.info/pg
✔️Информатика БУ: shkolkovo.info/tn
✔️Обществознание ОГЭ: shkolkovo.info/xj
Кстати говоря, эта задача была ещё в 9 классе на этой же олимпиаде в этом году (9.2)
Решил её)
Задачка для неолимпиадного школьника или для школьной олимпиады очень хорошая, понятная, не заумная.
Ну как бы формально нужно было рассмотреть ситуацию, когда подбор двух дополнительных делителей до 120 производится не по схеме p; p×2 , а по схеме р, q - то есть добавляем два простых числа величиной больше чем 120/2 (например, 41 и 43). И показать, что для этой схемы подбора 120 также будет 18ым делителем, но n будет выше, чем 4920
Очень остроумная задача. Красивая.
А зачем отдельно рассматривать случаи 2, 3, 5? Почему это не подходит под общий случай?
Логика p,2p,3p дает сбой, например есть 16, но нет 32; есть 9, но нет 27. C пятеркой все проходит без изменений. [только не говорите, что 16 и 9 - составные числа :))))]
халява
как говорил Райгородский -- Испытал катарсис
Ура! задача не на клеточки 🤡
Ура, не геома (геома - зло)🎉
Халява
Если p>=61, то добавится всего 1 делитель(т.к. 61*2>120)=>41
Нужно было n минимальное найти, а не максимальное
На самом деле сверху n не ограничено: можно добавлять простые множители >120, и они никак не повлияют на кол-во делителей до 120 (ещё можно было кстати добавлять не один простой множитель >40, а добавить 2 простых множителя >60 и < 120 (например, 61 и 67), тогда тоже только 2 делителя
что-то сильно похоже на ту самую ирландскую олимпиаду
да-да, есть такое)
Спасибо! Получил удовольствие от задачи
Решил кодом на питоне. А вот правило про 41 не понял совсем. Откуда именно 41
for x in range(100, 10**5):
s = set()
for i in range(1, int(x**0.5)+1):
if x % i == 0:
s.add(x//i)
s.add(i)
s = sorted(list(s))
if len(s)>=18 and s[17] == 120:
print(s,x)
break
Смотри, Дмитрий Алексеевич выяснил, что у данного n уже не меньше 16-и делителей, а 120 - это именно 18-й делитель (по условию). То есть, наименьшее n = 2 * 2 * 2 * 3 * 5 * k, где k - простое число. После проверки k = 2 или 3 или 5, Дмитрий выяснил, что в таких случаях 120 будет НЕ 18-ым делителем числа n, соответственно чтобы 120 было именно 18-ым, надо поискать другие простые числа (7, 11, 13, ...), но в таком случае у нас будут появляться хотя бы делители 2 * k, 3 * k, 5 * k и k (k делитель в любом случае появится). Если у нас 2 * k и 3 * k будет меньше 120, то у нас 120 будет уже хотя бы 19-ым делителем n, а не 18-ым (делителей 15 + 1 (делитель k) + 1 (делитель 2k) + 1 (делитель 3k), итого у нас уже будет 18 делителей как минимум перед 120). Заметим, что 3k > 2k и при k < 41 (натуральном k) 3k
залява
Интересно, число 120 имеет только 16 делителей, но по условию у него 18. Из это 41,82. А если максимум было бы d17=120? 113 было?
По условию 120 - это 18 делитель числа n по возрастанию. Если решать задачу, где 120 - 17ый делитель числа n, то к выписанным на доске делителям должен добавиться ровно 1 делитель < 120
По таким же рассуждениям нельзя увеличивать степень 2, 3 и 5, поэтому надо добавлять ещё простой множитель
Если добавить простой множитель р=60, значит р=61 - минимальное р
И число n=61•120 - подходит, действительно 120 будет его 17ым делителем
@@TiLTovozzik лучше меня ответили!)
@@TiLTovozzik это же минимум а я хотел максимум
@@BirzhanBerikkhanovмаксимум не ограничен
@@BirzhanBerikkhanovвообще максимум не ограничен, мы можем домножать n на простые множители > 120, и это никак не будет влиять на количество делителей, которые < 120