I was trying to prove the following
Proposition:
Let $A=\{a_1,\ldots, a_k\}$ and $B=\{b_1,\ldots, b_k\}$ be two multisets (repetition is allowed)
with $|A|=|B|=k$. Also $0\le a_1\le a_2\le\ldots \le a_k$ and $0\le b_1\le
\ldots \le b_k$. If $A$ and $B$ have the same subset sums, then $A=B$.
Same subset sums means that for every $A_i\subseteq A$, there is a $B_i\subseteq B$ such that the sum of elements of $A_i$ is equal to the sum of elements of $B_i$. Also just to clarify, if a number arises $x$ times as a subset sum from $A$, then it should arise $x$ times from $B$.
I believed that I found a proof:
Clearly, $a_1=b_1$ since they are the smallest subset sums of $A$ and $B$ respectively.
Let $S(A
_i)$ denote the sum of elements of $A_i$.
We must also have $\sum_{A_i\subseteq A}x^{S(A_i)}=\prod_{i=1}^k(1+x^{a_i})=\prod_{i=1}^k(1+x^{b_i})=\sum_{B_i\subseteq B}x^{S(B_i)}$ (since they have the same subset sums).
Since $a_1=b_1$, we cancel from the products the factors $(1+x^{a_1})$ and $(1+x^{b_1}$) and we are left with $\prod_{i=2}^k(1+x^{a_i})=\prod_{i=2}^k(1+x^{b_i})$. This shows that the sets $A-\{a_1\}, B-\{b_1\}$ have the same subset sums. We repeat this process until $a_k=b_k$.
Question: Is there another more "simple" proof of this proposition?
(If the proof I presented is correct)
Best Answer
Your basic approach of induction on the number of elements in the multisets is a good one. I think you can simplify it by saying that any $A_i$ that includes $a_1$ must have a matching $B_i$ that includes an element equal to $b_1$ because otherwise $A_i\setminus a_1$ would have no matching multiset. Now you can delete $a_1,b_1$ from any pair that have both of them and get to your claim that $A\setminus a_1$ and $B \setminus b_1$ have mathching subset sums.