# How many $3$-element subsets of $\{1,2,3,...,19,20\}$ have product divisible by $4$?

Same question :- Where am I overcounting?

How many $$3$$ element subsets of the set $$\{1,2,3,...,19,20\}$$ are there such that the product of the three numbers in the subset is divisible by $$4$$?

My attempt:-

I divided this into broadly 2 cases :-

Case 1:-

Subsets containing atleast 1 number of type 4k :-

1. $$4k, 4k, 4k$$ =$${5 \choose 3}$$

2. $$4k, 4k, 4k+1$$ =$${5 \choose 2}*{5 \choose 1}$$

3. $$4k,4k,4k+2$$ =$${5 \choose 2}*{5 \choose 1}$$

4. $$4k,4k,4k+3$$ =$${5 \choose 2}*{5 \choose 1}$$

5. $$4k,4k+1,4k+1$$ =$${5 \choose 1}*{5 \choose 2}$$

6. $$4k,4k+1,4k+2$$ =$${5 \choose 1}*{5 \choose 1}*{5 \choose 1}$$

7. $$4k,4k+1,4k+3$$ =$${5 \choose 1}*{5 \choose 1}*{5 \choose 1}$$

8. $$4k,4k+2,4k+2$$ =$${5 \choose 1}*{5 \choose 2}$$

9. $$4k,4k+2,4k+3$$ =$${5 \choose 1}*{5 \choose 1}*{5 \choose 1}$$

Case 2:- without any 4k type of number

1. $$4k+2, 4k+2, 4k+2$$ =$${5 \choose 3}$$

I cant figure out what all cases am I missing ? I am getting 685 cases however total cases are 795

• Try complementary counting instead. Now there are just two cases: All numbers are odd or two numbers are odd and one is even. Commented Aug 27, 2023 at 0:15
• You missed $4k,4k+3,4k+3$,and $4k+2,4k+2,2k+1$ Commented Aug 27, 2023 at 0:31

## 2 Answers

We use complementary counting. For a set to have the product of its elements not divisible by $$4$$, there are two cases:

1. All elements are odd. There are $$10$$ odd numbers, so there are $$\binom{10}{3}$$ ways here.
2. Two elements are odd and one is even, but not divisible by $$4$$. This is $$\binom{5}{1}\cdot \binom{10}{2}$$.

Thus the answer is $$\binom{20}{3}-\binom{10}{3}-\binom{5}{1}\binom{10}{2}=\boxed{795}$$.

Although complementary counting provides the most elegant approach, the approach taken by the OP (i.e. original poster) is still viable.

Case 1: At least one number that is a multiple of $$~4.~$$

There are $$~\displaystyle \binom{20}{3}~$$ ways of choosing three numbers, and there are $$~\displaystyle \binom{15}{3}~$$ ways of choosing three numbers, none of which is an element in $$~\{4,8,12,16,20\}.$$

Therefore, the Case 1 enumeration is

$$\binom{20}{3} - \binom{15}{3} = 685.$$

Case 2: None of the numbers are a multiple of $$~4.~$$

So, you either have exactly two even numbers, none of which is a multiple of $$~4,~$$ or three such even numbers.

Case 2a: Exactly two even numbers, neither of which is a multiple of $$~4.~$$

So, you have exactly one element from $$~\{1,3,5,\cdots,19\},~$$ and exactly two elements from $$~\{2,6,10,14,18\}.$$

So, the Case 2a enumeration is

$$\binom{10}{1} \times \binom{5}{2} = 100.$$

Case 2b: Exactly three even numbers, neither of which is a multiple of $$~4.~$$

You then have exactly three elements from $$~\{2,6,10,14,18\}.$$

So, the Case 2b enumeration is

$$\binom{5}{3} = 10.$$

Final Total:

$$685 + 100 + 10 = 795.$$