Q3 Matemática  (International Olympiad of Metropolises 2020)

Seja $n>1$ um dado inteiro. A Casa da Moeda emite moedas de $n$ valores diferentes $a_1,a_2,...,a_n$, onde cada $a_i$ é um inteiro positivo (o número de moedas de cada valor é ilimitado). Um conjunto de valores $\{a_1,a_2,...,a_n\}$ é chamado de sorte, se a soma $a_1+a_2+...+a_n$ puder ser coletada de uma maneira única (ou seja, pegando uma moeda de cada valor). (a) Prove que existe um conjunto sortudo de valores $\{a_1,a_2,...,a_n\}$ com $$a_1+a_2+...+a_n<n\cdot 2^n.$$(b) Prove que todo conjunto sortudo de valores $\{a_1,a_2,...,a_n\}$ satisfaz $$a_1+a_2+...+a_n>n\cdot 2^{n-1}.$$ Proposto por Ilya Bogdanov