Question: For every subset $T$ of $U = \{ 1,2,3,\ldots,18 \}$, let $s(T)$ be the sum of the

elements of $T$, with $s(\emptyset)$ defined to be $0$. If $T$ is chosen at random

among all subsets of $U$, the probability that $s(T)$ is divisible by $3$ is

$\frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Find $m$

my attempt:

there will be $2^{18}$ subsets in total

and there 6 numbers which are multiple of $3 $,

$6$ numbers are giving remainder 1

when divided by 3,

6 numbers are giving remainder 2 when divided by 3

first i counted subsets of size $1$ such that it's sum is divisible by 3 which

is 6

then, similarly numbers of subset of size $2$ such that its sum is divisible by 3 is $^6 C_1.^6 C_1=36$

similarly numbers of subset of size $3$ such that its sum is divisible by 3 is $216$

but i find difficult to count this way when size of subset increases (say above 10).

in my book solution is provided using Generating function which i do not

understand.so, i want to ask how to derive the expression for generating function in these kind of questions rest i can do myself (finding coefficient of suitable power of 'x')

Thank you.


I believe the size of the set $T$ is a bad parameter for the generating function, the numbers $i$ of residue $1$'s and $j$ of residue $2$'s are better (the number of $0$'s is irrelevant). Let $c_{i, j}=C_{6, i} C_{6, j}$ be the number of subsets of the $\{1, 2, 4, 5, 7, 8, \ldots 17\}$ (no residue $0$'s) out of $2^{6 \cdot 2}$ possible, which have $i$ of residue $1$'s and $j$ of residue $2$'s. Just take the generating function $$c_{i, j}s^it^j=\sum_{i, j} C_{6, i} C_{6, j} s^i t^j=(1+s)^6 \cdot (1+t)^6$$ and calculate the sum of coefficients with $i-j$ divisible by $3$ (and divide it by $2^{6 \cdot 2}$ to get the probability).

If you need, I may write down the complete solution, but I believe it is a nice exercise. If you have a problem, there is a following hint: if $f(i)=\sum_i c_it^i$, the sum of coefficients $c_i$ with $i$ divisible by $3$ is a linear combination of $f(1), f(\epsilon), f(\epsilon^2)$ for $\epsilon$ a degree $3$ root of $1$; the answer seems to be $$\frac{2+2^{2 \cdot 6}}{3 \cdot 2^{2 \cdot 6}}=\frac{(1+2^{11})/3}{2^{11}}=\frac{683}{2048}.$$

  • $\begingroup$ Is it clearer now? Do you understand how $c_{i, j}$'s are related with probability? $\endgroup$ – evgeny Mar 15 '18 at 14:55
  • $\begingroup$ Yes, $(-1+\sqrt(2)i)/3$. $\endgroup$ – evgeny Mar 15 '18 at 16:04

after further reading and with the help of the previous answer i reached at solution:

without using bivariate G.f

generating function for this is come out to be :


now we will calculate,





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.