5
$\begingroup$

Problem

I'm told that a bag of marbles contains $10$ red and $5$ white marbles. Each of the red and white marbles is numbered such that they are distinct within their own groups, i.e.

$R = \{a, b, c, d, e, f, g, h, i, j\}$

$W = \{1, 2, 3, 4, 5\}$

I'm asked to calculate how many combinations there are if I am to select $4$ marbles from the bag but at least one of them must be a red marble.

Attempt

If there is at least $1$ marble, then that is $10$ choose $1$, which is just $10$. Afterwards, we are left with $14$ marbles in total and need to choose $3$ of them, which is $364$. Multiplying by $10$, I get $3,640$, but the answer key says it's supposed to be $1,360$.

Where did I go wrong?

Edit: I tried using the counting by complement rule and got the right answer, but I'm still curious what's wrong with this approach.

$\endgroup$
2
  • $\begingroup$ It is frequently to your advantage to flip these cominatorics problems on their heads. At least one is red is the inverse of none are white. None are white has fewer variables to account for. $\endgroup$
    – Doug M
    Jun 29, 2017 at 22:44
  • $\begingroup$ Yup, I didn't think of that at first, and I mentioned in the edit that I used that approach and was indeed able to get $1,360$. $\endgroup$ Jun 29, 2017 at 22:45

2 Answers 2

4
$\begingroup$

What's wrong with this approach?

When you selected $1$ red marble in the first round (by 10 ways), suppose you selected $a$. Now later on, you selected 3 more marbles, let, $b,c$ and $d$. Now take a look at another case. Suppose you had selected $b$ in the first round and $a,c$ and $d$ in the second round. Don't you think these are the same cases but you have counted them repeatedly. Therefore, your answer is far greater than correct answer (Due to repetitive counting of same cases)


What to do now?

Just count the cases when there was not a single red marble selected, and subtract that number from total cases, to get the number of cases with at least one red marble.

$\endgroup$
1
  • $\begingroup$ Ah, interesting. That example makes it clearer, thank you! $\endgroup$ Jun 29, 2017 at 22:46
1
$\begingroup$

A direct count of the number of selections with at least one red marble is $$\binom{10}{1}\binom{5}{3} + \binom{10}{2}\binom{5}{2} + \binom{10}{3}\binom{5}{1} + \binom{10}{4}\binom{5}{0} = 1360$$ which can be obtained more easily obtained by using complementary counting. $$\binom{15}{4} - \binom{5}{4} = 1360$$

You counted selections in which there is more one red marble multiple times. For instance, if you selected $\{a, b, 1, 2\}$, you counted it twice, once when you counted $a$ as the designated red marble and once when you counted $b$ as the designated red marble.

In general, any selection with two red marbles is counted twice, once for each of the $\binom{2}{1}$ ways of designating a particular marble as the red marble you selected. You counted each selection with three red marbles three times, once for each of the $\binom{3}{1}$ ways you could designate a particular red marble as the red marble you selected, and each selection with four red marbles four times, once for each of the $\binom{4}{1}$ ways you could designate a particular red marble as the red marble you selected. Note that $$\binom{10}{1}\binom{5}{3} + \binom{2}{1}\binom{10}{2}\binom{5}{2} + \binom{3}{1}\binom{10}{3}\binom{5}{1} + \binom{4}{1}\binom{10}{4}\binom{5}{0} = 3640$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .