2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 (1,2,3,...2016)
Сообщение06.10.2016, 18:55 
Аватара пользователя


21/06/08
476
Томск
Дано множество $A=(1, 2, 3, ..., 2016)$. Сколько подмножеств множества A чтобы сумма всех элементов подмножества делится на $3$.

 Профиль  
                  
 
 Re: (1,2,3,...2016)
Сообщение06.10.2016, 20:07 
Модератор
Аватара пользователя


11/01/06
5660
Рассмотрите производящую функцию для количества подмножеств с заданной суммой:
$$f(x)=\prod_{i=1}^{2016} (1+x^i)$$
осуществите её мультисекцию с шагом 3 и подставьте $x=1$.

 Профиль  
                  
 
 Re: (1,2,3,...2016)
Сообщение06.10.2016, 21:20 
Заслуженный участник
Аватара пользователя


18/05/06
13435
с Территории
С такой артиллерией ответ получится тяжелее самой задачи. Ну а если так: поначалу смотрим, сколько у нас подмножеств с суммами 0, 1 и 2 (mod 3), а потом добавляем числа по одному? Это уже кто-то сделал - A068010, там даже формула есть. Она уродлива, но хотя бы замкнута.

 Профиль  
                  
 
 Re: (1,2,3,...2016)
Сообщение06.10.2016, 21:32 
Модератор
Аватара пользователя


11/01/06
5660
ИСН, не вижу проблемы с "артиллерией" и замкнутостью. Мультисекция как раз даст выражение в косинусах от углов кратных $\frac{\pi}{6}$, а там стандартная тригонометрия. Уверен, что получится та же формула, что и в A068010.

 Профиль  
                  
 
 Re: (1,2,3,...2016)
Сообщение06.10.2016, 22:25 
Заслуженный участник
Аватара пользователя


18/05/06
13435
с Территории
Ну это-то да, разумеется, с чего бы ей быть другой.

 Профиль  
                  
 
 Re: (1,2,3,...2016)
Сообщение08.10.2016, 17:47 
Заслуженный участник


23/07/08
10626
Crna Gora
Пусть $G$ (от слова good) — множество элементов $A$, делящихся на $3$, а $B$ (bad) — не делящихся:
$G=\{3,6,\ldots,2016\}$
$B=\{1,2,4,5,\ldots,2014,2015\}$
Сумма выбранных элементов из $B$ должна делиться на $3$, тогда из $G$ что ни выбирай, будет хорошо.

Заменим каждый элемент $B$ на другое число так:
$1\to 2^0$
$2\to 2^1$
$4\to 2^2$
$5\to 2^3$
$7\to 2^4$
$8\to 2^5$
...
$2015\to 2^{1343}$
Такая замена не меняет остаток от деления на $3$.

Теперь каждому подмножеству $B$ взаимно однозначно соответствует число от $0$ до $2^{1344}-1$. Надо посчитать, сколько из них делятся на $3$.

Добавление потом разных подмножеств $G$ — тривиальная задача.

 Профиль  
                  
 
 Re: (1,2,3,...2016)
Сообщение10.10.2016, 06:42 
Аватара пользователя


21/06/08
476
Томск
maxal Метод хорошо и красиво работает.
svv проблема как посчитать $B$.

 Профиль  
                  
 
 Re: (1,2,3,...2016)
Сообщение10.10.2016, 12:18 
Заслуженный участник


23/07/08
10626
Crna Gora
Опишу очень подробно.

В множестве $A$ есть $2016$ элементов. Само число $2016$ делится на $3$. Можно разбить на тройки:
$1,2,3$
$4,5,6$
...
$2014,2015,2016$
В каждой тройке первое и второе число не делится на $3$, а третье число делится на $3$. Значит, множество $B$ состоит из $\frac 2 3\cdot 2016=1344$ элементов, а множество $G$ состоит из $\frac 1 3\cdot 2016=672$ элементов.

Каждый элемент $B$ я заменяю на другое число $2^n$, где $n$ меняется от $0$ до $1344-1=1343$.
$1\to 2^0$ (остаток был и остался $1$)
$2\to 2^1$ (остаток был и остался $2$)
$4\to 2^2$ (остаток был и остался $1$)
$5\to 2^3$ (остаток был и остался $2$)
$7\to 2^4$ (остаток был и остался $1$)
$8\to 2^5$ (остаток был и остался $2$)
...
$2014\to 2^{1342}$ (остаток был и остался $1$)
$2015\to 2^{1343}$ (остаток был и остался $2$)
Вам надо понять, как связан остаток со степенью $n$ и объяснить, почему он не меняется при такой замене.

Посмотрите на числа $2^0, 2^1, ..., 2^{1343}$ как на $1344$ разряда двоичного числа, от младшего к старшему. Тогда будет понятно, что сумма каких-то чисел из этого множества может принимать все значения от $0$ (когда не выбрали ни одного числа) до $2^{1344}-1=2^0+2^1+...+2^{1343}$ (когда выбрали все числа). И, наоборот, по сумме однозначно восстанавливается набор слагаемых.

Итак, каждое из чисел $0...2^{1344}-1$ взаимно однозначно соответствует некоторому подмножеству $B$, и делится на $3$, если сумма элементов подмножества делится на $3$.

Теперь нам надо посчитать, сколько чисел из множества
$0,1,...,2^{1344}-1$
делится на $3$. Так как $2^{1344}-1$ делится на $3$ (почему?), таких чисел $\frac {2^{1344}+2} 3$ (почему?). Столько будет подмножеств множества $B$, сумма элементов которых делится на $3$.

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

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



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

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


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

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