Problem 50. Show that among any n+1 positive integers not exceeding 2n, there must be an integer that divides one of the other integers.
Answer:
Base case: n=1, {0,1,2}
Inductive step: Assume P(n): n+1 positive integers not exceeding 2n
Given n+2 positive integers not exceeding 2n+2
If there are n+1 numbers not exceeding 2n+2, done by induction
If we have 2n+1 and 2n+2 in the list
If n+1 is also in the list we are done, (2n+2)/(n+1)
If we remove 2n+1 and 2n+2 and add n+1, which is the set of n+1 integers not
exceeding 2n. There is a pair in which one divides the other. If n+1 is not
one of them, then we have an original pair, and we are done.Italic text
Else some number divides n+1 and thus, divides 2n+2, and we are done Italic text
