• Support PF! Buy your school textbooks, materials and every day products Here!

Math Olympiad problem - Applying induction and the pigeon hole principle

  • #1
155
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
 

Answers and Replies

  • #2
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
179
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.
 

Related Threads for: Math Olympiad problem - Applying induction and the pigeon hole principle

  • Last Post
Replies
3
Views
1K
Replies
56
Views
3K
Replies
1
Views
6K
  • Last Post
Replies
2
Views
644
  • Last Post
Replies
4
Views
890
Replies
5
Views
1K
Replies
0
Views
4K
Replies
4
Views
2K
Top