# Find ways to pick 3 numbers such that their product is a multiple of 8

$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?

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*}

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.

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.

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

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.