Il Buono, il Brutto, il Cattivo
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).
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.
July 6th, 2009 at 3:48 am
The ugly and the good are sometimes given (in this order!) as homework in Discrete Math introductory courses.
The bad is known as http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem and was first proved in 1935.
July 6th, 2009 at 9:05 am
*SPOILER*
Rani,
You are welcome to still write down the answers to the Ugly and the Good. Although the Bad is much harder, it could be given in Discrete Math as well, as its proof relies entirely on the pigeonhole principle too.
What about the Unrelated?
July 6th, 2009 at 9:24 am
BTW, Liron Raz asked me the Good, the Bad and the Ugly, and Oren Sarig asked me the Unrelated.
Thanks guys!
July 7th, 2009 at 3:21 pm
Il Non Collegato Solution:
call the Polynomial f. f(x(i)) = +-1 for each i=1,…,7
Suppose f=g*h, two Polynomials of degree 1 at least.
so one of them is of degree 3 at most. WLOG it’s g.
since the polynomials are of integer coefficients, and x(i) are integers too, f(x(i))=g(x(i))*h(x(i)), and all g(x(i)) must divide +-1, so g(x(i)) = +-1 for each i = 1,…,7
so we now have g, a polynomial of degree at most 3, getting +-1 on 7 integers.
one of the values +1 or -1 is received 4 times at least. WLOG it’s 1
so we now have g-1, a polynomial of degree at most 3, getting 0 on 4 integers at least.
so g-1 == 0 every place.
contradiction (g’s degree is at least 1)