Question

Given a positive integer n, suppose S is a subset of {1, 2,..., 2n} with |S| = n + 1. Prove that there are distinct a,b in S such that a divides b

Answer 1

What have you tried? Or what has been your thinking so far. Do you understand what it is asking or saying?

Like so we have the universe={1,2,3,...,n,n+1,n+2,n+3,...n+n}

(n+n=2n I just wrote it like the above to see the set better for myself)

Now S is a subset of that universe and is said to have (n+1) elements of the universe.

There are suppose to be numbers a and b in S such that
a|b or a*(some integer)=b

Now if n=1 we have the universe={1,2(1)}={1,2}
There is exactly 2 elements in the universe if n=1
Since n=1, then |S|=1+1=2
Which means that S has to be the universe and 1 does divide 2 since 1(2)=2.

If n=5 we have the universe={1,2,3,4,5,5+1,5+2,5+3,5+4,5+5}
={1,2,3,4,5,6,7,8,9,10}
Remember |S|=1+5=6
So we are suppose to have 6 elements in the universe.
There are many different sets that can be obtained for S.
Here are some possibilities for S:
Possibility 1: {1,2,3,4,5,6}
1|any number
2|4
2|6
3|6

Possibility 2: {1,2,3,4,5,7}
1| any number
2|4

Possibility 3: {1,2,3,4,5,10}
1|any number
2|4
2|10

Possibility 4: {1,2,3,7,9,10}
1|any number
2|10
3|9

Possibility 5: {2,3,5,7,9,10}
2|10
3|9


I will have to be back but I will do some more thinking. Be back in maybe like 3 hours. Sorry. Class time.