Consider the following proposition. For every positive integer n, any subset of {1, 2, . . . , 2n} which has size n + 1 contains two distinct elements a and b such that a divides b. - () Prove () using mathematical induction on n. (You can use strong induction if you want.)

Find a counterexample of () when the size n + 1 is changed to n in (). That is, find a positive integer n and a subset of {1, . . . , 2n} which has size n but does not contain any two distinct elements a and b such that a divides b.

We consider more ambitious claim states as follows: For every positive integer n, there exists a subset of {1, . . . , 2n} which has size n but does not contain any two distinct elements a and b such that a divides b. - () Prove (). That is, find a subset with the desired property for every positive integer n.