Expert: Ahmed Salami - 4/18/2009

Question
3. Let X = {1, 2, 3, ..., 1000}. Find the number of 3-element subsets {a, b, c} of X such that the product abc is divisible by 3.

Answer
Hi Rizza,
The total number of 3-element subsets is 1000C3 (read '1000 combination 3') i.e the number of ways of selecting 3 numbers from 1000.
The product abc is either divisible by 3 or it is not. The number of 3-element subsets divisible by 3 plus the number of those not divisible by 3 must be equal to the total number of possible 3-element subsets i.e 1000C3
Now,
1000C3 = 1000!/(1000-3)!.3!
      = 1000!/997!.3!
      = 1000.999.998.997!/997!.3!
      = 1000.999.998/3.2.1
      = 166167000
The product abc is only divisible by 3 if it contains at least one element that is divisible by 3. From the numbers 1 to 1000, there are a total of 333 numbers divisible by 3 i.e 3,6,9,12,.........., 996, 999. To find the number of 3-element subsets not divisible by 3, we realize that we need to pick our three elements such that it contains none of these numbers. This means that we'll be selecting our three elements from the remaining 667 numbers and the number of possible selections for that is 667C3.
667C3 = 667!/(667-3)!.3!
     = 667!/664!.3!
     = 667.666.665.664!/664!.3!
     = 667.666.665/3.2.1
     = 49234605
Therefore, the number of 3-element subsets {a, b, c} of X such that the product abc is divisible by 3 is
1000C3 - 667C3
= 166167000 - 49234605
= 116932395

You can always get back to me.

Regards