1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Differences of numbers

  1. Nov 20, 2007 #1
    1. The problem statement, all variables and given/known data
    http://math.stanford.edu/~vakil/putnam07/07putnam1.pdf
    I am working on number 6.

    Consider the the ordered pairs (1,12),(2,13),...,(89,100). There are 89 of them. These are the pigeon holes.

    There are 55 numbers between 1 to 100 and each of them flies to one or two pigeon holes. So split all of the pigeons not equal to 1 and 100 in half to get at least 108 pigeons. Then we have 108 pigeons flying to 89 holes. So there must be two numbers that differ by 11.

    What is wrong with my logic?


    2. Relevant equations



    3. The attempt at a solution
     
  2. jcsd
  3. Nov 20, 2007 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Why?
     
  4. Nov 20, 2007 #3
    Because every integer except 1 and 100 is in exactly 2 of the order pairs.
     
  5. Nov 21, 2007 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    But that's not true.
     
  6. Nov 21, 2007 #5
    Oh. So I need to exclude 1 to 11 and 90 to 100 which makes 22 numbers, right? So we have at least 55*2 - 22 = 88 numbers going to 89 pigeonholes, so they can fit each fit in a different one and even leave 1 open.

    But in the case of 10 you have more pigeons than pigeonholes.

    I am not sure about 12, though...
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?