Exercise 14 (Homework 1).
(induction proof,
proof by cases,
hard exercise,
pigeonhole principle)
Divisibility in number set
Prove that any set of n+1 positive integers less than or equal to 2n, where n \ge 1, contains two distinct elements a and b such that a divides b.
Hint
A possibility is to use the pigeonhole principle: the pigeons are the n+1 numbers and the holes are the odd numbers between 1 and 2n. A pigeon of the form 2^k d with d odd flies to hole d.
Another option is to consider an induction proof on n and distinguish two cases in the inductive step: at least one of the elements 2n+1 and 2n+2 is not in the set or both are.