2
$\begingroup$

I got this problem at high school. The problem doesn’t have a contest, since it is really old, but you can find it on the internet at several websites, like Art of problem solving. Here is the problem:

Let $A=\{1,2,3,\dots,n\}$. How many subsets does $A$ have, such that the sum of the numbers in the subset is divisible by 4?

There are some extra and difficult questions as well:

(1) How many subsets does $A$ have, such that the sum of the numbers in the subset is divisible by 16?

(2) How many subsets does $A$ have, such that the sum of the numbers in the subset is divisible by 32?

(3) How many subsets does $A$ have, such that the sum of the numbers in the subset is divisible by 3?

(4*) How many subsets does $A$ have, such that the sum of the numbers in the subset is divisible by $k$?

If you know the answer to any of these questions, please write a solution. Thanks in advance!!

I don’t know if there exist a formula for (4*). Note that $k,n$ are positive integers. The sum of the numbers in an empty subset is 0.

$\endgroup$
  • 3
    $\begingroup$ Which of these questions can't you answer? This is supposed to be a site where you ask about problems you are having difficulty with. The question sounds like you know how to do the problem, or at least the first 3 parts of it. If that is so, and may be relevant to the solution of the fourth part, then you should explain your solutions to the first three parts, at least in outline. $\endgroup$ – saulspatz Sep 13 '18 at 18:53
  • $\begingroup$ Your title refers to the size of the subsets while the body asks about the sum of the numbers in the subset. Please correct. $\endgroup$ – Ross Millikan Sep 13 '18 at 19:18
  • $\begingroup$ @RossMillikan Whoops, that was my mistaken edit. I changed the title to make it more descriptive, but misread the problem. $\endgroup$ – Mike Earnest Sep 13 '18 at 19:37
2
$\begingroup$

The title originally asked to find the number of subsets whose size is divisible by a given integer. Here is a way to compute the number.

The number of subsets $X$ of a set $S$ of size $n\in\mathbb{Z}_{\geq0}$ such that $$|X|\equiv r\pmod{m}$$ for a given $m\in\mathbb{Z}_{>0}$ and for a fixed $r\in\{0,1,2,\ldots,m-1\}$ is given by $$N(n,m,r):=\frac1m\,\sum_{k=0}^{m-1}\,\exp\left(-\frac{2\pi \text{i}kr}{m}\right)\,\Biggl(1+\exp\left(\frac{2\pi \text{i}k}{m}\right)\Biggr)^n\,,$$ where $\text{i}:=\sqrt{-1}$. In particular, $$N(n,m,0)=\frac1m\,\sum_{k=0}^{m-1}\,\Biggl(1+\exp\left(\frac{2\pi \text{i}k}{m}\right)\Biggr)^n\,,$$ is the number of subsets $X$ of $S$ such that $m$ divides $|X|$. The key idea of the proof is that, for all integers $t$, $$\sum_{k=0}^m\,\exp\left(\frac{2\pi\text{i}kt}{m}\right)=0\text{ if }t\not\equiv 0\pmod{m}\,,$$ and $$\sum_{k=0}^m\,\exp\left(\frac{2\pi\text{i}kt}{m}\right)=m\text{ if }t\equiv 0\pmod{m}\,.$$


This is a way to compute the required answer (with the sum of elements). However, it is not very aesthetic.

Suppose now that $S=\{1,2,\ldots,n\}$. Consider the polynomial $$f_{n}(x):=\prod_{l=1}^n\,\left(1+x^l\right)\,.$$ Then, the coefficient of $x^s$ in $f_n(x)$ is precisely the number of subsets $X$ of $S$ such that $$s=\sum X=\sum_{j\in X}\,j\,.$$ Therefore, the number of subsets $X$ of $\{1,2,\ldots,n\}$ such that $\sum X\equiv r\pmod{m}$ is given by $$\begin{align}L(n,m,r)&:=\frac{1}{m}\,\sum_{k=0}^{m-1}\,\exp\left(-\frac{2\pi\text{i}kr}{m}\right)\,f_n\Biggl(\exp\left(\frac{2\pi\text{i}k}{m}\right)\Biggr) \\&=\frac{1}{m}\,\sum_{k=0}^{m-1}\,\exp\left(-\frac{2\pi\text{i}kr}{m}\right)\,\prod_{l=1}^n\,\Biggl(1+\exp\left(\frac{2\pi\text{i}kl}{m}\right)\Biggr)\,.\end{align}$$ In particular, $$L(n,m,0)=\frac{1}{m}\,\sum_{k=0}^{m-1}\,\prod_{l=1}^n\,\Biggl(1+\exp\left(\frac{2\pi\text{i}kl}{m}\right)\Biggr)$$ is the number of subsets $X$ of $\{1,2,\ldots,n\}$ such that the sum of elements of $X$ is divisible by $m$.


You can do more. Let $\mu\in\mathbb{Z}_{>0}$ and $\rho\in\{0,1,2,\ldots,\mu-1\}$. Then, the number of subsets $X$ of $S:=\{1,2,\ldots,n\}$ such that $$|X|\equiv r\pmod{m}\text{ and }\sum\,X\equiv\rho\pmod{\mu}$$ is given by $$K(n,m,r,\mu,\rho):=\small\frac{1}{m\mu}\,\sum_{k=0}^{m-1}\,\sum_{\kappa=0}^{\mu-1}\,\exp\left(-\frac{2\pi\text{i}kr}{m}-\frac{2\pi\text{i}\kappa\rho}{\mu}\right)\,\prod_{l=1}^n\,\Biggl(1+\exp\left(\frac{2\pi\text{i}k}{m}+\frac{2\pi\text{i}\kappa l}{\mu}\right)\Biggr)\,.$$

$\endgroup$
  • $\begingroup$ The title refers to the size of the subsets, which is what you are answering. The body of the question refers to the sum of the elements in the subsets, which is rather different. $\endgroup$ – Ross Millikan Sep 13 '18 at 19:21
  • $\begingroup$ @RossMillikan Then, I will vote to close the thread until the OP clarifies what he wants exactly. Thanks for the notification. $\endgroup$ – Batominovski Sep 13 '18 at 19:23
  • $\begingroup$ I am the reason for the discrepancy between the title and body, sorry to mislead you. $\endgroup$ – Mike Earnest Sep 13 '18 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.