Ways of choosing $16$ integers from first $150$ integers such that there is no $(a,b,c,d)$ for which $a+b=c+d$

Here is a problem I found out recently:

In how many ways one can choose $16$ distinct positive integers from first $150$ positive integers such that there are no $4$ distinct ones $(a,b,c,d)$ for which $a+b=c+d$?

My approach:

If $a+b=c+d$, then $a-c=d-b$. There are $149$ differences from the first $150$ positive integers. We have to choose $\binom{16}{2}=120$ differences. So, the answer is $\binom{149}{120}$.

I'm confused with my approach.
Edit: My solution is not correct.

So, what is the correct solution to the problem? And I noticed that it is hard to find out such $16$ integers. So, if choosing $16$ such numbers is not possible, how to prove that? Any helpful approach is welcome.

Source: The problem is self-made and inspired from a problem from the book 102 Combinatorial Problems: From The Training of The USA IMO Team by Titu Andreescu and Zuming Feng.

Solution 1:

There is a solution!

Despite my doubts for much of this time, expecting the answer to be that a solution could not be found without going above 150, it turns out that there is a valid solution.

The solution that I have found is:

$$ 1,4,6,7,33,50,60,69,94,107,119,127,131,135,142,149 $$

I have confirmed that all 120 sums of two values are unique. Note that a second solution is the same as this, except with each value replaced with 150 minus the value.

The value was found by my code, after maybe 2 days of run time. The code is still running, so it may find more solutions.

Previous observations...

To assist in seeking an answer to this, I have investigated the equivalent questions for smaller numbers. In particular, what's the smallest number of "first $n$ integers" that you need to be able to choose $k$ integers satisfying the condition. For each of the numbers presented here, I have used code to confirm that it cannot be done with a smaller range of values.

In the table below, the set of solutions are "up to reversal" - this is because, if you replace all values, $s$, in the solution with $n+1-s$, you get another solution, and thus all solutions come in equivalent pairs. For example, $[1,2,3,5,8]$ and $[1,4,6,7,8]$ are identical, up to reversal.

$$\begin{array}{c|c|c} \hline\text{choose $k$ integers} & \text{from first $n$ integers} & \text{Solutions (up to reversal)} \\ \hline 5 & 8 & [1,2,3,5,8] \\ \hline 6 & 13 & \begin{array}{c}[1,2,3,5,8,13]\\ [1,2,3,7,10,13]\end{array} \\ \hline 7 & 19 & \begin{array}{c}[1,2,3,5,9,14,19]\\ [1,2,3,8,11,15,19]\end{array} \\ \hline 8 & 25 & [1,2,3,5,9,15,20,25] \\ \hline 9 & 35 & \begin{array}{c}[1,2,3,5,9,16,25,30,35]\\ [1,2,3,8,14,17,27,31,35]\\ [1,2,3,15,20,25,28,31,35]\end{array} \\ \hline 10 & 46 & [1,2,8,11,14,22,27,42,44,46] \\ \hline 11 & 58 & \begin{array}{c}[1,2,6,10,18,32,35,38,45,56,58]\\ [1,2,6,10,18,32,34,45,52,55,58]\end{array} \\ \hline 12 & 72 & \begin{array}{c}[1,2,3,8,13,23,38,41,55,64,68,72]\\ [1,2,12,19,22,37,42,56,64,68,70,72]\end{array} \\ \hline 13 & 87 & [1,2,12,18,22,35,43,58,61,73,80,85,87] \\ \hline 14 & 106 & \left[\begin{array}{c}1,2,7,15,28,45,55,67,\\70,86,95,102,104,106\end{array}\right] \\ \hline 15 & 127 & \left[\begin{array}{c}1,2,3,23,27,37,44,51,81,\\96,108,111,114,119,127\end{array}\right]\\ \hline \end{array}$$

Some insights:

1. The increase in $n$ needed to increase $k$ by 1 seems to grow each time (with the only exception being 13->19->25 - the differences between $n$ values go 5,6,6,10,11,12,14,15,19 - this is not overly surprising, but worth noting.

2. The density of sums within the possible range can be calculated relatively easily. There are $\frac{k(k-1)}2$ pairs within the set, and thus that many sums if no two are the same. There are $2n-3$ possible sums creatable from a pair of numbers between $1$ and $n$ (as the sum cannot be $1$, $2$, or $2n$). Therefore, the density is given by $\frac{k(k-1)}{2(2n-3)}$ - the resulting densities are (approximately) 76.9%, 65.2%, 60.0%, 59.6%, 53.7%, 50.6%, 48.7%, 46.8%, 45.6%, and 43.5%.

3. All optimal solutions found so far (accounting for reversal) can be written with $[1,2...$ at the start.

4. Interestingly, while a solution for $k=15$ can be found with $n=127$, no such solution can be found for $n=128$ if you require both 1 and 128 in the set.

Approaches I have used to try to find solutions:

1. A code that seeks the solution in an "additive" approach - find which values can be added to the existing set you have, and keep expanding until you run out of values, then backtrack and try a new value. With careful coding to ensure it minimises the search space reasonably well, this can find all optimal solutions for up to $k=14$ within a reasonable amount of time, if you input the correct $n$ in (and can similarly be used to confirm that no lower $n$ will work). However, for larger $n$, it becomes a lot more unwieldy.

2. A greedy code that seeks the solution in a "subtractive" approach - start with all possible values in the same set (so, 1 through 150 for the actual question), then remove numbers based on which ones will reduce the number of "collisions" (sums that appear multiple times) by the most - with some randomness where multiple numbers can achieve the same reduction... and then add numbers back if they don't substantially increase the number of collisions. This can find many solutions quite quickly for "easy" cases, but due to the random aspect, is also pretty slow to find optimal values for larger $n$. A non-random approach is likely to be very, very slow, as you start with a lot of numbers and there are a lot of options for removal.

3. Take a smaller solution, such as for $k=12$ ($n=72$), then rescale the numbers and try to fill the gaps. For example, multiplying the first $k=12$ solution by 2 gives $[2,4,6,16,26,46,76,82,110,128,136,144]$. From here, we can find that $[31,89,147]$ is capable of being added, for a total of $k=15$... but despite various attempts, I have not succeeded in reaching $k=16$ using this approach.