3
$\begingroup$

$Let$ $A=\{1,2,3,4,5,6,7,8,9\}$

How many ways are there to pick 3 non-repeated numbers from the set $A$ such that their product is a multiple of 8?

My attempt:

I need to fit three $2$s in the multiplication and after that I can pick whatever to get 3 numbers.

I tried separating this by cases:

I pick $8$ then I have $2$ slots left, and so I pick $2$ out of the $8$ numbers remaining.

Case 2: I pick $2$ first, then $4$, then whatever number is left.

Case 3: I pick $6$, etc...

But then I have repeated scenarios between my cases, how can I approach this?

$\endgroup$
3
$\begingroup$

To obtain a multiple of $8$, we must select numbers containing at least three factors of $2$. We can do this by selecting an $8$, by selecting a $2$ and a $4$, or by selecting a $4$ and a $6$.

Let $E$ be the event that you select $8$ and two other numbers from set $A = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$. Let $F$ be the event that you select $2$, $4$, and a third number from set $A$. Let $G$ be the event that you select $4$, $6$, and a third number from set $A$. The number of ways to pick three elements from set $A$ such that their product is a multiple of $8$ is $|E \cup F \cup G|$, where $|S|$ denotes the number of elements in set $S$.

The Inclusion-Exclusion Principle states that $$|E \cup F \cup G| = |E| + |F| + |G| - |E \cap F| - |E \cap G| - |F \cap G| + |E \cap F \cap G|$$

As you observed, the number of elements in event $E$ is $\binom{8}{2}$ since we must select $8$ and two of the other eight numbers in set $A$.

The number of elements in event $F$ is $7$ since we must select $2$, $4$, and one of the other seven numbers in set $A$.

The number of elements in event $G$ is also $7$ since we must select $4$, $6$, and one of the other seven numbers in set $A$.

Since $E \cap F = \{2, 4, 8\}$, $|E \cap F| = 1$.

Since $E \cap G = \{4, 6, 8\}$, $|E \cap G| = 1$.

Since $F \cap G = \{2, 4, 6\}$, $|F \cap G| = 1$.

Observe that $E \cap F \cap G = \emptyset$ since no three element set contains $2$, $4$, $6$, and $8$.

Hence, the number of three elements of set $A = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ in which the product is a multiple of $8$ is \begin{align*} |E \cup F \cup G| & = |E| + |F| + |G| - |E \cap F| - |E \cap G| - |F \cap G| + |E \cap F \cap G|\\ & = \binom{8}{2} + 7 + 7 - 1 - 1 - 1 + 0\\ & = 28 + 7 + 7 - 1 - 1 - 1 + 0\\ & = 39 \end{align*}

$\endgroup$
1
$\begingroup$

The key is to break up the problem into disjoint cases. Try the following:

Case I: You pick 8.

Case II: You don't pick 8, but you pick 4.

Case III: You don't pick 8 or 4.

Each of these cases is easy to deal with.

$\endgroup$
1
$\begingroup$

Well, for your first case you have $_{8}C_{2}$ combinations. For the second case, assuming you pick two and four first, you have 7 numbers left, but you wish to exclude 8, so, you have 6 choices. Thus, $_{6}C_{1}$ cases for this scenario. Then, after this, if you pick 6, you must pick 4 after this. You do not want the case where you choose 2 after this, because this would be a repeat. So, $_{6}C_{1}$ again. Then, add them all up, and that is the total amount of ways.

Also, I wanted to mention that I am assuming that 6*4*2 is the same thing as picking 2*4*6. If the order does matter, then you need to take into account the permutations.

$\endgroup$
  • $\begingroup$ Be careful, you have counted the set $\{4, 6, 8\}$ twice, once in your first case and once in your third case. $\endgroup$ – N. F. Taussig Apr 7 '15 at 3:26
0
$\begingroup$

Draw a frequency tree diagram (like a normal tree diagram but with frequency instead of probability).

First number can be 2 (f=1), 4 (f=1), 6 (f=1), 8 (f=1) or something else (f=5)

From the 2 branch, the second number can be 4 (f=1), 6 (f=1), 8 (f=1) or something else (f=5)

From the 2, 4 branch all future choices (f=7) will give a multiple of 8. So there are 1 times 1 times 7 = 7 ways of choosing a multiple of 8.

From the 2, 6 branch choosing 4 or 8 (f=2) will give a multiple of 8. So there are 1 times 1 times 2 = 2 ways of choosing a multiple of 8.

Etc.

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