m (User:Aifrank moved to 4.1 Homework: wrong name) |
|||
| Line 2: | Line 2: | ||
Use mathematical induction to show that given a set of n + 1 positive integers, none exceeding 2n, there is at least one integer in this set that divides another integer in the set. | Use mathematical induction to show that given a set of n + 1 positive integers, none exceeding 2n, there is at least one integer in this set that divides another integer in the set. | ||
| + | |||
| + | Here is an idea: P(n)="given a set of n + 1 positive integers, none exceeding 2n, there is at least one integer in this set that divides another integer in the set". | ||
| + | |||
| + | Then assume P(n) and prove P(n+1) by | ||
| + | a) checking what happens when at most one of 2n+1 and 2n+2 are chosen, | ||
| + | b) what happens if both are chosen. | ||
| + | |||
| + | b) is harder, investigate what happens if n+1 was chosen. | ||
| + | |||
| + | if n+1 was not chosen, pretend you also get to chose k+1 and go from there. | ||
Revision as of 10:32, 2 September 2008
Does anyone know how to go about starting problem 50 for 4.1
Use mathematical induction to show that given a set of n + 1 positive integers, none exceeding 2n, there is at least one integer in this set that divides another integer in the set.
Here is an idea: P(n)="given a set of n + 1 positive integers, none exceeding 2n, there is at least one integer in this set that divides another integer in the set".
Then assume P(n) and prove P(n+1) by a) checking what happens when at most one of 2n+1 and 2n+2 are chosen, b) what happens if both are chosen.
b) is harder, investigate what happens if n+1 was chosen.
if n+1 was not chosen, pretend you also get to chose k+1 and go from there.
