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$
  • 2
    $\begingroup$ Can you provide som examples ? I find it really hard to understand $\endgroup$ – Fabich May 3 '16 at 13:45
  • $\begingroup$ @Lordofdark example is enough or should I rewrite the question? sorry for not being that clear :( $\endgroup$ – Oray May 3 '16 at 13:49
  • 1
    $\begingroup$ @Oray I think the question is pretty clear personally $\endgroup$ – Gordon Allocman May 3 '16 at 13:50
  • $\begingroup$ @Oray thank you for example, it is very clear now :) $\endgroup$ – Fabich May 3 '16 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 '16 at 14:18
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$
  • $\begingroup$ This answer guarantees that $20402$ is the minimum greatest value of the set? I missed this part, could you clarify that? $\endgroup$ – MariusSiuram May 4 '16 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 '16 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$ – MariusSiuram May 5 '16 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$
  • $\begingroup$ @MariusSiuram I believe you're correct about powers of 2 being an upper bound $\endgroup$ – Paul Evans May 3 '16 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$ – MariusSiuram May 3 '16 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$
  • $\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 '16 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$ – MariusSiuram May 3 '16 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$ – MariusSiuram May 3 '16 at 14:44
  • $\begingroup$ Your answer is incorrect, it sure is a first approach, but not the answer $\endgroup$ – Mario Garcia May 3 '16 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$
  • $\begingroup$ Why not 1-2-4-7-12? $\endgroup$ – Trenin May 3 '16 at 14:13
  • $\begingroup$ 4+4 = 8 = 7+1, so that one is not correct $\endgroup$ – Mario Garcia May 3 '16 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.