(1,2,3,...2016)

[daogiauvang]

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

[maxal]

Рассмотрите производящую функцию для количества подмножеств с заданной суммой:

$$f(x)=\prod_{i=1}^{2016} (1+x^i)$$

осуществите её мультисекцию с шагом 3 и подставьте $x=1$.

[ИСН]

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

[maxal]

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

[ИСН]

Ну это-то да, разумеется, с чего бы ей быть другой.

[svv]

Пусть $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$ — тривиальная задача.

[daogiauvang]

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

[svv]

Опишу очень подробно.

В множестве $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$.