The general motivation for $S$ is the technique of monovariants. To show that the desired state (no more quarrels) will happen eventually, we show that we are always "making progress" toward the state in some sense. To show that we are making progress, we need to have a way to track progress.
The specific formula for $S$ is:
- Justified in its existence by our later proof that it will decrease every day until we're done. That's all we need for this proof to work, and so you can think of $S$'s definition as an "algebraic trick".
- Intuitively motivated as the following quantity: how many pairs of people living in the same apartment are there? It makes sense that this quantity ought to decrease when the inhabitants of a crowded apartment split up.
Why does the quantity change? Well, the number of people in different apartments changes. Suppose that on day 1, we have $19$ residents in the first apartment ($a_1 = 19$), $5$ residents in each of the next $20$ apartments ($a_2 = a_3 = \dots = a_{21} = 5$) and nobody in any of the other apartments ($a_{22} = \dots = a_{119} = 0$). Then on day 1, we have $$S = \binom {19}{2} + 20 \cdot \binom 52 + 99 \cdot \binom 02 = 371.$$
On day 1, the inhabitants of the first apartment quarrel. Let's say that all $19$ of them move to already-populated apartments. Now $a_1 = 0$, $a_2, \dots, a_{20}$ increase to $6$, and the rest stay the same. On day 2, we have
$$
S = \binom 02 + 19 \cdot \binom 62 + \binom 52 + 99 \cdot \binom 02 = 310.
$$
To solve the extension (and give a simpler proof!), we prove the following claim:
Claim. For $k\le 15$, in order for there to be at least $k$ apartment fights, on day $1$ there must be at least $k$ different apartments with $16-k$ or more people.
Proof. Suppose there have been $k$ apartment fights, for some $k\le 15$. An apartment that's had a fight gains a person after every subsequent fight, for at most $k-1<15$ people by the end; so no apartment can have had two fights yet. Therefore all $k$ fights have been in different apartments. By symmetry, let's assume the $i^{\text{th}}$ fight has been in apartment $i$.
Then apartment $i$ has gained at most one person after each of the first $i-1$ fights: $i-1$ new people total. In order to have at least $15$ people for the $i^{\text{th}}$ fight, it must have started out with at least $15 - (i-1) = 16-i$ people. In particular, apartments $1, 2, \dots, k$ all must have at least $16-k$ people. QED
Without loss of generality, assume that $a_1 \ge a_2 \ge \dots \ge a_{120}$ on day 1. The the condition in the claim says that $a_k \ge 16-k$.
This condition cannot hold for all of $k=1, 2, \dots, 15$. If it did, we'd get $a_1 \ge 15$, $a_2 \ge 14$, $a_3 \ge 13$, and so on through $a_{15} \ge 1$. But then there are at least
$$
a_1 + a_2 + \dots + a_{15} \ge 15 + 14 + \dots + 1 = 120
$$
people, and we know there are only $119$.
Therefore $15$ fights cannot happen, and so the process must be completed after the $14^{\text{th}}$ day. This bound is tight: one way to have the process last $14$ days is to start with populations
$$
a_1 = 15, a_2 = 14, a_3 = 13, \dots, a_{14} = 2, a_{15} = \dots = a_{120}=0
$$
and have the $15$ inhabitants of an apartment go to the first $15$ other apartments by number after each fight.
Best Answer
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:
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.
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%.
All optimal solutions found so far (accounting for reversal) can be written with $[1,2...$ at the start.
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:
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.
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.
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.