Il Buono, il Brutto, il Cattivo
Sunday, July 5th, 2009
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).