Using the pigeonhole principle Discrete math Application 5 F

(Using the pigeonhole principle) Discrete math

Application 5. From the integers 1,2, ... ,200, we choose 101 integers. Show that, among the integers chosen, there are two such that one of them is divisible by the other.

By factoring out as many 2s as possible, we see that any integer can be written in the form 2k x a, where k ;::: 0 and a is odd. For an integer between 1 and 200, a is one of the 100 numbers 1,3,5, ... ,199. Thus among the 101 integers chosen, there are two having a\'s of equal value when written in this form. Let these two numbers be 2T x a and 28 x a. If r < s, then the second number is divisible by the first. If r > s, then the first is divisible by the second. 0

Let us note that the result of Application 5 is the best possible in the sense that we may select 100 integers from 1,2, ... ,200 in such a way that no one of the selected integers is divisible by any other (for instance, the 100 integers 101,102, ... , 199,200).

We conclude this section with another application from number theory. First, we recall that two positive integers m and n are said to be relatively prime if their greatest common divisor5 is 1. Thus 12 and 35 are relatively prime, but 12 and 15 are not since 3 is a common divisor of 12 and 15.

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 number of integers required from the set {1,2,...,2n} will be equal to (n+1)

Let us make an set of number {1,3,5,7,9,...,(2n-1)}, now if we add one more number then the number of integers will become divisible with each other hence the minimum pigeonholes for this problem will be equal to (n+1) for 2n integers

15) Consider n boxes labeled from 0,1,...,r-1, place the integers from a1,a2,...,an in the box such taht a1 leaves a remainder r when is divided by n

Since the number of boxes is n, hence there will be atleast two boxes such that number mod (n) will be the same using the pigeonhole principle, hence the difference of these two numbers when taken mod n will be equal to zero