Kassuno’s blog

こんにちは!

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!

Kassuno’s blog

A Very Sad Contrived Number Theory Problem!

こんにちは!

Who Am I and How did I get here?