попарные НОК и число делителей

[maxal]

Докажите, что для всякого натурального числа $n$ и множества $S$ натуральных чисел таких, что НОК каждой пары элементов $S$ не превосходит $n$, существует натуральное число $m\leqslant n$ с числом делителей $\tau(m)\geqslant |S|$.

[Руст]

Это не верно, так как число делителей $\tau(m)<Cm^{1/4}\le Cn^{1/4}$. В качестве $S$ можем взять все натуральные не превосходящие $\sqrt{n}$ их количество $|S|=[\sqrt{n}]$.

[maxal]

Ага, обмануть не получилось. ;)
Предлагаю тогда найти наименьшее $n$, для которого утверждение неверно.

[EtCetera]

maxal в сообщении #617280 писал(а):

Предлагаю тогда найти наименьшее $n$, для которого утверждение неверно.

Похоже, что $n_{min}=12\,600=2^{3}\cdot 3^{2}\cdot 5^{2}\cdot 7^{1}$. Ближайшее снизу сверхсоставное число равно $10\,080$ и имеет 72 делителя. Множество $S$ в данном случае состоит из делителей числа $N=2^4\cdot 3^3\cdot 5^2\cdot 7^1$ (это НОК всех элементов $S$), в каноническом разложении которых число показателей степени, совпадающих с соответствующими показателями в разложении $N$, не превышает 1 (все остальные показатели должны быть меньше). Число таких делителей равно
$4\cdot 3\cdot 2\cdot 1\cdot \left(1+\dfrac{1}{4}+\dfrac{1}{3}+\dfrac{1}{2}+\dfrac{1}{1}\right)=24+6+8+12+24=76>72$.
Мощность множества $S$ получается с небольшим запасом, однако выбросить некоторые из них, чтобы улучшить результат $n_{min}$, вроде бы нельзя.

[maxal]

EtCetera в сообщении #617603 писал(а):

Похоже, что $n_{min}=12\,600=2^{3}\cdot 3^{2}\cdot 5^{2}\cdot 7^{1}$.

Уже $n=625$ и множество $S=\{1,2,\dots,25\}$ дают контрпример. Но и это не минимальное $n$.

[ИСН]

Комбинируя подходы: $n=520$, $S=\{1..16, 18, 22, 24, 26, 28, 30, 32, 36, 40\}$.

[maxal]

ИСН в сообщении #618170 писал(а):

Комбинируя подходы: $n=520$, $S=\{1..16, 18, 22, 24, 26, 28, 30, 32, 36, 40\}$.

Хорошо, но всё ещё не минимум.

[EtCetera]

ИСН в сообщении #618170 писал(а):

Комбинируя подходы: $n=520$, $S=\{1..16, 18, 22, 24, 26, 28, 30, 32, 36, 40\}$.

20 тоже пролазит в $S$. Если выбросить 40 и добавить 20, то $n$ снизится до 480.

[ИСН]

Вот чёрт! Перебирал руками и выронил

[EtCetera]

Можно еще улучшить это множество: $S=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 21, 24, 30, 36, 42, 48\}$ ($|S|=21$), тогда $n=336$.

[maxal]

EtCetera в сообщении #618266 писал(а):

Можно еще улучшить это множество: $S=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 21, 24, 30, 36, 42, 48\}$ ($|S|=21$), тогда $n=336$.

Ага, это оно.

[EtCetera]

1. Пусть НОК всех элементов $S$ равно $N$ и содержит $k$ различных простых чисел в своем каноническом разложении. При каком наименьшем $k$ возможно выполнение условий задачи (я имею в виду задачу о поиске наименьшего $n$)? Чему равно $n$ при этом $k$?

(Размышления вслух)

Очевидно, $k\ne 1$. По-видимому, двум тоже. Три? Для четырех выше есть пример, однако для него, вероятно, можно получить и меньшее значение $n$.

2. Пусть мы берем НОК не двух, а $m$ элементов $S$. При $m=|S|$ условие задачи, очевидно, не выполняется. Чему равно $n$ при небольших $m$? Скажем, при $m=3$...