Ну как бы формально нужно было рассмотреть ситуацию, когда подбор двух дополнительных делителей до 120 производится не по схеме p; p×2 , а по схеме р, q - то есть добавляем два простых числа величиной больше чем 120/2 (например, 41 и 43). И показать, что для этой схемы подбора 120 также будет 18ым делителем, но n будет выше, чем 4920
Решил кодом на питоне. А вот правило про 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
Логика p,2p,3p дает сбой, например есть 16, но нет 32; есть 9, но нет 27. C пятеркой все проходит без изменений. [только не говорите, что 16 и 9 - составные числа :))))]
Нужно было n минимальное найти, а не максимальное На самом деле сверху n не ограничено: можно добавлять простые множители >120, и они никак не повлияют на кол-во делителей до 120 (ещё можно было кстати добавлять не один простой множитель >40, а добавить 2 простых множителя >60 и < 120 (например, 61 и 67), тогда тоже только 2 делителя
По условию 120 - это 18 делитель числа n по возрастанию. Если решать задачу, где 120 - 17ый делитель числа n, то к выписанным на доске делителям должен добавиться ровно 1 делитель < 120 По таким же рассуждениям нельзя увеличивать степень 2, 3 и 5, поэтому надо добавлять ещё простой множитель Если добавить простой множитель р=60, значит р=61 - минимальное р И число n=61•120 - подходит, действительно 120 будет его 17ым делителем
@@BirzhanBerikkhanovвообще максимум не ограничен, мы можем домножать n на простые множители > 120, и это никак не будет влиять на количество делителей, которые < 120
Кстати говоря, эта задача была ещё в 9 классе на этой же олимпиаде в этом году (9.2)
Решил её)
Задачка для неолимпиадного школьника или для школьной олимпиады очень хорошая, понятная, не заумная.
Ну как бы формально нужно было рассмотреть ситуацию, когда подбор двух дополнительных делителей до 120 производится не по схеме p; p×2 , а по схеме р, q - то есть добавляем два простых числа величиной больше чем 120/2 (например, 41 и 43). И показать, что для этой схемы подбора 120 также будет 18ым делителем, но n будет выше, чем 4920
Решил кодом на питоне. А вот правило про 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
Очень остроумная задача. Красивая.
А зачем отдельно рассматривать случаи 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 делителя
что-то сильно похоже на ту самую ирландскую олимпиаду
да-да, есть такое)
Спасибо! Получил удовольствие от задачи
залява
Интересно, число 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