Question 36
A **partial sum** of $n$ real numbers $a_1, a_2, ..., a_n$ is the sum of some of them; that is, $\epsilon_1 a_1 + \epsilon_2 a_2 + ... + \epsilon_n a_n$, where for each $1 \le i \le n$, $\epsilon_i$ is either 0 or 1 and at least one of them is nonzero. Now, having these partial sums, we want to find the numbers.
Years ago a valuable list containing $n$ real (not necessarily distinct) numbers and all their $2^n - 1$ partial sums was shown to the public in a museum. Some strange creatures from the planet Hot Dog (after being defeated in solving the Rotund Polygon problem!) have stolen our original $n$ numbers and the only thing that is left are those $2^n - 1$ partial sums.
a) Prove that if all the partial sums are positive, all the stolen numbers can be determined uniquely.
b) Suppose that some of the partial sums are positive and some of them negative, but none of them zero. Prove that still all the stolen numbers can be determined uniquely.
c) Prove that for $n = 1392$, an example can be constructed to show it's not possible to determine all of the stolen numbers uniquely, by only having their $2^n - 1$ partial sums.
Years ago a valuable list containing $n$ real (not necessarily distinct) numbers and all their $2^n - 1$ partial sums was shown to the public in a museum. Some strange creatures from the planet Hot Dog (after being defeated in solving the Rotund Polygon problem!) have stolen our original $n$ numbers and the only thing that is left are those $2^n - 1$ partial sums.
a) Prove that if all the partial sums are positive, all the stolen numbers can be determined uniquely.
b) Suppose that some of the partial sums are positive and some of them negative, but none of them zero. Prove that still all the stolen numbers can be determined uniquely.
c) Prove that for $n = 1392$, an example can be constructed to show it's not possible to determine all of the stolen numbers uniquely, by only having their $2^n - 1$ partial sums.