Math Olympiad problem - Applying induction and the pigeon hole principle

1 reply · 3K views · last reply
jdinatale
Messages
153
Reaction score
0
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.

Placeholder graphic reading "Photo not found. CLICK for Photos" over a blurred photo of a kitten with its mouth open, and a camera icon below.
 
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.