75th NMO Selection Tests

a) Two real numbers (not necessarily distinct) always form a suitable collection. Let $n\ge 3$ and consider the initial collection. Note that any $a$ can be paired off with some $b\ne a$ to form an eligible pair: Otherwise, $a+b=s+1=a+c$ for distinct $b,c\ne a$, so $b=c$, contradicting the fact that the initial numbers are pairwise distinct. Hence the initial collection is suitable.

Choose an eligible pair $a_1,a_2$ and use the formula to replace them by $b_1$. As the remaining numbers are pairwise distinct, there is at most one that cannot be paired with $b_1$ to form an eligible pair, so there are at least $n-2$ candidates to form an eligible pair with $b_1$. Let $a_3$ be one such and use the formula to replace $b_1$ and $a_3$ by $b_2$. Repeat the argument to replace $b_2$ and some $a_4$ by $b_3$ and so on and so forth all the way down to some $b_{n-2}$ and $a_n$ (possibly, $b_{n-2}=a_n$). These latter form an eligible pair, so they can be replaced by a single number.

b) Let $c_1,c_2,\dots ,c_n$ be the initial numbers. The final number is ${\sum }_i{c}_i+{\sum }_{i<j}{c}_i{c}_j$. This is clearly the case if $n=2$, so let $n\ge 3$.

Consider a generic stage $x_1,x_2,\dots ,x_m$ and let $s=x_1+x_2+\cdots +x_m$. We will prove that $s+{\sum }_{1\le i<j\le m}{x}_i{x}_j$ does not change upon passing to the next stage. Let $x$ be the number obtained by replacing an eligible pair $(x_k,x_{\ell })$. Then $s$ changes by $x-x_k-x_{\ell }$ and the other sum changes by $-x_k{x}_{\ell }-(x_k+x_{\ell })(s-x_k-x_{\ell })+x(s-x_k-x_{\ell })$, so the overall change is $$x-x_k-x_{\ell }-x_k{x}_{\ell }-(x_k+x_{\ell })(s-x_k-x_{\ell })+x(s-x_k-x_{\ell }).$$ Finally, express $x$ in terms of $s$, $x_k$ and $x_{\ell }$ and carry out calculations to show that the overall change vanishes, whence the desired invariance.