In how many ways can you choose three distinct numbers from the set of {1,2,3,...,19,20} such that their product is divisible by 4 ?


closed as off-topic by Namaste, Hayden, Gina, user147263, Davide Giraudo Jul 21 '14 at 15:43

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Namaste, Hayden, Gina, Community, Davide Giraudo
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ It might be easier to find number of triples which are not divisible by 4 $\endgroup$ – Jack Yoon Jul 21 '14 at 14:08

Strategy: There are $\binom{20}{3}$ possible choices. Let us see how many are bad.

We could choose all odd. Easy to count.

We could choose $2$ odd, and the other divisible by $2$ but not by $4$, that is, one of the numbers $2,6,10,14,18$. Again, it should not be hard to count these.


You can break it down like this. First we ask how many numbers are divisible by four in the set $\{1,...,20\}$ that is $4,8,12,16,20$. If exactly one is chosen from this list we have $$5\cdot {15 \choose 2}$$ ways of doing this. If two are chosen we have $${5 \choose 2} \cdot 15$$ ways of doing that. And finally there are $${5 \choose 3}$$ ways of picking three of the numbers divisible by four.

Then ask how many ways are there to choose two numbers divisible by only two? This includes $2,6,10,14,18$ and then to avoid over counting we can only choose a number not divisible by four from the rest. If we choose it to be an odd number we find: $${5 \choose 2} \cdot 10,$$ and if we choose three even numbers (not divisible by four) we find: $${5 \choose 3}$$ ways of doing this.

The sum of all of these is the answer.

  • 1
    $\begingroup$ (I think you may have to correct for over-counting in the first step, since you could choose 4, 5, 8 or 8, 5, 4.) $\endgroup$ – user84413 Jul 21 '14 at 14:36
  • $\begingroup$ You are right. I think it just needs to be divided by 2... $\endgroup$ – Joel Jul 21 '14 at 14:39
  • 2
    $\begingroup$ It might be easier to break the first step into cases, depending on the number of multiples of 4 chosen. (I believe $5\binom{19}{2}$ is odd.) $\endgroup$ – user84413 Jul 21 '14 at 15:01
  • $\begingroup$ I should never do combinatorics without my coffee. I think this fixes it. $\endgroup$ – Joel Jul 21 '14 at 15:13
  • 1
    $\begingroup$ This looks almost right, but I think maybe there is slight over-counting in the second step. (For example, you could have 2, 6, 10 or 10, 2, 6.) $\endgroup$ – user84413 Jul 21 '14 at 15:30
  1. We need three numbers, one of which is divisible by 4, and any other two

    In this set, the divisible by 4 are only 5 $\{4,8,12,16,20\}$. And we don't care what the other 2 will be, as they all will do the job. =>$5\cdot19\cdot18\div2 = 855$

  2. We need three numbers, two of which are divisible by 2, but not by 4, and one undivisible by 4

    In the set, the divisible by 2, but not by 4, are only 5$\{2,6,10,14,18\}$. We need 2 of this set, and 1 from the set, exlcuding only divisible by 4 $\{1,2,3,5,...,19\}$, which are 15, but since we used 2 of them, there are only 13 left. => $5\cdot4\cdot13\div2=130$

Giving us a total of $985$ ways

  • $\begingroup$ This is not correct. Do you see why? $\endgroup$ – Jack Yoon Jul 21 '14 at 14:20
  • $\begingroup$ Yep, thanks, already updated it. $\endgroup$ – Peter Jul 21 '14 at 14:42
  • $\begingroup$ Still not true. Following Andre's method I get 795. Firstly dividing by two in case 1 is not enough. $\endgroup$ – Jack Yoon Jul 21 '14 at 15:04

Not the answer you're looking for? Browse other questions tagged or ask your own question.