2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Количество наборов
Сообщение28.01.2014, 19:14 


28/01/14
10
Дано множество натуральных чисел $\{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?

 Профиль  
                  
 
 Re: Буду очень признателен любой помощи
Сообщение28.01.2014, 20:03 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Posted automatically
Сообщение28.01.2014, 20:04 
Супермодератор
Аватара пользователя


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

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

 Профиль  
                  
 
 Posted automatically
Сообщение28.01.2014, 23:33 
Админ форума
Аватара пользователя


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

 Профиль  
                  
 
 Re: Количество наборов
Сообщение29.01.2014, 00:08 


28/01/14
10
Пробовал. Пускай $\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$. Интуитивно чую, что где-то есть какая-то зависимость либо закономерность, но не могу понять где, что и к чему

 Профиль  
                  
 
 Re: Количество наборов
Сообщение29.01.2014, 07:02 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Количество наборов
Сообщение29.01.2014, 08:17 
Модератор
Аватара пользователя


11/01/06
5660
Примените мультисекцию к ряду
$$(1+x)(1+x^2)\cdots (1+x^n).$$

 Профиль  
                  
 
 Re: Количество наборов
Сообщение29.01.2014, 11:19 


28/01/14
10
Sonic86 в сообщении #820227 писал(а):
Пусть подмножество содержит $k$ элементов, $k=0,...,n$. Выпишите сравнение, определяющее, что сумма чисел подмножества делится на $m$. Решите это сравнение. Найдите число его решений, просуммируйте по $k$.

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

 Профиль  
                  
 
 Re: Количество наборов
Сообщение29.01.2014, 18:42 
Заслуженный участник


08/04/08
8556
DonVito в сообщении #820265 писал(а):
я не совсем понял как это сделать :-(
Что именно непонятно? Где конкретно не получается?

 Профиль  
                  
 
 Re: Количество наборов
Сообщение29.01.2014, 19:50 
Модератор
Аватара пользователя


11/01/06
5660
Sonic86 в сообщении #820227 писал(а):
Выпишите сравнение, определяющее, что сумма чисел подмножества делится на $m$. Решите это сравнение.

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

 Профиль  
                  
 
 Re: Количество наборов
Сообщение29.01.2014, 23:38 
Заслуженный участник
Аватара пользователя


18/01/13
12044
Казань
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. Осталось догадаться, как переходить к следующей тройке чисел. Если будет формула, может, удастся доказать по индукции.

 Профиль  
                  
 
 Re: Количество наборов
Сообщение30.01.2014, 15:46 


28/01/14
10
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 слишком объемная работа.

 Профиль  
                  
 
 Re: Количество наборов
Сообщение30.01.2014, 17:31 
Заслуженный участник


08/04/08
8556
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$

 Профиль  
                  
 
 Re: Количество наборов
Сообщение30.01.2014, 17:55 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group