101 special numbers

Question

There are 101 special positive integer numbers (1,2,3...) you need to find for this question.

What is the minimum value of the biggest number of these 101 numbers that provides all sums of any two numbers among these (including the same numbers chosen, like 1+1) are different than each other?

For Examples: Let say the question is asked for 3 special positive integer numbers, the result would be 4.

1,2,4 would be the answer since (1+1), (1+2), (1+4), (2+2), (2+4), (4+4) would be different from each other.

Answer 1

Here is a construction (going back to the Hungarian mathematician Simon Sidon) that yields an example with largest number $2\cdot101^2=20402$.

Construction: For $k=1,2,\ldots,101$ set $x_k=202k+(k^2\bmod 101)$.

Hence $x_1=202+1=203$, and $x_2=404+4=408$, and $x_3=606+9=615$, and so on.

Suppose for the sake of contradiction that there exist two distinct pairs $(a,b)$ and $(c,d)$ with $a\le b$ and $c\le d$, so that $$ x_a+x_b ~=~ x_c+x_d. $$ Then the trivial bounds $202k\le x_k< 202k+101$ imply that \begin{eqnarray*} 202(a+b) ~\le~ &x_a+x_b& <~ 202(a+b+1)\\ 202(c+d) ~\le~ &x_c+x_d& <~ 202(c+d+1) \end{eqnarray*} Since $x_a+x_b=x_c+x_d$, we conclude from this that $$a+b=c+d.$$ Furthermore, we get that $$(a^2\bmod 101)+(b^2\bmod 101)=(c^2\bmod 101)+(d^2\bmod 101),$$ which implies $$a^2+b^2 ~\equiv~ c^2+d^2 \pmod{101}.$$ But then modulo $101$ we also have $$(a-b)^2 ~\equiv~ 2(a^2+b^2)-(a+b)^2 ~\equiv~ 2(c^2+d^2)-(c+d)^2 ~\equiv~ (c-d)^2.$$ Hence $a+b=c+d$ and $a-b=\pm(c-d) \bmod 101$. Since $101$ is prime, this implies (together with $a\le b$ and $c\le d$) that $a=c$ and $b=d$. Contradiction.

Answer 2

EDIT: Thanks to MariusSiuram the upper bound is

$2^{100}$

Because

The sum of any two of $2^0, 2^1, 2^2, 2^3 \dots 2^{100}$ are differet.

Answer 3

I will present a bound, but not the solution --not yet! :(

If there are $101$ numbers, then there are $5151$ different pairs. Given that each pair has to yield a different sum, the greatest sum will be, at least, $5151$.

Now, the greatest sum is expected to be $A_n + A_{n+1}$ where $A_n$ is the number asked in the question, and $A_{n+1} < A_n$. Then, the minimum value is when $A_n = 2576$.

So, in general, we can affirm that the solution is greater than $2576$.

I will keep working in a better lower bound, an upper bound and a solution, let's see what comes first.

EDIT: An upper bound, as some answers state is the set $A = \lbrace 2^i \rbrace_i$, which gives $2^{100}$. So we can affirm that the solution is less than $2^{100}$

Answer 4

For n=1 => 1
For n=2 => 1,2
For n=3 => 1,2,4
For n=4 => 1,2,4,8
For n=101 => 1,2,4,8, ......, 2^100
So the required answer is 2^100.

Answer 5

Got it...hope this one counts as valid

I think it could be

13

I know, you will be thinking. wtf? that is not even close but...

Is the question saying there are 101 numbers? Or...are there just 5 numbers? (101 binary). I took the second option, and with that premise, I think 13 is correct
1 - 2 - 4 - 8 - 13
2 = 1+1
3 = 1+2
5 = 1+4
9 = 1+8
14= 1+13
4 = 2+2
6 = 2+4
10= 2+8
15= 2+13
8 = 4+4
12= 4+8
17= 4+13
16= 8+8
21= 8+13
26= 13+13