0
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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}.$$

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

You must log in to answer this question.