Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Proving a polynomial is constant

  1. Nov 16, 2007 #1
  2. jcsd
  3. Nov 16, 2007 #2
    what have you tried?
    Last edited: Nov 16, 2007
  4. Nov 16, 2007 #3
    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.
  5. Nov 17, 2007 #4


    User Avatar
    Science Advisor
    Homework Helper

    P(x) = x

    n=1, and |P(x)|<1 whenever |x|<1^2. But P(x) is not constant.
  6. Nov 17, 2007 #5
    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?
  7. Nov 17, 2007 #6


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    If each pigeonhole has at most n pigeons, then at most how many pigeons are there?
  8. Nov 17, 2007 #7
    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?
    Last edited: Nov 17, 2007
  9. Nov 17, 2007 #8
    I did the problem backward, I am sorry. But the way it should be as Ehrenfest posted is correct if you apply my argument.

    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.
  10. Nov 17, 2007 #9
    That is what I would just call the normal pigeonhole principle. Is there a reason you called is "strong"?
  11. Nov 17, 2007 #10
    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).
  12. Nov 17, 2007 #11
    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!
  13. Nov 18, 2007 #12


    User Avatar
    Science Advisor
    Homework Helper

    Am I missing something, or isn't P(x)=x a counterexample to the original problem?
  14. Nov 18, 2007 #13
    It is a counterexample. See post #7.
  15. Nov 21, 2007 #14
    @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}
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook