6
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ Can you provide som examples ? I find it really hard to understand $\endgroup$
    – Fabich
    May 3, 2016 at 13:45
  • $\begingroup$ @Lordofdark example is enough or should I rewrite the question? sorry for not being that clear :( $\endgroup$
    – Oray
    May 3, 2016 at 13:49
  • 1
    $\begingroup$ @Oray I think the question is pretty clear personally $\endgroup$ May 3, 2016 at 13:50
  • $\begingroup$ @Oray thank you for example, it is very clear now :) $\endgroup$
    – Fabich
    May 3, 2016 at 13:55
  • 1
    $\begingroup$ Such sets of special integers are also known as "Sidon sets"; en.wikipedia.org/wiki/Sidon_sequence $\endgroup$
    – Gamow
    May 3, 2016 at 14:18

5 Answers 5

9
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ This answer guarantees that $20402$ is the minimum greatest value of the set? I missed this part, could you clarify that? $\endgroup$ May 4, 2016 at 12:05
  • 1
    $\begingroup$ @MariusSiuram From what I could gather from the Wikipedia page, finding the optimal set for n > 27 is an open problem. $\endgroup$
    – ffao
    May 4, 2016 at 17:17
  • $\begingroup$ Ok, then I won't complain about this "not being an answer" ;) --as you say, it is state of the art on the answer hehe $\endgroup$ May 5, 2016 at 7:09
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ @MariusSiuram I believe you're correct about powers of 2 being an upper bound $\endgroup$
    – Paul Evans
    May 3, 2016 at 14:26
  • $\begingroup$ I was correct about upper bound but provided an invalid counterexample. The valid counterexample: Set 1, 2, 4, 8, 13 is better than 1, 2, 4, 8, 16 $\endgroup$ May 3, 2016 at 14:38
0
$\begingroup$

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}$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ It cannot be an upper bound as the last number could be any large number. In your set (20+22) = (21+21). So yours is not valid. $\endgroup$
    – thepace
    May 3, 2016 at 14:23
  • 1
    $\begingroup$ The set 1, 2, 4, 8, 13 is better than 1, 2, 4, 8, 16 (in regards of the question). So your constructive solution is not yielding optimum for all $n$. $\endgroup$ May 3, 2016 at 14:36
  • $\begingroup$ I meant an upper bound for the answer, not for any "special number set". Given that powers of two is a valid special number set, the answer to the question is guaranteed to be less than $2^{100}$ $\endgroup$ May 3, 2016 at 14:44
  • $\begingroup$ Your answer is incorrect, it sure is a first approach, but not the answer $\endgroup$ May 3, 2016 at 14:44
-2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Why not 1-2-4-7-12? $\endgroup$
    – Trenin
    May 3, 2016 at 14:13
  • $\begingroup$ 4+4 = 8 = 7+1, so that one is not correct $\endgroup$ May 3, 2016 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.