6
$\begingroup$

Let A = {1, 2,..., 10}. How many three-element subsets of A contain at least two consecutive integers?

I believe there are $\displaystyle \tbinom{10}{3}$ total 3-subsets of A. To find the subsets containing at least two consecutive integers, I thought to subtract from the total all subsets that do not contain consecutive integers.

I had some trouble understanding the general formula for determining the number of size-k subsets of a size-n set that don't contain consecutive integers, but this explanation helped.

Anyway, that gives me $\displaystyle \tbinom{10}{3}- \tbinom{n-k+1}{k}= 120 - \tbinom{10-3+1}{3}= 64$.

Did I miss anything?

Thanks!

$\endgroup$
8
$\begingroup$

First we add subsets by taking any of the $9$ pairs of consecutive integers $\{1,2\},\{2,3\},...,\{9,10\}$ and an arbitrary choice of the third element - in each case there are $8$ such choices, so this gives $9 \cdot 8 = 72$.

However, we see that any set of three consecutive integers $\{1,2,3\},\{2,3,4\},...,\{8,9,10\}$ has been counted twice, so we remove these. There are $8$ of them, so we subtract that and get $9\cdot 8 - 8 = 64$.

$\endgroup$
2
$\begingroup$

You could count the number of $3$ element subsets that have no consecutive integers.

The first number $n_1$ is taken from $1,...,6$ (any higher and there must be a consecutive pair). The next number $n_2$ is taken from $n_1+2,...,8$, and the last number $n_3$ is taken from $n_2+2,...,10$.

Summing gives \begin{eqnarray} \sum_{n_1=1}^6 \sum_{n_2=n_1+2}^8 \sum_{n_3=n_2+2}^{10} 1 &=& \sum_{n_1=1}^6 \sum_{n_2=n_1+2}^8 (9-n_2) \\ &=& \sum_{n_1=1}^6 \sum_{n_2=n_1}^6 (7-n_2) \\ &=& \sum_{n_1=1}^6 \sum_{n_2=1}^{7-n_1} (8-n_2-n_1) \\ &=& \sum_{n_1=1}^6 ((8-n_1)(7-n_1)-\frac{1}{2}(7-n_1)(8-n_1)) \\ &=& \sum_{n=1}^6 \frac{1}{2}(8-n)(7-n) \\ &=& \frac{1}{2} \sum_{n=1}^6 (n^2-15n+56) \\ &=& \frac{1}{2} (91-15\frac{1}{2}(6)(7)+6(56))\\ &=& 56 \end{eqnarray} Since $\binom{10}{3} = 120$, the answer is $120-56= 64$.

$\endgroup$
  • $\begingroup$ Hmm, this really doesn't deserve upvotes, I started writing a solution but it ended up becoming essentially the same as 'tfw cant into math's answer, so I took another approach which I seriously cannot recommend. $\endgroup$ – copper.hat Oct 24 '13 at 22:28
1
$\begingroup$

Alternatively, first count sets of the form $\{a,a+1,b\}$, where $b>a+1$. There are $8$ for $a=1$, there are $7$ for $a=2$, ... , and there's $1$ for $a=8$. That's 36 sets. Still to be counted are sets of the form $\{c,a,a+1\}$ with (to avoid re-counting any previously-counted sets) $c < a-1$. There is $1$ for $a=3$, there are $2$ for $a=4$, ..., and there are $7$ for $a=9$, for another $28$ sets. In all, there are $36+28$ = $64$ sets, which agrees with tfw's calculation.

$\endgroup$

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.