In how many ways can you choose three distinct numbers ....

2,201

Solution 1

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.

Solution 2

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.

Share:
2,201

Related videos on Youtube

teamathematic
Author by

teamathematic

Updated on July 22, 2020

Comments

  • teamathematic
    teamathematic over 3 years

    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 ?

    • Jack Yoon
      Jack Yoon over 9 years
      It might be easier to find number of triples which are not divisible by 4
  • Jack Yoon
    Jack Yoon over 9 years
    This is not correct. Do you see why?
  • user84413
    user84413 over 9 years
    (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.)
  • Joel
    Joel over 9 years
    You are right. I think it just needs to be divided by 2...
  • Peter
    Peter over 9 years
    Yep, thanks, already updated it.
  • user84413
    user84413 over 9 years
    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.)
  • Jack Yoon
    Jack Yoon over 9 years
    Still not true. Following Andre's method I get 795. Firstly dividing by two in case 1 is not enough.
  • Joel
    Joel over 9 years
    I should never do combinatorics without my coffee. I think this fixes it.
  • user84413
    user84413 over 9 years
    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.)
  • Joel
    Joel over 9 years
    Right again. I don't think I have ever made so many edits to a question.
  • user84413
    user84413 over 9 years
    Thanks for taking the time to edit your answer. (Some MSE users only care about points, not whether their work is actually correct.)
  • Joel
    Joel over 9 years
    I would much rather have correct answers than points. If an answer is not salvageable, then I rather delete it. Points are a silly incentive in any case.