China-TST-2025A

Proof: For a finite multiset $S$ of integers, let $\sigma (S)$ denote the sum of all elements in $S$ (counting multiplicities), and let $\Sigma (S)=\{\sigma (T)\mid \sigma (T)\ne T\subseteq S\}$, where $\Sigma (S)$ is treated as a set (ignoring multiplicities). Let ${\Sigma }_n(S)$ denote the set of congruence classes modulo $n$ of the elements in $\Sigma (S)$. For $x\in \mathbb{Z}$, let $\bar{x}$ denote the congruence class of $x$ modulo $n$. Under this notation, conditions (2) and (3) can be written as $${\Sigma }_n(\{a_1,a_2,\dots ,a_k\})=\{\bar{1},\bar{2},\dots ,\bar{\ell }\}.$$ Step 1: The main idea is to add an element $x$ to a nonempty multiset $S$, obtaining $T=S\cup \{x\}$. Assuming that neither ${\Sigma }_n(S)$ nor ${\Sigma }_n(T)$ contains $\bar{0}$, we compare ${\Sigma }_n(S)$ and ${\Sigma }_n(T)$. In particular, if ${\Sigma }_n(T)$ contains exactly one more element than ${\Sigma }_n(S)$, we can deduce a very refined structure for ${\Sigma }_n(S)$. Observe that $$\Sigma (T)=\Sigma (S)\cup (\Sigma (S)+x)\cup \{x\},$$ so ${\Sigma }_n(S)\subset {\Sigma }_n(T)$. Moreover, $\overline{\sigma (S)+x}$ belongs to ${\Sigma }_n(T)$ but not to ${\Sigma }_n(S)$, since otherwise ${\Sigma }_n(T)$ would contain $\bar{0}$. Hence, ${\Sigma }_n(S)⊊{\Sigma }_n(T)$. If ${\Sigma }_n(T)$ contains exactly one more element than ${\Sigma }_n(S)$, then this new element must be $\overline{\sigma (S)+x}$. However, $\bar{x}\in {\Sigma }_n(T)$, and $\bar{x}\ne \overline{\sigma (S)+x}$, so $\bar{x}\in {\Sigma }_n(S)$. Let $d=\frac{n}{\text{gcd}(x,n)}$, where $d$ is the smallest positive integer such that $d\bar{x}=\bar{0}$. Suppose $\bar{x},2\bar{x},\dots ,p\bar{x}\in {\Sigma }_n(S)$, but $(p+1)\bar{x}\notin {\Sigma }_n(S)$. A set of the form $$\{\bar{a},\overline{a+x},\overline{a+2x},\dots ,\overline{a+(d-1)x}\}$$ is called a coset of $\bar{x}$. The congruence classes modulo $n$ can be partitioned into $\frac{n}{d}$ cosets of $\bar{x}$. If ${\Sigma }_n(S)$ contains some elements of a coset $C$ of $\bar{x}$ but not the entire coset, then $({\Sigma }_n(S)\cap C)+\bar{x}$ will produce new elements not in ${\Sigma }_n(S)\cap C$. Since ${\Sigma }_n(T)$ contains only one more element than ${\Sigma }_n(S)$, it follows that ${\Sigma }_n(S)$ must consist of several complete cosets of $\bar{x}$ and one incomplete coset. This incomplete coset can only be $\{\bar{x},2\bar{x},\dots ,p\bar{x}\}$, and the new element in ${\Sigma }_n(T)$ is $(p+1)\bar{x}$, which must equal $\overline{\sigma (S)+x}$. Therefore, $\overline{\sigma (S)}=p\bar{x}$. Step 2: Returning to the original problem, first add $n-1-\ell$ copies of 1 to $\{a_1,a_2,\dots ,a_k\}$, obtaining a multiset $S$. It is easy to see that $m:=|S|=k+(n-1)-\ell \ge \frac{n+1}{2}$ (using condition (1)), and $${\Sigma }_n(S)=\{\bar{1},\bar{2},\dots ,\overline{n-1}\}.$$ Let the elements of $S$ be ordered as $b_1\le b_2\le \cdots \le b_m$. Then $b_1=1$ (using condition (1), $\ell \le n-2$, so $S$ contains at least one 1), and $b_m<n$. If for every $2\le i\le m$, we have $b_i\le 1+b_1+\cdots +b_{i-1}$, then by induction, it follows that $$\Sigma (S)=\{1,2,\dots ,b_1+b_2+\cdots +b_m\}.$$ Since ${\Sigma }_n(S)=\{\bar{1},\bar{2},\dots ,\overline{n-1}\}$, it must be that $b_1+b_2+\cdots +b_m=n-1$. Removing the added $n-1-\ell$ copies of 1, we obtain $$a_1+a_2+\cdots +a_k=\ell .$$ Now suppose there exists $2\le i\le m$ (take the smallest such $i$) such that $b_i>1+b_1+\cdots +b_{i-1}$. Let $s=b_1+\cdots +b_{i-1}\ge i-1$. Then $$\Sigma (\{b_1,\dots ,b_{i-1},b_i\})=\{1,2,\dots ,s,b_i,b_i+1,\dots ,b_i+s\}.$$ Since $b_i<n$, we have $b_i+s<n$ (otherwise $\overline{0}\in {\Sigma }_n(S)$), so $$|{\Sigma }_n(\{b_1,\dots ,b_i\})|=2s+1\ge 2i-1.$$ Now, iteratively add the remaining elements to $\{b_1,\dots ,b_i\}$ such that at each step, ${\Sigma }_n$ gains at least two new elements, until no more can be added. Suppose we obtain $T\subset S$ with $|T|=t\ge i$, satisfying $$|{\Sigma }_n(T)|\ge 2i-1+2(t-i)=2t-1.$$ It follows that $t<m$, since otherwise $|{\Sigma }_n(T)|\ge 2m-1\ge n$, which is a contradiction. Now, the remaining elements must each add only one new element to ${\Sigma }_n$ when included in $T$. Claim: The remaining elements are all identical. Suppose $x$ and $y$ are remaining elements, and both ${\Sigma }_n(T\cup \{x\})$ and ${\Sigma }_n(T\cup \{y\})$ contain exactly one more element than ${\Sigma }_n(T)$. By the conclusion of Step 1, ${\Sigma }_n(T)$ consists of several complete cosets of $\bar{x}$ and one incomplete coset $\{\bar{x},2\bar{x},\dots ,p\bar{x}\}$, with $\overline{\sigma (T)}=p\bar{x}$. Since ${\Sigma }_n(T\cup \{y\})$ contains only one more element, $\overline{\sigma (T)+y}=\bar{y}+p\bar{x}$, it follows that $\bar{y},\bar{y}+\bar{x},\dots ,\bar{y}+(p-1)\bar{x}\in {\Sigma }_n(T)$, but $\bar{y}+p\bar{x}\notin {\Sigma }_n(T)$. Therefore, $\bar{y}$ cannot belong to a complete coset of $\bar{x}$ in ${\Sigma }_n(T)$, so it must be in $\{\bar{x},2\bar{x},\dots ,p\bar{x}\}$. Consequently, $$\{\bar{y},\bar{y}+\bar{x},\dots ,\bar{y}+(p-1)\bar{x}\}\subset \{\bar{x},2\bar{x},\dots ,p\bar{x}\},$$ which implies $\bar{y}=\bar{x}$, i.e., $x=y$. The claim is proved. Thus, the remaining elements are all equal to some $x$. Each time we add $x$, ${\Sigma }_n$ gains exactly one new element, successively adding $(p+1)\bar{x},(p+2)\bar{x},\dots ,(d-1)\bar{x}$. In the final step, $S=T_1\cup \{x\}$, and the new element added to ${\Sigma }_n$ is $(d-1)\bar{x}=\overline{\sigma (T_1)+x}=\overline{\sigma (S)}$, so $\bar{x}=-\overline{\sigma (S)}$. Earlier, when we added 1 to $\{a_1,a_2,\dots ,a_k\}$ to obtain $S$, each addition also introduced exactly one new element to ${\Sigma }_n$. Considering the last addition, $S=T_2\cup \{1\}$, we similarly deduce $\overline{1}=-\overline{\sigma (S)}$, so $x=1$. This means that in the previous process, the remaining elements were all 1. However, this is impossible because we had already taken $\{b_1,\dots ,b_i\}$ with $b_i>1$, which includes all the 1's. This contradiction completes the proof. $\square$