Nice problem! (a) Consider $a_i=2^n-2^{i-1},i=1,2,\cdots,n$. Their sum is $S=\sum_{i=1}^n (2^n-2^{i-1})=(n-1)\cdot 2^n+1<n \cdot 2^n$ Assume that there is a collection of coins with total value $S$, write $$ S=\sum_{j=1}^m a_{i_j}=\sum_{j=1}^m (2^n-2^{i_j-1})$$where $i_1 \le i_2 \le \cdots \le i_m$. Since each $a_i$ is no more than $2^n-1$, we must have $m \ge \lceil \tfrac{S}{2^n-1} \rceil =n$. On the other hand, modulo $2^n$ gives $$ \sum_{j=1}^m 2^{i_j-1} \equiv 2^n-1 \pmod{2^n}$$Modulo $2^k$ ($ 1 \le k \le n$) shows that at least $k$ of $i_j$ s are $\le k$. Iin other word, $i_k \le k$ for all $1 \le k \le n$. But then \begin{align*} (n-1)\cdot 2^n+1 &= S = \sum_{j=1}^m (2^n-2^{i_j-1}) \\ & \ge \sum_{i=1}^n (2^n-2^{i-1})+(m-n) \cdot (2^n-2^{n-1}) \\ &= (n-1)\cdot 2^n+1+(m-n) \cdot (2^n-2^{n-1}) \\ &= S+(m-n) \cdot (2^n-2^{n-1}) \end{align*}So we must have $m=n$ and equality holds everywhere, i.e. the representation is unique. (b) We prove that $a_i \ge 2^{n-1}$ for all $1 \le i \le n$. Take $i=n$ as an example, lets consider $$\sum_{i \in B} a_i, \quad \text{where} \quad B \subset \{1,2,\cdots,n-1\}.$$If there are two sums, say $\sum_{i \in B_1} a_i$ and $\sum_{i \in B_2} a_i$, are congruence modulo $a_n$, let $\sum_{i \in B_1} a_i-\sum_{i \in B_2}a_i =k \cdot a_n$, then $$\sum_{i \notin B_1} a_i +\sum_{i \in B_2} a_i +k \cdot a_n=S$$is another representation of $S$, which is absurd. So all $2^{n-1}$ sums are pairwise not congruent modulo $a_n$, thus $a_n \ge 2^{n-1}$. Add all gives $a_1+a_2+\cdots+a_n \ge n \cdot 2^{n-1}$. It's clear that the equality cannot hold.

a. For every integer $n$ larger than 1, define $S_{n}$ as the set $\{2^{n}-1,2^{n}-2,2^{n}-4,\dots, 2^{n}-2^{n-1}\}$. We want to prove that $S_{n}$ is a lucky set which will prove the problem. To do this, we will proceed by induction. The base case $n=2$ is easy. Assume it is true that $S_{k}$ is beautiful. We will prove that $S_{k+1}$ is also beautiful. Suppose the contrary, there exists a tuple of nonnegative integer $(x_1,x_2,\dots ,x_{k+1})\neq (1,1,\dots, 1)$ such that \[\sum_{i=1}^{k+1} x_{i}(2^{k+1}-2^{i-1})=\sum_{i=1}^{k+1} (2^{k+1}-2^{i-1})\]The above equation is equivalent to \[\sum_{i=1}^{k+1} x_{i}2^{k} + \sum_{i=1}^{k} x_i(2^{k}-2^{i-1}) = \sum_{i=1}^{k+1} 2^k + \sum_{i=1}^{k} (2^{k}-2^{i-1})\]Define $Y=x_{1}+x_{2}+\dots +x_{k+1}-(k+1)$. It's easy to check that $Y\ge 0$ because $x_{1}+x_{2}+\dots +x_{k+1}\ge \frac{\sum_{i=1}^{k+1} 2^{k+1}-2^{i-1}}{2^{k+1}-1}>k$. Then, we have \[\sum_{i=1}^{k-1} x_{i}(2^{k}-2^{i-1})+(2^{k}-2^{k-1})(2Y+x_{k})=\sum_{i=1}^{k} (2^{k}-2^{i-1})\]By the assumption of induction, we must have $x_1=x_2=\dots = x_{k-1}=2Y+x_{k}=1$. This implies $(x_1,x_2,\dots , x_{k+1})=(1,1,\dots , 1)$. So, by induction, part (a) is proven. b. WLOG $a_1 < a_2 < \dots < a_n$. We want to prove that $a_1\ge 2^{n-1}$ which will prove the problem. Suppose the contrary, $a_1\le 2^{n-1}-1$. Define $X=\sum_{i=1}^{n} a_i$ and $U=\{2,3,\dots , n\}$. If there exists a non empty set $S\subseteq U$ such that $\sum_{i\in S} a_i \equiv 0\pmod {a_1}$, then we have \[X=a_1\cdot j +\sum_{i\in U-S} a_i\]for some $j\in \mathbb N$. A contradiction. If there doesn't exist a non empty set $S\subseteq U$ such that $\sum_{i\in S} a_i\equiv 0\pmod {a_1}$, by PHP and the fact that $a_1\le 2^{n-1}-1$, there must exists two different non empty sets $A,B\subseteq U$ such that \[\sum_{i\in A} a_i\equiv \sum_{i\in B} a_i \pmod {a_1}\]WLOG $\sum_{i\in A} a_i\le \sum_{i\in B} a_i$. We have, \[X=\sum_{i\in U-(A\cup B)} a_i + \sum_{i\in A} a_i + \sum_{i\in A-B} a_i +a_1\cdot j\]for some $j\in \mathbb N$. Another contradiction Therefore, we must have $a_1\ge 2^{n-1}$. So, part (b) is also proven.

Metropolises 2020 P3 wrote: Let $n>1$ be a given integer. The Mint issues coins of $n$ different values $a_1, a_2, ..., a_n$, where each $a_i$ is a positive integer (the number of coins of each value is unlimited). A set of values $\{a_1, a_2,..., a_n\}$ is called lucky, if the sum $a_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 $\{a_1, a_2, ..., a_n\}$ with $$a_1+ a_2+...+ a_n < n \cdot 2^n.$$(b) Prove that every lucky set of values $\{a_1, a_2,..., a_n\}$ satisfies $$a_1+ a_2+...+ a_n >n \cdot 2^{n-1}.$$ Proposed by Ilya Bogdanov Another idea for (a). For (b) my solution coincides with the ones above, so I won't bother writing it up. We prove that the set $(2^n-1,2^n-2,\ldots, 2^n-2^{n-1})$ is lucky. It is easy to verify that $(2^n-2^0)+\ldots+(2^n-2^{n-1})=2^n(n-1)+1<n \cdot 2^n$. Suppose now that we collect the sum $2^n(n-1)+1$, taking $b_i$ coins from each value, that is $$(2^n-1)b_1+\ldots+(2^n-2^{n-1})b_n=2^n(n-1)+1$$For each $1 \leq i\leq n$ we consider the previous one $\pmod {2^i}$. We obtain that $b_1+2b_2+\ldots+2^{i-1}b_i \equiv -1 \pmod {2^i}$, hence $b_1+\ldots+2^{i-1}b_i \geq 2^i-1$ for all $i \leq n$. Now, note that $$\sum_{i=1}^{n} 2^{n-i}(a_1+\ldots+2^{i-1}a_i)=(2^n-1)a_1+(2^n-2^1)a_2+\ldots+(2^n-2^{n-1})a_n$$since $2^{n-1}+\ldots+2^0=2^n-1$. Hence we have $$ (n-1)2^n+1=(2^n-1)a_1+(2^n-2^1)a_2+\ldots+(2^n-2^{n-1})a_n)=\sum_{i=1}^{n} 2^{n-i}(a_1+\ldots+2^{n-i}a_i) \geq \sum_{i=1}^{n} 2^{n-i}(2^i-1)=(n-1) 2^n+1$$therefore equality must hold, implying $a_1=1, a_1+2a_2=3, \ldots, a_1+\ldots+2^{n-1}a_n=2^n-1$ hence we easily conclude that all $a_i$ are $1$, as desired.

An extremal principle in a summation problem. How unique! Without Loss of Generality always assume that $a_1 < a_2 <\ldots < a_n$. $\color{green} \rule{25cm}{2pt}$ $\color{green} \textbf{\text{Part a.}}$ We claim that the configuration $\{a_i\} = \{ 2^{n-1}, 2^n+1, 2^n+2,\ldots,2^n+2^{n-2} \}$, which has sum exactly $n \cdot 2^n - 1$ is a lucky set. To prove this, let there exists $e_1,e_2,\ldots,e_n$ so that \[ e_1a_1+e_2a_2+\ldots+e_na_n = n \cdot 2^n - 1 \]for some $(e_1,e_2,\ldots,e_n) \in \mathbb{N}^n$ not all $1$. Take the equation mod $2^{n-1}$ . The equation becomes \[ e_2+2e_3+\ldots+2^{n-2}e_n \equiv 2^{n-1}-1 \pmod{2^{n-1}}\]By standard binary representation, as the number $11\ldots1_2$ (with $n-1$ digits) must require at least $n-1$ $``\text{nodes}"$ to form, then \[e_2+\ldots+e_n \geq n-1 \]Since it is impossible for $e_2+e_3+\ldots+e_n$ to be $n$ or more, then its quantity is exactly $n-1$. Then, \[e_1a_1 \leq n \cdot 2^n-1 - ((n-1) \cdot 2^n) < 2^n \]and we get $e_1 \leq 1$. If $e_1 = 1$, we immediately get all $e_i$ to be $1$. Otherwise, if $e_1 = 0$, taking mod $2^n$ (or just forming $b_i = a_i - 2^n$ for $2 \leq i \leq n$), we get that $111\ldots1_2$ (with $n$ digits) will require at least $n$ nodes. Contradiction. $\color{red} \rule{25cm}{2pt}$ $\color{red} \textbf{\text{Part b.}}$ Almost the same as the above solutions, but posting anyways because this problem has an unexpected Solution. Since the above approach(es) hints the significance of $a_i$'s bound, we try to copy that way of thinking to $\color{red} \textbf{\text{Part b}}$ as well. We prove that $a_1 \geq 2^{n-1}$, implying that $a_2,a_3,\ldots,a_n > 2^{n-1}$, hence the conclusion. If $a_1 \leq 2^{n-1}$, consider the subsets of the set $\{a_2,\ldots,a_n\}$ mod $a_1$. Since there are $2^{n-1}$ subsets, at least two must have equal residue. Call them $X$ and $Y$, and let \[ \sum_{a_i \in X} a_i - \sum_{a_j \in Y} a_j = S_X-S_Y = c \cdot a_1 \]for some $c \in \mathbb{N}_0$ (assume $S_X \geq S_Y$ here.) Then, we can pick $c+1$ $a_1$s, throw out all numbers $a_i$ which belongs to the bigger-summed set $X$ and add in extra $a_j$ which belongs to the smaller-summed set $Y$. We are done, since the total sum is exactly equal to the initial sum (after we compensate the loss by adding $a_1$s to our possession.)

(a) Consider the set $A=\{a_1,a_2,...,a_n\}=\{2^{n-1}(2-1),2^{n-2}(2^2-1),2^{n-3}(2^3-1),...,2(2^{n-1}-1),2^n-1\}$. Then $$a_1+a_2+...+a_n=(n-1)2^n+1<n\cdot2^n$$We now claim that $A$ is lucky. Suppose $e_1,e_2,...,e_n\geq 0$ and $$e_1a_1+e_2a_2+...+e_na_n=(n-1)2^n+1$$then we have $$\sum_{i=0}^{n-1}e_{n-i}2^{i}=(e_1+e_2+...+e_n-n)2^{n}+2^{n}-1\hspace{20pt}(1)$$Claim. Given $k$, then if $f_1,f_2,...,f_n\geq 0$ and satisfies $$\sum_{i=0}^{n-1} f_{n-i}2^i=k2^n+2^n-1\hspace{20pt}(2)$$then $\displaystyle\sum_{i=1}^{n-1}f_{n-i}\geq2k+n$ Proof. Indeed, suppose $(f_1,f_2,...,f_n)$ is the $n$-tuple which satisfies $(1)$ with $f_1+...+f_n$ minimized. Then we must have $f_2=...=f_n\leq 1$, otherwise if $f_i\geq 2$ replace $(f_{i-1},f_i)$ by $(f_{i-1}+1,f_i-2)$, it still satisfies $(2)$ but $f_1+f_2+...+f_n$ is decreased. Moreover since the right hand side of $(2)$ congruent $-1$ mod $2^n$ we must have $f_2=...=f_n=1$. Hence $f_1=1+2k$ and so $f_1+f_2+...+f_n=2k+n$. $\blacksquare$ Now applying the Claim to $(1)$ we have $$e_1+...+e_n\geq 2(e_1+...+e_n-n)+n$$and so $e_1+...+e_n\leq n$. Notice that $(n-1)2^n+1>(n-1)(2^n-1)$ so $e_1+...+e_n>n-1$. As a result we must have $e_1a_1+...+e_na_n=n$, so using the same reasoning in the claim we conclude that we must have $e_1=...=e_n=1$ and we are done. (b) Suppose $a_1<a_2<...<a_n$. Now we claim that $a_1>2^{n-1}$ which obviously solves the problem. Indeed, obviously the set $S=\{a_2,...,a_n\}$ is lucky. If $a_1<2^{n-1}$, by pigeonhole principle there exists $S_1,S_2$ such that $$\sum_{x\in S_1}x-\sum_{x\in S_2}x\equiv 0\pmod a_1$$WLOG assume sum of elements of $S_1$ is greater than the sum of elements of $S_2$, we can pick $c$ such that $$\sum_{x\in S_1}x=ca_1+\sum_{x\in S_2}$$WLOG assume $S_1,S_2$ are disjoint or otherwise just delete some of their common elements. As a result, $$a_1+...+a_n=2\sum_{x\in S_2}x+\sum_{x\in S\setminus S_2}x+(c+1)a_1$$and so the set $\{a_1,...,a_n\}$ is unlucky as desired.