4
$\begingroup$

The Set is S={1,2,3,.....,25}. We have to count the number of subsets of size 5 such that each has atleast one Odd number in it.

Method 1:

Count = (Total Subsets of size 5) - (Total subsets having all even numbers) $$ = \binom {25} {5} - \binom {12} {5} = 53130 - 792 = 52338$$

Method 2:

Consider the 5 element subsets as 5 distinct boxes, each can be filled with one number.

1st box can be filled by any of the 13 Odd numbers. 2nd by the remaining 24. 3rd by remaining 23. 4th by remaining 22. 5th by remaining 21. $$\text{Total} = 13 \times{24} \times{23} \times{22} \times{21}=3315312$$

Why am I getting two answers? Which method is flawed and how?

$\endgroup$
  • $\begingroup$ Keep in mind that conpliment to 'each' is $\exist$ at least 1. You can have two sets with no odd numbers. $\endgroup$ – Alex Jan 19 '17 at 9:34
4
$\begingroup$

First method is correct

Second method is false because you are counting several solutions multiple times.

For example the set {1, 2, 3, 4, 6 } is counted at least twice :

  • a first time when you consider putting 1 into the first box
  • a second time when you consider putting 3 into the first box
$\endgroup$
3
$\begingroup$

The second answer is incorrect, and the first answer is the one that is correct.

As mentioned by Adren, you are counting the same set twice. Also, I would further mention the fact that you are counting the numbers assuming they were ordered, but since they are all an element of the same set, they are in reality, unordered. The correct method would be thus: $$\sum_{i=1}^{5}\binom{13}{i} \times \binom{12}{5-i}$$ Where you are dividing the cases where there are $1,2,3,4,5$ odd numbers.

$\endgroup$
  • $\begingroup$ @spaceisdarkgreen I misread the OP. I was skimming. I'm currently on my phone, so I will be unable to edit. $\endgroup$ – S.C.B. Jan 19 '17 at 9:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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