Discrete Math Using THE PIGEONHOLE PRINCIPLE 3 Generalize Ap

Discrete Math

Using THE PIGEONHOLE PRINCIPLE

3. Generalize Application 5 by choosing (how many?) integers from the set

{l, 2, ... ,2n}.

5. Show that if n + 1 distinct integers are chosen from the set {l, 2, ... , 3n}, then there are always two which differ by at most 2.

7. * Show that for any given 52 integers there exist two of them whose sum, or else whose difference, is divisible by 100.

15. Prove that, for any n + 1 integers al, a2, ... ,an+1, there exist two of the integers ai and aj with i =f. j such that ai - aj is divisible by n.

Solution

3) The question is incomplete since what is Application 5 is not mentioned?

I am solving the problem 5, please post multiple problems for the remaining questions

5) Let us choose the numbers with the condition that the minimum difference is >2, so lets start choosing the numbers

S = {1,4,7,10,....,3n}

We have n numbers in the set which are at minimum distance of 3 from any other element in the set

The other number n+1 must be choosen from {1,2,...,3n}, in any way we choose the number now difference will be atmost 2

Hence there exsist two which differ by atmost 2 by pigeonhole, since we have n holes and (n+1) pigeons, hence 1 hole will contain atleast 2 pigeons