Math Olympiad problem - Applying induction and the pigeon hole principle

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.

Untitled-5.png
 
on Phys.org
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.
 

Similar threads

  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 1 ·
Replies
1
Views
3K
Replies
1
Views
3K
  • · Replies 17 ·
Replies
17
Views
3K
  • · Replies 14 ·
Replies
14
Views
3K
  • · Replies 6 ·
Replies
6
Views
3K
  • · Replies 1 ·
Replies
1
Views
1K
  • · Replies 18 ·
Replies
18
Views
3K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 2 ·
Replies
2
Views
5K