Difference between revisions of "4.1 Homework MA375Fall2008walther" - Rhea

Revision as of 07:19, 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.

 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. If you have n+2 numbers, one must be in the same column as another. (more on this later)

Related: 7.5 Homework_MA375Fall2008walther