Is it possible to find $100$ positive integers not exceeding $25,000$, such that all pairwise sums of them are different?
Attachments:
Problem
Source: IMO ShortList 2001, number theory problem 6
Tags: modular arithmetic, number theory, Additive Number Theory, sums, IMO Shortlist
Attachments:
orl
30.09.2004 20:57
Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions
Myth
03.10.2004 22:18
I have just constructed (with aid of computer) a set of 100 numbers with required property, but last number in this set is 26780. All my numeric experiments lead to result that the largest number is about 27000. So we have two possibilities: 1) Estimate 25000 is quite exact and there are no such set; 2) my very simple "greedy" algorithm is nearly to optimal. Approximately behaviour of my sequences is $\frac{n^2\sqrt{n}}{4}$.
pbornsztein
03.10.2004 22:55
This b) Look at WOP to India # ? and France # 6. Pierre.
Myth
03.10.2004 23:34
I believe that trick with prime numbers is far from evidence. Hence France 6 is much more easier than this one.
pbornsztein
03.10.2004 23:57
The solution given in WOP for France 6 (and as I see in the ISL01) is due to Erdos and Turan. Pierre.
Zhero
28.12.2010 04:43
Let $p = 101$, let $[n]_p$ denote the remainder when $n$ is divided by $p$, and let $f(n) = 2pn + [n^2]_p$. We claim that the set $\{f(1), f(2), \ldots, f(100)\}$ satisfies the conditions of the problem.
For all $i \leq 100$, $f(i) = 2pi + [i^2]_p < 20200 + 101 < 25000$. In addition, for $1 \leq i,j \leq 100$, $f(i) = f(j)$ implies $|2p(i-j)| = |[i^2]_p - [j^2]_p| < p$, whence $i=j$. It follows that all of the numbers $f(1), f(2), \ldots, f(100)$ are distinct and less than 100.
We will now show that if $f(a) + f(b) = f(c) + f(d)$ for $1 \leq a, b, c, d \leq 100$, then $\{a,b\} = \{c,d\}$. If the equation holds, then $2p((a+b)-(c+d)) = [c^2]_p + [d^2]_p - ([a^2]_p + [b^2]_p)$. The right-hand side is divisible by $2p$ and has absolute value less than $2p$, so both sides are 0. Hence, $a+b=c+d$ and $a^2 + b^2 \equiv c^2 + d^2 \pmod{p}$. But $a^2 + b^2 + 2ab = c^2 + d^2 + 2cd$, so $ab \equiv cd \pmod{p}$. Since $a+b \equiv c+d \pmod{p}$ as well, $c$ and $d$ must be the two roots of the quadratic $t^2 - (a+b)t + ab$ mod $p$, whence $\{a, b\} \equiv \{c, d\} \pmod{p}$.
Without loss of generality, suppose that $a \equiv c \pmod{p}$. Since $|a-c| < 100$, we must have $a=c$, and therefore that $b=d$. The result follows immediately.
SCP
20.03.2011 11:47
Zhero wrote:
Let $p = 101$, let $[n]_p$ denote the remainder when $n$ is divided by $p$, and let $f(n) = 2pn + [n^2]_p$. We claim that the set $\{f(1), f(2), \ldots, f(100)\}$ satisfies the conditions of the problem.
For all $i \leq 100$, $f(i) = 2pi + [i^2]_p < 20200 + 101 < 25000$. In addition, for $1 \leq i,j \leq 100$, $f(i) = f(j)$ implies $|2p(i-j)| = |[i^2]_p - [j^2]_p| < p$, whence $i=j$. It follows that all of the numbers $f(1), f(2), \ldots, f(100)$ are distinct and less than 100.
We will now show that if $f(a) + f(b) = f(c) + f(d)$ for $1 \leq a, b, c, d \leq 100$, then $\{a,b\} = \{c,d\}$. If the equation holds, then $2p((a+b)-(c+d)) = [c^2]_p + [d^2]_p - ([a^2]_p + [b^2]_p)$. The right-hand side is divisible by $2p$ and has absolute value less than $2p$, so both sides are 0. Hence, $a+b=c+d$ and $a^2 + b^2 \equiv c^2 + d^2 \pmod{p}$. But $a^2 + b^2 + 2ab = c^2 + d^2 + 2cd$, so $ab \equiv cd \pmod{p}$. Since $a+b \equiv c+d \pmod{p}$ as well, $c$ and $d$ must be the two roots of the quadratic $t^2 - (a+b)t + ab$ mod $p$, whence $\{a, b\} \equiv \{c, d\} \pmod{p}$.
Without loss of generality, suppose that $a \equiv c \pmod{p}$. Since $|a-c| < 100$, we must have $a=c$, and therefore that $b=d$. The result follows immediately.
Do you not only look to one possible set?
Zhero
22.03.2011 23:09
What do you mean?
SCP
22.03.2011 23:12
Zhero wrote: What do you mean? They constructed a set with such functions, and show it isn't a good one. But they didn't prove it is so with all ones.
alex443399
07.10.2019 02:24
SCP wrote: Do you not only look to one possible set? They found a sequence which complies with the requirement. Which means that it is possible to find a set of 100 numbers with that property
Justanaccount
21.04.2021 07:59
PUTNAM 1994 B6 kills this problem instantly.
Sprites
17.08.2021 20:34
We will prove that for any $p$,we can find $p-1$ numbers $a_1,.....,a_{p-1}$ less than $2p^2$ with their pairwise sums different (then we just plug in $p=101$ to get the result)
If $a$ is an integer then define $a'$ to be the remainder obtained when $a$ is divided by $p$
Now choose $a_n=2np+n^{2'}$
Clearly,$\max(a_i)=a_{p-1}=2p(p-1)+(p-1)^{2'}<2p(p-1)+p<2p^2$ and it remains to check that the pairwise sums are all distinct.
Now for the sake of contradiction assume that $a_n+a_m=a_k+a_l$ for some $n \neq m$ and $k \neq l$ between $1$ and $p-1$.
Note that this is equivalent to $2p(n+m-k-l)=k^{2'}+l^{2'}-m^{2'}-n^{2'}-------(1)$
The right hand side is between $2-2(p-1)$ and $2(p-1)-2$,so $n+m=k+l$
Now $n^2+m^2 \equiv k^2+l^2 \pmod p$(from $(1)$) and combining this gives $nm \equiv lk \pmod p$
Thus to conclude by the general method for such cases consider a polynomial $P(X)=(X-m)(X-n)-(X-l)(X-k)$ are multiples of $p$,hence choose $m=l$ and $n=k$ or $m=k$ and $n=l$ for stewing up a contradiction,hence we have exhausted all possibilities and the result is clear by substituting $p=101$
awesomeming327.
12.06.2024 17:53
The answer is yes. Let the remainder of $n^2$ upon division by $101$ be $r_n$. Then consider the numbers $202n+r_n$ for $n=1,2,\dots,100$. Suppose that not all pairwise sums are different then \[202(a+b)+r_a+r_b=202(c+d)+r_c+r+d\]for some $1\le a,b,c,d\le 100$, all distinct. Note that $202(a+b-c-d)=r_c+r_d-r_a-r_b$. Since $0\le r_i\le 100$ for all $i$, $|r_c+r_d-r_a-r_b|\le 200$ and $202(a+b)-202(c+d)$ is either $0$ or has absolute value at least $202$. The latter is impossible so it is zero, meaning $a+b=c+d$. Now, $a^2+b^2\equiv c^2+d^2\pmod{101}$ and $(a+b)^2\equiv (c+d)^2\pmod{101}$ implies $2ab\equiv 2cd\pmod{101}$ and as a result, $(a-b)^2\equiv (c-d)^2\pmod{101}$. If $a-b\equiv c-d\pmod{101}$ then adding $a+b\equiv c+d\pmod{101}$ gives $a\equiv c\pmod{101}$, contradiction. If $a-b\equiv d-c\pmod{101}$ then adding $a+b=c+d$ gives $a\equiv d\pmod{101}$, also contradiction. Therefpre, all pairwise sums are different, and the largest number is between $20200$ and $20300$.
Ritwin
26.08.2024 07:39
Yes. The idea is to instead work in two dimensions, and then show that construction can be edited to work in one dimension. Claim: Let $p \geq 3$ be a prime. Let $S$ be the set of vectors $\langle n, n^2 \bmod p \rangle$ for $n \in \{0, 1, \ldots, p-1\}$. Then the pairwise sums of elements of $S$ are distinct. Proof. If $a+b \equiv c+d$ and $a^2+b^2 \equiv c^2+d^2$ then $ab \equiv cd \pmod p$, and by unique factorization of $t^2 - (a+b) t + ab$ in $\mathbb Z/p\mathbb Z$ we have $\{a, b\} = \{c, d\}$. $\square$ Use the above claim with $p = 101$. All vectors lie in $({\mathbb Z}/p{\mathbb Z})^2$, so we can apply the mapping $\langle x, y \rangle \mapsto 1 + x + 2py$ to $S$, which will give $p$ integers in $[1, 2p^2+p+1]$, and preserve the "pairwise sums are distinct" property. $\blacksquare$