(Homework 4.1) |
|||
| (11 intermediate revisions by 4 users not shown) | |||
| 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 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. | ||
| + | |||
| + | The base case has 1 on top of 2, making one column for n=1. This was the basis case. | ||
| + | |||
| + | By the induction hypothesis, the chart has n columns for the case n. | ||
| + | <pre> | ||
| + | 1 3 5 7 9 11 13 15 | ||
| + | 2 6 10 14 | ||
| + | 4 12 | ||
| + | 8 | ||
| + | 16 | ||
| + | </pre> | ||
| + | |||
| + | 2n+1 will always go to the right, and 2n+2 will be on the left, thus making n+1 columns in total. Thus, the induction hypothesis for n+1 (that the diagram using 1...2n+2 will have n+1 columns) is shown. (It was explained more thoroughly in my solution though.) | ||
| + | |||
| + | If you have n+2 numbers, one must be in the same column as another, by the pigeonhole principle. By how the diagram was set up, if two numbers are in the same column, one divides the other. Thus the statement is proven for all n by using the above argument based on induction. | ||
| + | |||
| + | Related: [[7.5 Homework_MA375Fall2008walther]] | ||
Latest revision as of 10:09, 5 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.
The base case has 1 on top of 2, making one column for n=1. This was the basis case.
By the induction hypothesis, the chart has n columns for the case n.
1 3 5 7 9 11 13 15 2 6 10 14 4 12 8 16
2n+1 will always go to the right, and 2n+2 will be on the left, thus making n+1 columns in total. Thus, the induction hypothesis for n+1 (that the diagram using 1...2n+2 will have n+1 columns) is shown. (It was explained more thoroughly in my solution though.)
If you have n+2 numbers, one must be in the same column as another, by the pigeonhole principle. By how the diagram was set up, if two numbers are in the same column, one divides the other. Thus the statement is proven for all n by using the above argument based on induction.
Related: 7.5 Homework_MA375Fall2008walther
