Неоперившиеся числа

[Ktina]

Возможно, уже было. Но, как говорится, ученье - свет, а повторение - мать его!

Натуральное число назовем неоперившимся, если множество всех его натуральных делителей можно разбить на два непустых непересекающихся подмножества с одинаковым количеством элементов и одинаковой их суммой. Доказать, что неоперившихся чисел бесконечно много.

[gris]

Имеются в виду все делители? То есть, например, $24$ число неоперившееся?
Ибо $1+2+3+24=4+6+8+12$.
Но не ошиблись ли Вы? Мне кажется, что именно эти числа оперились, а вот остальные нет. Хотя, возможно, у Вас другая трактовка этого слова

[Руст]

Если есть одно решение 24, то их бесконечно много.
Пусть $(6,n)=1$. Тогда делители числа
24n так же можно разделить на две части, в соответствии с делением на делители числа 24.

[Ktina]

gris
Руст
Моё решение также связано с числом 24, а именно - $24p$, где $p$ - простое число, большее 3.
У такого числа ровно 16 делителей, сумма которых равна $60p+60$, причём всегда можно выбрать 8 делителей с суммой $30p+30$. Это будут:

$$1,\quad 2,\quad 3,\quad 24,\quad p,\quad 2p,\quad 3p\quad\text{и}\quad 24p$$

[Руст]

Ваше решение не полное. К тому же чисто переборное решение не является математической задачей.
Докажем некоторые свойства.

1. Если М является решением, то $nM$ является так же решением для любого натурального n, взаимно простого с M.
Док-во. Пусть $m_1,m_2,...,m_k, 2k=\tau(M)$ делители М с суммой $\sum_i m_i=\frac 12 \sigma(M)$.
Пусть $d_j$ набор всех делителей n. Выделим половину всех делителей числа $nM$:
$\{m_id_j\}$. Их количество $\frac 12 \tau(M)*\tau(n)=\frac 12 \tau(nM)$ (т.е. ровно половина), их сумма
$\sum_{i,j}m_id_j=\frac 12 \sigma(M)*\sigma(n)=\frac 12 \sigma(nM)$.
В док-ве использовались мультипликативность функций $\tau(n),\sigma(n)$.

2. Если $М=2^kM_1$, где $M_1-$ нечетное и $M$ является решением, то 2М так же является решением.
Док-во. Пусть $M=2^kM_1$, где $M_1$ нечетное. Заметим, что $M_1\not =l^2$
(степень двойки не является решением и произведение квадрата на степень двойки так же не является решением)
и соответственно $\sigma(M_1), \tau(M_1)$ - четные. Тогда любой делитель М есть
$2^id$, где d нечетное - делитель $M_1$. Для каждого такого нечетного делителя определим
число $s(d,k)=\sum_{i|2^id\in N_1}2^i$ - отношение суммы всех делителей вида $2^id$ входящих в первое множество на d.
Числа $s(d,k)$ могут быть произвольными натуральными числами, не превосходящими $2^{k+1}-1$. Обозначим количество ненулевых цифр в двоичном исчислении
числа $s(d,k)$ через $m(d,k)$. Тогда условие того, что M является решением выражается двумя уравнениями относительно s(d):

$$\sum_{d|M_1} m(d,k)=\frac 12 (k+1)\tau(M_1), \sum_{d|M_1} s(d,k)=\frac 12 (2^{k+1}-1)\sigma(M_1).$$

Чтобы получить решение для числа $2M$ нам надо выбрать числа $s(d,k+1)$ так, чтобы
$\sum_{d|M_1} s(d,k+1)=2\sum_{d|M_1}s(d,k)+\frac 12 \sigma(M_1)=\sum_{d|M_1}s(d,k)+2^k\sigma(M_1),$
$ \sum m(d,k+1)=\sum m(d,k)+\frac 12 \tau(M_1).$
Разделим делители числа $M_1$ на подмножества с одинаковым количеством членов $\frac 12 \tau(M_1)$. Тогда, если их суммы одинаковы мы
определим $s(d,k+1)=2s(d,k)$ для элементов одного множества и $s(d,k+1)=2s(d,k)+1$ для другого подмножества решает вопрос.
А так нам надо изменить $s(d,k+1)=2s(d,k)+s'(d)$ так, чтобы
$\sum s'(d)=\frac{1}{2}\sigma(M_1)$ при этом увеличивая суммарное количество ненулевых цифр только на $\frac 12 \tau(M_1)$.
Это всегда можно сделать.
Вообще таких чисел очень много. Есть подозрение, что для любого нечетного числа n, не являющегося квадратом найдется небольшое
$\alpha(n)$, что все числа $2^kn, k\ge \alpha(n)$ удовлетворяют этому свойству.

[Ktina]

(Оффтоп)

Руст в сообщении #832516 писал(а):

Ваше решение не полное.

Ktina в сообщении #832133 писал(а):

Доказать, что неоперившихся чисел бесконечно много.

Вот если бы в задаче требовалось найти все такие числа, ...

[Руст]

Я могу доказать, что для любого нечетного числа $n$, не являющегося квадратом,
все числа вида $2^kn$ неоперившиеся числа, начиная с некоторого k.
Это само по себе интересная математическая задача.
Похоже, что плотность таких чисел равно 1. Т.е. если обозначить количество чисел, не являющихся
таковыми и меньших n через $\kappa(n)$, то предел $\lim_{n\to \infty}\frac{\kappa(n)}{n}=0$.

[Ktina]

Руст
А доказательство у Вас длинное? Было бы любопытно его увидеть...

[Руст]

Ktina в сообщении #832908 писал(а):

Руст
А доказательство у Вас длинное? Было бы любопытно его увидеть...

Идея доказательства заключается в следующем.
Пусть $M$ нечетное число, не являющееся квадратом. Соответственно $\tau(M),\sigma(M)$ - четные числа.
Рассмотрим подмножества делителей числа M $\Sigma=\{\sigma_i\}$. Каждый элемент $\sigma_i$ является делителем.
Рассмотрим число $2^{k-1}M$. Разделим делители этого числа на две равных подмножества.
Это определяет разделение для каждого разряда i разделение делителей числа M на две части $\sigma_i$ и его дополнение.
Условие того, что число $2^{k-1}M$ является оперившимся числом записывается в виде двух соотношений:

$$\sum_{i=0}^{k-1}2^is(\sigma_i)=0, \sum_{i=0}^{k-1} |\sigma_i|=\frac 12 k\tau(M),$$

где через $s(\sigma_i)$ обозначено $\sum_{d\in \sigma_i} d -\frac 12 \sigma(M).$
Обозначим через $A_k$ минимум величины

$$A_k=min |S_k|, S_k=\sum_{i=0}^{k-1}2^is(\sigma_i)$$

по всем разбиениям на подмножества $\sigma_i, i<k$, таким, что выполняется $\sum_{i=0}^{k-1} |\sigma_i|=\frac 12 k\tau(M).$
Если $A_1=0$, то все $A_k$ равны нулю, для этого достаточно брать все $\sigma_i$ из разбиения при $A_1$.
Если $A_k=0=A_m$ для взаимно простых k,m, то $A_{ak+bm}=0$, т.е. все $A_i=0$ начиная с числа $km-k-m$.
Покажем как можно уменьшить $A_i$. Если взять все $\sigma_i=\sigma, i=0,1,...,k-2$ взять равными кроме старшего разряда, а в старшем разряде $\sigma_{k-1}$ дополнение множества $\sigma$, то сумма $S_k=s(\sigma)(1+2+...+2^{k-2})-2^{k-1}s(\sigma)=-s(\sigma)$.
Отсюда следует, что $A_k\le A_1$. Допустим, что $\sigma$ давало минимальное положительное значение при $k=1$ среди разбиений, не содержащих 1.
Тогда добавив на соответвующих разрядах 1 в $\sigma_i$ получим нулевую сумму. Однако при этом мы нарушили условие на выбор количества делителей, увеличив их на количество ненулевых цифр числа $s(\sigma)$. Взяв всюду дополнения к полученным разбиениям получим другую нулевую сумму с нарушением количества делителей в другую сторону. Совместив их получим число $2^{2k}M$ без нарушений.

[Ktina]

Руст
Спасибо!