What is the maximum possible sum?

Question

What is the maximum possible sum of the elements one can choose from the set $\{1, 2, . . . , 99 \}$ such that all their pairwise sums $a_i + a_j , i < j$, would be different?

Answer 1

I'll start things off with 856.

Set {99, 98, 97, 95, 92, 87, 79, 70, 61, 47, 26, 5} obtained with the greedy method. I tried a few other starting seeds and got lower values.

This is 100 - A011185.

The phrase you'll need to search is Sidon sequence. This is a 12-term Sidon sequence. According to the linked paper, the densest 13-term Sidon sequence uses the number 101, just above your cut-off. Therefore, the greedy 12-term sequence is best.

Answer 2

You can solve the problem via integer linear programming as follows. For $i \in\{1,\dots,99\}$, let binary decision variable $x_i$ indicate whether element $i$ is selected. For each pair $(i,j)$ with $1 \le i < j \le 99$, let binary (optionally, nonnegative) decision variable $y_{i,j}$ indicate whether that pair appears (that is, $y_{i,j}=x_i x_j$). The problem is to maximize $\sum_{i=1}^{99} i x_i$ subject to \begin{align} x_i + x_j - 1 &\le y_{i,j} &&\text{for $1 \le i < j \le 99$} \tag1 \\ \sum_{i<s-i} y_{i,s-i} &\le 1 &&\text{for $s\in\{3,\dots,197\}$} \tag2 \\ \end{align} Constraint $(1)$ enforces the logical implication $x_i \land x_j \implies y_{i,j}$, equivalently, $x_i x_j \le y_{i,j}$. Constraint $(2)$ enforces that each pairwise sum $s$ appears at most once. As @Gabriel Burns observed, you can optionally impose an additional constraint $\sum_{i=1}^{99} x_i \le 20$.

The maximum sum turns out to be $879$, attained by $$\{17,35,53,65,70,75,84,91,95,97,98,99\}.$$