Difference between revisions of "2001 IMO Shortlist Problems/N6"

(New page: == Problem == Is it possible to find 100 positive integers not exceeding 25,000, such that all pairwise sums of them are different? == Solution == {{solution}} == Resources == * [[2001 ...)
 
(This should have been combinatorics, and how did it get to the shortlist anyways???)
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
{{solution}}
+
The biggest pairwise sum is <math>24999+25000=49999</math>, and there are <math>\binom{100}{2}=50050</math> sums. Thus by the [[Pigeonhole Principle]], there must be at least two sums which are equal.
  
 
== Resources ==
 
== Resources ==

Revision as of 08:12, 6 October 2008

Problem

Is it possible to find 100 positive integers not exceeding 25,000, such that all pairwise sums of them are different?

Solution

The biggest pairwise sum is $24999+25000=49999$, and there are $\binom{100}{2}=50050$ sums. Thus by the Pigeonhole Principle, there must be at least two sums which are equal.

Resources