My first combinatorics post!

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


The answer is 795.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

The total number of 3 3 -element subsets is ( 20 3 ) 20 \choose 3 = 1140 =1140 .

Now, we count the 3 3 -element subsets say a , b , c {a,b,c} such that 4 4 does not divide a b c abc .

This is possible if and only if either all the three numbers are odd or any two of them are odd and the other an even number not divisible by 4 4 .

There are 10 10 odd numbers in the set 1 , 2 , 3 , , 19 , 20 {1,2,3,\ldots,19,20} and 5 5 even numbers not divisible by 4 4 .

Thus the number of 3 3 -element subsets a , b , c {a,b,c} such that 4 4 does not divide a b c abc is ( 10 3 ) 10 \choose 3 + 5 +5 ( 10 2 ) 10 \choose 2 = 345 =345 .

Thus the number of 3 3 -element subsets such that the product of these elements is divisible by 4 4 is 1140 345 = 795 1140-345= \boxed{795} .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...