Question

Counting and Pigeonhole Principle (a). A set of four different integers is chosen at random between 1 and 200 (inclusive). How many different outcomes are possible? (b). How many different integers between 1 and 200 (inclusive) must be chosen to be sure that at least 3 of them are even? (c). How many different integers between 1 and 200 (inclusive) must be chosen to be sure that at least 2 of them add up to 20? (d). How many different integers between 1 and 200 (inclusive) must be chosen to be sure that at least one of them contains the digit 5? (For example, {11, 35, 42} has an integer that contains the digit 5, while {2, 48, 71, 96} does not.)

Answer 1

(a). the total possible number of ways to choose 4 object out of 200 objects is

$\binom{200}{4}$ = 200!/(196!4!)= 64684950.

(b). if we choose n integers from 1 to 200 and if n is less then or equals to 100 then there is always possibility that all the choosen n integers are even because there are 100 odd integers between 1 and 200, if we choose 101 or 102 integers then there is possibility that out of 101 or 102 choosen integers 100 integers are odd but if we choose 103 integers then since there are only 100 odd integers between 1 and 200 then 3 integers out of choosen 103 integers must be even so 103 is the answer.

(C) if we choose n number of integers from 1 to 200 and if n is less then or equals to 191 then there is always possibility that all those choosen n integers are greater then or equals to 10 so in this scenerio it's not possible to choose two integers such that there sum is 20 out of n integers as all such n integers will be greater then or ewuals to 10 so sum of any two of them will always exceed 20 ,now if we choose 192 integers between 1 and 200 then there will always exist two integers such that sum of them is 20 as we have choosen 192 integers only 8 integers between 1 and 200 are not choosen so only atmost 8 integer between 1 to 9 are not choosen for particular suppose that 8 integers from 1 to 9 are not choosen so exactly1 integer from 1 to 9 is choosen let's say it is 'a' then 20-a is also choosen and a+(20-a)=20. similarly if less then 8 integer between 1 and 9 are not choosen we can show that there exist an integer 'a' between 1 to 9 such that a and 20-a both are choosen ,so 192 is the answer.

(d). there are 29 integers between integers from 1 to 200 ,so we must choose atleast (200-29)+1 = 172 integers to make sure that atleast one of them have digit 5.