Proving a polynomial is constant

[ehrenfest]

Homework Statement

Can someone give me a hint on problem 5:

http://math.stanford.edu/~vakil/putnam07/07putnam1.pdf

?

Homework Equations

The Attempt at a Solution

 

[ircdan]

what have you tried?

 

[Kummer]

It is a nice problem. First, you need to know that is a polynomial of degree n takes the same value (n+1) times then it must be be a constant polynomial. The problem says P(x) is a polynomial with integer coefficients so it means P(x) is an integer whenever x is an integer. We know that |P(x)|<n^2 whenever |x|<n so it means for x = -(n-1),...,-1,0,1,...,(n-1) we get P(x) = -(n^2-1),...,-1,0,1,...,(n^2-1). Let P(x) be the "pigeons" and x be the "x". By strong pigeonhole at least n+1 of the pigeons end up in the same hole. So it must be constant.

 

[morphism]

P(x) = x

n=1, and |P(x)|<1 whenever |x|<1^2. But P(x) is not constant.

 

[ehrenfest]

It is a nice problem. First, you need to know that is a polynomial of degree n takes the same value (n+1) times then it must be be a constant polynomial. The problem says P(x) is a polynomial with integer coefficients so it means P(x) is an integer whenever x is an integer. We know that |P(x)|<n^2 whenever |x|<n so it means for x = -(n-1),...,-1,0,1,...,(n-1) we get P(x) = -(n^2-1),...,-1,0,1,...,(n^2-1). Let P(x) be the "pigeons" and x be the "x". By strong pigeonhole at least n+1 of the pigeons end up in the same hole. So it must be constant.

First of all it should be |P(x)|<n whenever |x|<n^2 and secondly I get that there are 2n^2-1 pigeons flying into n-1 pigeon-holes? I have never heard of the strong pigeonhole principle but I do not see why one of the pigeonholes needs to get n+1 pigeons?

 

[Hurkyl]

First of all it should be |P(x)|<n whenever |x|<n^2 and secondly I get that there are 2n^2-1 pigeons flying into n-1 pigeon-holes? I have never heard of the strong pigeonhole principle but I do not see why one of the pigeonholes needs to get n+1 pigeons?

If each pigeonhole has at most n pigeons, then at most how many pigeons are there?

 

[ehrenfest]

Less than or equal to n times the number of pigeon-holes.

In our case, there must be less than or equal to 2n^2 - n total pigeons, which is a contradiction when n is greater than 1. So that explains morphism's counterexample.

But what exactly is the strong pigeon-hole principle? How is it different than "if kn+1 pigeon fly into n pigeonholes, than one of the pigeonholes gets at least k+1 pigeons"?

Can you instead show that ceiling( (2n^2-1)/(2n-1)) is greater than or equal to n+1 somehow?

 

[Kummer]

P(x) = x. n=1, and |P(x)|<1 whenever |x|<1^2. But P(x) is not constant.

First of all it should be |P(x)|<n whenever |x|<n^2 and secondly I get that there are 2n^2-1 pigeons flying into n-1 pigeon-holes?

I did the problem backward, I am sorry. But the way it should be as Ehrenfest posted is correct if you apply my argument.

I have never heard of the strong pigeonhole principle

Okay, it is very simple. If you have 6 pigeonholes and 32 pigeons then there is a pigeonhole that has at least 6 pigeons. In general given h pigeonholes and p pigeons then the number is [n/p] where [ ] here is the ceiling function.

 

[ehrenfest]

That is what I would just call the normal pigeonhole principle. Is there a reason you called is "strong"?

 

[Kummer]

That is what I would just call the normal pigeonhole principle. Is there a reason you called is "strong"?

I call the "basic" pigeonhole to be the one that says that there exists at least one hole having two pigeons. The "strong" one is the generalized argument. I am not sure if that is how it is officially called but that is how I refer to it.

Here is a problem to try for you to solve:
"Let S be the set {2,3,...,100} what is the largest subset that can be chosen of non-prime numbers so that all are pairwise co-prime?"
(Here, 'largest' means the largest number of elements in a set).

 

[ehrenfest]

That's hard. So the pigeon-holes would have to be the number of primes less than 100. And the pigeons would have to be the elements of S. But the problem is pigeon's can fly into multiple holes!

 

[morphism]

Am I missing something, or isn't P(x)=x a counterexample to the original problem?

 

[ehrenfest]

It is a counterexample. See post #7.

 

[Kummer]

@ehrenfest. It really is not so hard. If n is a number in {2,3,...,100} it not a prime number then we can write n = p*m where p is a prime number. So for any n there exists a smallest possible prime divisor. Given any n the smallest prime divisor is 7 because it cannot be 11 because if it were its other prime divisor (which it must have because the number is not prime) must be at least 11 again but then 11*11=121 > 100 which is too large. So 7 is the smallest prime divisor of n. So the smallest prime divisors of n can be: 2,3,5,7. That means if you have 5 (non-prime) numbers by pigeonhole it means two of them share a prime factor so they are not co-prime. That means if you have at least 5 non-prime numbers then they all cannot be pairwise coprime. That means 4 is the largest possible subset, i.e. {4,9,25,49}