5
$\begingroup$

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

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

2 Answers 2

13
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

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