Количество наборов

[DonVito]

Дано множество натуральных чисел $\{1,2,3, ... , n\}$. Известно, что количество всех различных наборов (подмножеств) равно $2^n$. Сколько существует наборов, сумма элементов которых делится без остатка на два, на три ? (сумму элементов пустого множества берем за 0)

Пока что методом тыка и перебором для $n=1,2, ..., 5$ заметил только то, что количество наборов, сумма элементов которых кратна 2, равно $2^{n-1}$. Обобщить и доказать эту гипотезу математически не могу.
Что касается тройки, то для всех n, кратных 3, могу найти только количество трехэлементных подмножеств, сумма элементов которых делится без остатка на 3.
Например, возьмем конечное множество, элементы которого являются натуральными числами от 1 до 300. Пусть $A_j$ - множество всех натуральных чисел от 1 до 300, что дают остаток j при делении на 3. Тогда $N(A_j)=100$, где $0\leqslant j \leqslant 2$. Если a, b, c - три натуральных числа в пределах от 1 до 300, то $a+b+c$ делится на 3 только в двух случаях: а) каждое из чисел a, b, c или из множества $A_0$, либо из $A_1$, либо из $A_2$; б) одно из чисел a, b, c принадлежит множеству $A_0$, другое - $A_1$, последнее - $A_2$. Число трехэлементных подмножеств множества $A_j$, $0\leqslant j \leqslant 2$ равно $C^3_{100}$. Для каждого выбора числа a из $A_0$, b из $A_1$, c из $A_2$, мы получаем трехэлементное подмножество, для которого сумма $a+b+c$ делится на 3. Таким образом, общее количество трехэлементных подмножеств $\{a, b, c\}$, таких, что сумма $a+b+c$ делится на 3, равно:

$$3C^3_{100}+100^3=1485100$$

Для двухэлементных подмножеств должны выполнятся такие условия: а) два элемента принадлежат множеству $A_0$; б) первое число принадлежит множеству $A_1$, второе - $A_2$. Тогда сумма элементов таких двухэлементных подмножеств делится на 3.
А что делать, когда количество элементов в наборе больше трех и n не кратно 3, какие условие можно наложить или каким еще способом можно найти количество подмножеств множества $\{1, 2, 3, ..., n\} $, суммы элементов которых кратны 3?

[provincialka]

А вы попробовали выписать эти подмножества для малых $n$? Понаблюдайте, может, появится какая-нибудь гипотеза.

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: не приведены попытки решения, формулы не оформлены $\TeX$ом, бессодержательный заголовок

DonVito
Приведите попытки решения, укажите конкретные затруднения.
Измените заголовок темы на более содержательный.
Наберите все формулы и термы $\TeX$ом правильно.
Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

[Toucan]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[DonVito]

Пробовал. Пускай $\alpha_n$ - количество различных наборов множества $N_n$ натуральных чисел, тогда $\alpha_{n,3}$ - количество наборов, суммы элементов которых кратны 3. Выписав вручную все наборы для $n=1,2,...,6$, их у меня вышло 126, я получил $\alpha_{1,3}=1, \alpha_{2,3}=2, \alpha_{3,3}=4, \alpha_{4,3}=6, \alpha_{5,3}=12, \alpha_{6,3}=24$. Интуитивно чую, что где-то есть какая-то зависимость либо закономерность, но не могу понять где, что и к чему

[Sonic86]

Пусть подмножество содержит $k$ элементов, $k=0,...,n$. Выпишите сравнение, определяющее, что сумма чисел подмножества делится на $m$. Решите это сравнение. Найдите число его решений, просуммируйте по $k$.

[maxal]

Примените мультисекцию к ряду

$$(1+x)(1+x^2)\cdots (1+x^n).$$

[DonVito]

Sonic86 в сообщении #820227 писал(а):

Пусть подмножество содержит $k$ элементов, $k=0,...,n$. Выпишите сравнение, определяющее, что сумма чисел подмножества делится на $m$. Решите это сравнение. Найдите число его решений, просуммируйте по $k$.

я не совсем понял как это сделать

[Sonic86]

DonVito в сообщении #820265 писал(а):

я не совсем понял как это сделать

Что именно непонятно? Где конкретно не получается?

[maxal]

Sonic86 в сообщении #820227 писал(а):

Выпишите сравнение, определяющее, что сумма чисел подмножества делится на $m$. Решите это сравнение.

Тут проблемка - как вы будете требовать, чтобы все элементы решения были различны?

[provincialka]

DonVito в сообщении #820178 писал(а):

Пробовал. Пускай $\alpha_n$ - количество различных наборов множества $N_n$ натуральных чисел, тогда $\alpha_{n,3}$ - количество наборов, суммы элементов которых кратны 3. Выписав вручную все наборы для $n=1,2,...,6$, их у меня вышло 126, я получил $\alpha_{1,3}=1, \alpha_{2,3}=2, \alpha_{3,3}=4, \alpha_{4,3}=6, \alpha_{5,3}=12, \alpha_{6,3}=24$. Интуитивно чую, что где-то есть какая-то зависимость либо закономерность, но не могу понять где, что и к чему

Ну, внутри каждой тройки идет умножение на 2. Осталось догадаться, как переходить к следующей тройке чисел. Если будет формула, может, удастся доказать по индукции.

[DonVito]

provincialka в сообщении #820550 писал(а):

DonVito в сообщении #820178 писал(а):

Пробовал. Пускай $\alpha_n$ - количество различных наборов множества $N_n$ натуральных чисел, тогда $\alpha_{n,3}$ - количество наборов, суммы элементов которых кратны 3. Выписав вручную все наборы для $n=1,2,...,6$, их у меня вышло 126, я получил $\alpha_{1,3}=1, \alpha_{2,3}=2, \alpha_{3,3}=4, \alpha_{4,3}=6, \alpha_{5,3}=12, \alpha_{6,3}=24$. Интуитивно чую, что где-то есть какая-то зависимость либо закономерность, но не могу понять где, что и к чему

Ну, внутри каждой тройки идет умножение на 2. Осталось догадаться, как переходить к следующей тройке чисел. Если будет формула, может, удастся доказать по индукции.

В том то и дело, что я не могу понять какой переход к следующей тройке и формулу найти не получается. Писать вручную $2^7, 2^8, 2^9$ наборов и смотреть сколько сумм будет делиться на 3 слишком объемная работа.

[Sonic86]

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

Тут проблемка - как вы будете требовать, чтобы все элементы решения были различны?

Да, я чего-то наврал Я не так решал. Я перешел от $\{1,...,n\}$ к мультимножеству классов вычетов и потом, ввиду малости модуля $m=2;3$, находил все решения сравнения $\sum\limits_{s=0}^{m}sx_s\equiv 0\pmod m$, а потом по каждому решению строил решения и тогда их можно посчитать - выбор элементов из разных классов вычетов независим. Но все равно - там даже для $m=2;3$ сразу появляются суммы $\sum\limits_{k\leqslant mn_j}\binom{mn_j}{k}$ ($\sum n_j =n$), так что действительно проще сразу через мультисекцию, тем более, что там, видимо, не надо перебирать решения сравнения.

(Оффтоп)

upd: Что-то до меня только сейчас дошло: а насколько все эти мультисекции будут отличаться от $\frac{2^n}{m}$? М.б. разность вообще ограничена?!
Для $m=3$ у меня $0$-ая сумма свернулась:
$\frac{1}{3}(2^n-(-1)^n)+[3\mid n]$
$S_1=\frac{1}{3}(2^n-(-1)^n)+(-1)^n[3\mid n+1]$

upd2: похоже, что вопрос глупый: разность ограничена только для $m\leqslant 3$

[provincialka]

Ну, зачем вручную. Я посчитала на Excel, дальше будет 44, 88, 176 делящихся на 3.