A subsum of $n$ real numbers $a_1,\dots,a_n$ is a sum of elements of a subset of the set $\{a_1,\dots,a_n\}$. In other words a subsum is $\epsilon_1a_1+\dots+\epsilon_na_n$ in which for each $1\leq i \leq n$ ,$\epsilon_i$ is either $0$ or $1$. Years ago, there was a valuable list containing $n$ real not necessarily distinct numbers and their $2^n-1$ subsums. Some mysterious creatures from planet Tarator has stolen the list, but we still have the subsums. (a) Prove that we can recover the numbers uniquely if all of the subsums are positive. (b) Prove that we can recover the numbers uniquely if all of the subsums are non-zero. (c) Prove that there's an example of the subsums for $n=1392$ such that we can not recover the numbers uniquely. Note: If a subsum is sum of element of two different subsets, it appears twice. Time allowed for this question was 75 minutes.
Problem
Source: Iran 3rd round 2013 - final exam problem 5
Tags: combinatorics unsolved, combinatorics
ThE-dArK-lOrD
13.05.2018 18:36
I suppose the problem, by saying $2^n-1$ subsums, want to exclude the case when all $\epsilon_i$ are zeros from the subsum.
It's clear that there can't be any non-positive number in the set, i.e., all numbers are positive.
We'll inductively recover $i$ smallest numbers.
For base case, the smallest number is nothing but the smallest subsum too.
For inductive step, suppose we already recover $i$ smallest numbers, we consider the whole list again, and delete all the $2^i$ subsums of those $i$ numbers. The smallest subsum left must be the next smallest number, this complete the step.
So $0$ can't be a member of the set. Also, from the first part, we can consider only the case that there's at least one negative number in the list.
Also, if all numbers are negative (we can realise this happen when all the sums are negative), we can also use the first part but swapping all the signs to positive.
Say the actual list decomposed in two parts, the positive ones consist of $p_1,p_2,...,p_r$ and the negative ones consist of $m_1,m_2,...,m_t$.
Suppose the list of sum we've is $s_1< s_2\leq ...\leq s_k$. It's clear that $s_1=\sum_{i=1}^{t}{m_i}$.
Observe that there'll be at least one (multi)set that the list of subsums is $s_2-s_1\leq s_3-s_1\leq ...\leq s_k-s_1$ because that (multi)set is $p_1,p_2,...,p_r$ together with $-m_1,-m_2,...,-m_t$.
(Since for every $A\subseteq \{ 1,2,...,r\} ,B\subseteq \{ 1,2,...,t\}$, except when both $A=\emptyset$ and $B=\{ 1,2,...,t\}$, that $s_i=\sum_{a\in A}{p_a} +\sum_{b\in B}{p_b}$ for some $i\geq 2$, we've $s_i-s_1=\sum_{a\in A}{p_a} +\sum_{b\in B'}{(-p_b)}$ where $B'=\{ 1,2,...,t\} -B$.)
Moreover, all of $s_2-s_1,s_3-s_1,...,s_k-s_1$ are positive.
Hence, the first part make us recover the list consist of $p_1,p_2,...,p_r$ together with $-m_1,-m_2,...,-m_t$.
Now, we try to compute all subsums of those $r+t$ numbers to see which subset gives subsum that equal to $-s_1$.
Note that there'll be only one possible such subset (else there'll be some subset that give zero subsum, contradiction.)
Then we swap the sign of all numbers in that subset to get the actual correct set, done.