1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Math Olympiad problem - Applying induction and the pigeon hole principle

  1. Sep 2, 2012 #1
    Ok, so this problem looks like an induction problem to me, so I used that, but I only got as far as the induction hypothesis. The hint says to use the pigeon hole principle. I'm not sure how to use that for this problem.

  2. jcsd
  3. Sep 3, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I don't know the solution to this problem, but here are a few things that might be useful:

    There are only 2m distinct absolute values available between -(2m-1) and +(2m-1). Therefore if you have 2m+1 distinct numbers, then an absolute value must be repeated. This means that there must be a positive and negative pair. In other words, the set must contain two distinct values j and -j. If the set also contains zero, then you're done.

    Therefore, we may assume that zero is not one of the 2m+1 distinct integers. This means that there are in fact only 2m-1 possible absolute values (since zero is excluded). Therefore there must be two repeated absolute values, i.e. two positive/negative pairs.

    I haven't worked out where to go from here, and it might be a dead end. It might be useful to play around with a small concrete case, say m=4 or 5, and see how you might prove it in that case.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook