MathDB
Recovering Lost Numbers

Source: Iran 3rd round 2013 - final exam problem 5

September 25, 2014
combinatorics unsolvedcombinatorics

Problem Statement

A subsum of nn real numbers a1,…,ana_1,\dots,a_n is a sum of elements of a subset of the set {a1,…,an}\{a_1,\dots,a_n\}. In other words a subsum is ϵ1a1+⋯+ϵnan\epsilon_1a_1+\dots+\epsilon_na_n in which for each 1≤i≤n1\leq i \leq n ,ϵi\epsilon_i is either 00 or 11. Years ago, there was a valuable list containing nn real not necessarily distinct numbers and their 2n−12^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=1392n=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.
Back to ProblemsView on AoPS