For inspirational music, click here.

Il Buono (nice and easy)

Prove that in a subset of size n+1 of the set {1,2,…,2n} there are two numbers such that one divides the other.

Il Cattivo (beautiful and hard)

Prove that in a sequence of r*s+1 distinct numbers, there is either a monotonically increasing sub-sequence of length r+1 or a monotonically decreasing sub-sequence of length s+1.

Il Brutto (just easy)

Prove that in a subset of size n+1 of the set {1,2,…,2n} there are two relatively prime numbers (i.e. numbers whose gcd is 1).

Il Non Collegato (another easy one)

Prove that a degree 7 polynomial with integer coefficients, that receives the values +1 or -1 on 7 integer points is irreducible over the integers.

Unusually, I decided to omit the second page, so post your solution related comments below.