MathDB

3

Part of 2020 IOM

Problems(1)

every lucky set of values {a_1,a_2,..,a_n} satisfies a_1+a_2+...+a_n >n2^{n-1}

Source: 2020 International Olympiad of Metropolises P3

12/19/2020
Let n>1n>1 be a given integer. The Mint issues coins of nn different values a1,a2,...,ana_1, a_2, ..., a_n, where each aia_i is a positive integer (the number of coins of each value is unlimited). A set of values {a1,a2,...,an}\{a_1, a_2,..., a_n\} is called lucky, if the sum a1+a2+...+ana_1+ a_2+...+ a_n can be collected in a unique way (namely, by taking one coin of each value). (a) Prove that there exists a lucky set of values {a1,a2,...,an}\{a_1, a_2, ..., a_n\} with a1+a2+...+an<n⋅2n.a_1+ a_2+...+ a_n < n \cdot 2^n. (b) Prove that every lucky set of values {a1,a2,...,an}\{a_1, a_2,..., a_n\} satisfies a1+a2+...+an>n⋅2n−1.a_1+ a_2+...+ a_n >n \cdot 2^{n-1}.
Proposed by Ilya Bogdanov
algebra