| Line 8: | Line 8: | ||
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". | 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 | + | Then assume P(n) and prove P(n+1) by assuming n+2 numbers between 1 and 2n+2 have been chosen and |
a) checking what happens when at most one of 2n+1 and 2n+2 are chosen, | a) checking what happens when at most one of 2n+1 and 2n+2 are chosen, | ||
b) what happens if both are chosen. | b) what happens if both are chosen. | ||
| − | b) is harder, investigate what happens if n+1 was chosen. | + | b) is harder, investigate first here what happens if n+1 was chosen. |
| − | + | If in b) n+1 was not chosen, let a_1,...,a_n,2n+1,2n+2 be the chosen numbers. Now pretend(!) you also had n+1. That gives you n+1 numbers between 1 and 2n, so you can use the inductive hypothesis. It tells you that either some a_i divides another a_j (good) or that some a_i divides n+1 (which is ok, why?) or that n+1 divides some a_i (which turns out to be impossible- why?). | |
---- | ---- | ||
Revision as of 14:44, 3 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 assuming n+2 numbers between 1 and 2n+2 have been chosen and 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 first here what happens if n+1 was chosen.
If in b) n+1 was not chosen, let a_1,...,a_n,2n+1,2n+2 be the chosen numbers. Now pretend(!) you also had n+1. That gives you n+1 numbers between 1 and 2n, so you can use the inductive hypothesis. It tells you that either some a_i divides another a_j (good) or that some a_i divides n+1 (which is ok, why?) or that n+1 divides some a_i (which turns out to be impossible- why?).
The problem I had is if 2n+1, 2n+2 are chosen and n+1 is not chosen. It's a great start, but it took me a while to figure out where to go from there.
Here's the way I ordered the numbers in my proof, noticing where n+1 and n+2 go.
1 3 5 7 9 11 13 15 2 6 10 14 4 12 8 16
