A Very Sad Contrived Number Theory Problem!

こんにちは!

This is my first post so I hope that you like it o(>ω<)o

Problem:

Is it possible to find  100 positive integers not exceeding  25,000, such that all pairwise sums of them are different?
 Source: IMO ShortList 2001, number theory problem 6


Solution:

The answer is actually Yes!

Let  p be any odd prime number. In this solution, we will denote  \lbrace n \rbrace as the remainder of  n when divided by  p.

We now try to prove this lemma which kills the problem miraculously!

Lemma: Given any odd prime number  p we can get  p positive integers that don't exceed  2p^{2} such that the pairwise sums of the intgers are all different.

 Proof of the lemma:

Let  f(n) = 2pn +\lbrace n^{2} \rbrace for all  n = 0, \dots\ ,p-1

Let's assume that  f(a) + f(b) = f(c) + f(d) then we can easily notice that it implies  a + b = c + d since  \lfloor \frac{f(a) + f(b)}{2p}\rfloor = a + b which also means that  \lbrace a^{2} \rbrace + \lbrace b^{2} \rbrace = \lbrace c^{2} \rbrace + \lbrace d^{2} \rbrace. Now we have the following conditions  a + b \equiv c + d \pmod{p} and  a^{2} + b^{2} \equiv c^{2} + d^{2} \pmod{p} and the fact that  0 \le a,b,c,d \le p - 1 imply that the pairs  \lbrace a,b \rbrace and  \lbrace c,d \rbrace are actually the same, so that means if we have  \lbrace a,b \rbrace \neq \lbrace c,d \rbrace then we immediately have  f(a) + f(b) \neq f(c) + f(d), which finishes the proof of the lemma.

 

Now all what remains is to plug p = 101, and since we have  2\dot(101)^{2} \lt 25000 our problem is done  \blacksquare

 

Comment:I honestly found this problem somewhat nice and bad at the same time because coming up with the function  f(n) = 2pn +\lbrace n^{2} \rbrace wasn't trivial at all which actually kills the problem immediately but the result is pretty nice!

 

 

Who Am I and How did I get here?

Hi, I'm a rising senior student interested in math olympiad problems especially combinatorics and puzzles in general. 

I actually have seen many strong Japanese competitors using hatena blog to share a cool problem or a trick they have encountered recently during a recent contest or past problems that they want to put spotlight on them to enlighten the readers and teach them new smart stuff! 

I hope that you will enjoy the problems that I will share in this blog!