0
$\begingroup$

I found this problem from an old math questionnaire.

How many 3-element subsets of {1,2,3,...,11,12,13} are there for which the sum of the 3 elements is divisible by 3?

At first, I tried listing down all of them. But then, I realized they were too many and so, I just stopped. Next, I tried using stars and bars technique. I represented the 3 elements as a,b,c and their sum as a+b+c=m where m is the set of positive integers divisible by 3 from 3 to 39. From there, I tried out each equation with stars and bars from a+b+c=3 to a+b+c=15, and found a total of 185 subsets satisfying the given conditions. I stopped at here since I noticed that if I continued doing this from a+b+c=18 to a+b+c=39, I would have an error since I was not able to limit the values of a,b,c at most 13.

I do not know how to proceed right now. Can anyone help?

$\endgroup$
  • $\begingroup$ @Ross Millikan, Jack D' Aurizio and Batominovski, I really appreciate your help. Unfortunately, the solutions you suggested were honestly too much for me to handle. I really do not understand a single one you, guys, suggested. $\endgroup$ – Carl Terence Valdellon Aug 29 '16 at 1:07
6
$\begingroup$

Hint: There are five elements of your set that are $1 \bmod 3$, four that are $0 \bmod 3$ and four that are $2 \bmod 3$. You can get a sum that is $0 \bmod 3$ by taking three of the same kind or one of each kind.

$\endgroup$
  • $\begingroup$ but remember that you have to take them in order $\endgroup$ – G Cab Aug 28 '16 at 16:26
  • 1
    $\begingroup$ @GCab: we were asked for subsets, so order doesn't matter. $\endgroup$ – Ross Millikan Aug 28 '16 at 16:28
  • $\begingroup$ Oops, perhaps there is some misunderstanding: as far as I know sets and subsets are ordered lists, so in the present case one of the specified subsets would be for instance ${3,6,9}$, while ${6,3,9}$ is not a subset: am I wrong ? $\endgroup$ – G Cab Aug 28 '16 at 21:40
  • $\begingroup$ @GCab: No, sets are not ordered. $\{6,3,9\}$ is a subset of the given set, but it is the same subset as $\{3,6,9\}$. It should only be counted once. $\endgroup$ – Ross Millikan Aug 28 '16 at 21:45
  • $\begingroup$ so.. I'm not native english speaker, but (probably) understood the "punctualization" you want to make about the concept of set and that's right . However coming to counting, so in combinatorics at least, subsets (understanding different subsets) bi-ject to tuples : can we say that? $\endgroup$ – G Cab Aug 28 '16 at 23:58
2
$\begingroup$

A more general approach is given by generating functions.
We may consider the bivariate polynomial

$$ q(x,y)=(1+yx)(1+yx^2)\cdot\ldots\cdot(1+yx^{12})(1+yx^{13}) $$ and the coefficient of $y^3$ in $q(x,y)$, that is $$ [y^3]\,q(x,y) = r(x) = x^6+x^7+2 x^8+3 x^9+4 x^{10}+5 x^{11}+7 x^{12}+8 x^{13}+10 x^{14}+12 x^{15}+14 x^{16}+15 x^{17}+17 x^{18}+17 x^{19}+18 x^{20}+18 x^{21}+18 x^{22}+17 x^{23}+17 x^{24}+15 x^{25}+14 x^{26}+12 x^{27}+10 x^{28}+8 x^{29}+7 x^{30}+5 x^{31}+4 x^{32}+3 x^{33}+2 x^{34}+x^{35}+x^{36} $$ then sum the coefficients of the monomials of the form $x^{3k}$. If $\omega=\exp\left(\frac{2\pi i}{3}\right)$, that sum is just $$ \frac{1}{3}\left( r(1)+r(\omega)+r(\omega^2) \right) $$ or the coefficient of $y^3$ in the polynomial $\frac{1}{3}\left(q(1,y)+q(\omega,y)+q(\omega^2, y)\right)$, where:

$$\frac{1}{3}\left(q(1,y)+q(\omega,y)+q(\omega^2, y)\right) = (1+y)^4\cdot\left(1+20 y^2+14 y^3+\ldots\right)$$ gives us the answer: $$ 14+4\cdot 20+4 = \color{red}{98}. $$ Not by chance, this number is close to one third of the total number of $3$-subsets, given by $\binom{13}{3}=286$.

$\endgroup$
  • $\begingroup$ I am sorry, I do not have a background of generating functions. Is there any other solution that can be used? I believe that generating functions are too advanced for me. $\endgroup$ – Carl Terence Valdellon Aug 29 '16 at 1:17
  • 1
    $\begingroup$ @CarlTerenceValdellon: Ross Millikan already provided you an elementary solution: $$98=\binom{4}{3}+\binom{4}{3}+\binom{5}{3}+4\cdot 4\cdot 5.$$ $\endgroup$ – Jack D'Aurizio Aug 29 '16 at 1:23
1
$\begingroup$

Jack D'Aurizio's answer can be generalized. However, I don't think that the computation is simple.

Let $m$, $n$, and $p$ be positive integers such that $m\leq n$. The polynomial $f_{m,n}(x,y)\in\mathbb{Z}[x,y]$ is given by $$f_{m,n}(x,y):=\prod_{i=1}^n\,\left(1+xy^i\right)-1\,.$$ For any positive integer $s$, write $\omega_s:=\exp\left(\frac{2\pi\text{i}}{s}\right)$. Then, the number of $m$-subsets of $\{1,2,\ldots,n\}$ whose sum is $k$ modulo $p$, where $k\in\{0,1,2,\ldots,p-1\}$, is given by $$N_{m,n,p,k}:=\frac{1}{pn}\,\sum_{r=0}^{p-1}\,\omega_p^{-rk}\,\left(\sum_{j=0}^{n-1}\,\omega_n^{-jm}\,f_{m,n}\left(\omega_n^j,\omega_p^r\right)\right)\,.\tag{1}$$

Alternatively, let $$\tilde{f}_{m,n}(x,y):=\prod_{i=1}^n\,\left(1+xy^i\right)\,.$$ Then, $$N_{m,n,p,k}=\frac{1}{p(n+1)}\,\sum_{r=0}^{p-1}\,\omega_p^{-rk}\,\left(\sum_{j=0}^{n}\,\omega_{n+1}^{-jm}\,\tilde{f}_{m,n}\left(\omega_{n+1}^j,\omega_p^r\right)\right)\,.\tag{2}$$ The only difference between (1) and (2) is that (2) handles the trivial case $m=0$, while (1) does not.

$\endgroup$
  • $\begingroup$ I am sorry, but I do not understand how this solution works. $\endgroup$ – Carl Terence Valdellon Aug 29 '16 at 1:16
  • $\begingroup$ My post is not a solution per se. I wanted to make this as a comment on Jack D'Aurizio's answer, but commenting under his answer was not an option. For a real solution, Ross Millikan already gave that to you. $\endgroup$ – Batominovski Aug 29 '16 at 1:20

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.