(MA 375, HW1, problem 50) |
|||
| Line 14: | Line 14: | ||
one of them, '''then we have an original pair, and we are done.'''''Italic text'' | 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'' | Else some number divides n+1 and thus, divides 2n+2, '''and we are done''' ''Italic text'' | ||
| + | |||
| + | |||
| + | [[Category:MA375Spring2009Walther]] | ||
Latest revision as of 16:55, 29 January 2009
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
