There are finite many coins in David’s purse. The values of these coins are pair wisely distinct positive integers. Is that possible to make such a purse, such that David has exactly $2020$ different ways to select the coins in his purse and the sum of these selected coins is $2020$?
Problem
Source:
Tags: combinatorics, Canada
15.03.2020 02:19
15.03.2020 05:13
18.03.2020 05:19
19.03.2020 18:15
My construction is $S_1\cup S_2,$ where$\cdots$
09.09.2020 20:45
very simple construction
I have no idea why the official solution was so complicated.
29.12.2021 19:59
29.08.2022 05:32
$\{50,100,116,117,\ldots,123,126\}\cup [1010,2020]$ Denote $S=\{50,100,116,117,\ldots,123,126\}$. Any $10$ or $11$ subset of $S$ sum to greater than $1010$, and out of the $9$ element subsets, anything that discards $50$ or discards $100$ and an element less than $122$ have a sum greater than $1010$. Any $8$ element subset has sum less than $1010$, hence there are $2048-(11+1+10+6)=2020$ subsets of $S$ that can't be complemented uniquely by a number in $[1010,2020]$ to sum to $2020$, and obviously no two distinct numbers in $[1010,2020]$ can sum to $2020$.
06.10.2022 18:36
The answer is yes. We employ the following set of coin values: $$\{1, 2, 4, \ldots, 64\} \cup \{947,\ldots,1010\} \cup \{2017, 2018, 2019, 2020\}.$$Note that $947=1010-63$. We now show that this works. Call the three sets described $A,B,C$ respectively. Consider the following cases on the ways we can form a combined value of $2020$. Case 1: We use some element of $C$. Clearly we can use at most one, then, and then obviously we can't use anything in $B$. If we use $k \in C$, then there is exactly one way to form a value of $2020-k$ from some elements (possibly none) of $A$. Thus there are simply $|C|=4$ possibilities in this case. Case 2: We use no elements of $C$. Then since $1+2+4+\cdots+64=127<2020-1010$, we have to use at least two elements of $B$. On the other hand, since $947+948+949>2020$, we use at most elements of $B$, so we use exactly $2$ elements, say $x,y$. Then since $0 \leq 2020-x-y \leq 125$, there is exactly one way to form $2020-x-y$ from some elements of $A$, so there are $\binom{|B|}{2}=2016$ elements in this case. Combining these two cases, it follows that there are $2020$ possible ways to form a combined value of $2020$, as desired. $\blacksquare$ Remark: Fairly similar to #2 but much cleaner in my opinion. Binary seems somewhat natural because it's an easy way to get a fairly large range $[0,?]$ that we can form in exactly one way. From there we can also get $\binom{n}{2}$ values by taking some size $n$ set starting with $1010$ (here $n=64$), but it's a bit off since $2020$ can't exactly be expressed in that form. So we make a small adjustment and throw in $C$, which doesn't "interact" with $B$, and is easily controllable but somewhat limited by size (for example extending $|C|$ to large sizes like, say, $1500$, would obviously fail). This is fine though because we can still get $\binom{n}{2}$ close to $2020$.
02.11.2022 18:58
$\{1, 2, 3 \} \cup \{757 , 758, \dots, 1263 \} \cup \{2016, 2017 \dots 2020 \}$.
09.01.2023 21:16
Yes! We use the coins with values from the following set: $$P=\{i\; :\; 1\le i\le 3\}\cup \{i\; :\; 757\le i\le 2018\}.$$ We case our counting by the number of coins in the sums. Note we need at least two coins to make $2020$. Moreover, we can not have more than $5$ coins in the sum. Suppose we did, then we have $$2020>1+2+3+757+758+759$$which is clearly absurd. For $2$ coin sums, we have $$2+2018, 3+2017$$and $$757+1263, \dots, 1009+1011$$which total to $2+(1009-757+1)=255$ distinct sums. For $3$ coin sums, note we must choose at least one coin from $\{1 ,2, 3\}$ as otherwise, the sum would be more than $2020$. Thus, we have $$1+2+2017, 1+3+2016, 2+3+2015,$$$$1+757+1262, \dots, 1+1009+1010,$$$$2+757+1261, \dots, 2+1008+1010,$$and $$3+757+1260, \dots, 3+1008+1009$$which totals to $3+253+252+252=760.$ For $4$ coin sums, again note we must choose at least two coins from $\{1, 2, 3\}$ as otherwise, the sum would include at least three coins which sum to more than $2020$. Hence, we have $$1+2+3+2014,$$$$1+2+757+1260, \dots, 1+2+1008+1009,$$$$1+3+757+1259, \dots, 1+3+1007+1009,$$and $$2+3+757+1258, \dots, 2+3+1007+1008$$which totals to $1+252+251+251=755.$ Finally, for $5$ coin sums, we must include $1, 2,$ and $3$ again for size reasons. Hence, we have $$1+2+3+757+1257, \dots, 1+2+3+1006+1008$$which totals to $250$. Together, this gives $$255+760+755+250=2020$$as desired. Some motivation: If we only use small coins, it would be pretty hard to count to total ways to sum them. If we only use big coins, we don't have enough ways. Also, we really dont want to deal with $3$-sums of big coins, so we only want to use coins bigger than $673$. Some trial and error gives the construction.
07.02.2023 19:31
Another construction: $\{1,2,4,\ldots,64,700,701,\ldots,800,1201,1202,\ldots,1220\}$.
12.02.2023 10:45
I have a different enough solution that it's worth posting :O
06.11.2023 06:26
Yes it is. For positive integers $n < 66$, let $f(n)$ denote the number of ways to pick a nonempty subset of $\{1,2,\ldots, 11\}$ with elements summing up to $n$. Claim: If there exists a strictly increasing sequence of positive integers $x_1<x_2<\cdots < x_k$ for some positive integer $k$ and $f(x_1) + f(x_2) + \cdots + f(x_k) = 27$, then there exists a valid coin choice in David's purse. Proof: Consider \[\{1,2,\ldots, 11\} \cup \{2019 - 66, 2019 - 65, \ldots, 2019\} - \{2019 - x_k, 2019 - x_{k-1} , \ldots, 2019 - x_1\}\]Any subset of this with elements adding to $2020$ must include exactly one element at least $2019 - 66$ and is equal to $2019$ minus the sum of the subset of $\{1,2, \ldots, 11\}$ that is chosen. Therefore the (nonempty) subset of $\{1,2,\ldots, 11\}$ that is chosen determines the coins that are chosen. This implies for any nonempty subset of $\{1,2,\ldots, 11\}$ without elements adding to $x_i$ for some $i$, we have one choice of the coins adding up to $2020$. Thus, there are in total $(2^{11} - 1) - f(x_1) - f(x_2) - \cdots - f(x_k) = 2020$ coin choices, as desired. $\square$ We may manually compute that $f(1) = 1, f(2) = 1, f(3) = 2, f(4) = 2, f(5) = 3, f(6) = 4, f(8) = 6, f(9) = 8$. If we choose our sequence to be $1,2,3,4,5,6,8,9$, we get \[ \sum_{1\le i\le 8} f(x_i) = 1 + 1 + 2 + 2 + 3 + 4 + 6 + 8 = 27\]
23.01.2024 02:23
Cute little gem. The answer is yes; construction is given by $$S=\{1, 2, 3, 4, \dots, 11, 1954, 1958, 1959, 1960, \dots, 2010, 2011, 2020\}.$$ In particular, for every (possibly zero) sum $S$ consisting of numbers in $\{1, 2, \dots, 11\}$ that is not equal to any $1 \leq i \leq 8$ or $63, 64, 65$, we will have a subset with sum $2020$ by picking the corresponding element $2020-S$. There are precisely $$2^{11} - (1+1+2+2+3+4+5+6+1+1+2) = 2020$$such sums $S$, as needed.
04.08.2024 15:51
Another construction: \[\{1,2,4,8,16,32,64,128,256,512,1024\}\cup\{6,9,25,27,34,143,239,384,385,412,434\}\]
05.12.2024 19:15
We claim the set of coins $A = \{1,2,3,4,5,6,7,8,9,10,11 \} \cup B = (\{1954 \cdots 2020 \} \setminus {2012,2010, 2009}) $is sufficient. Obviously, every way to select the coins involves choosing exactly one element of $B$ and some subset of $A$. Clearly, for each element $i$ of $B$ the number of ways to select a valid set of coins from $A$ is the number of subsets of $A$ summing to $2020 - i$. As we range $i$ from $1954$ to $2020$, every subset of $A$ is counted once, so this is $2048$ ways. We then observe there are $6$ ways to choose a subset of $A$ summing to $8 = 2020 - 2012$ ($8,7 + 1,6 + 2, 5 + 3, 5 + 2 + 1, 4 + 3 + 1$), $10$ ways to choose a subset of $A$ summing to $10 = 2020 - 2010$ ($10, 9 + 1, 8 + 2, 7 + 3, 7 + 2 + 1, 6 + 3 + 1, 6 + 4, 5 + 3 + 2, 5 + 4 + 1, 4 + 3 + 2 + 1$), and $12$ ways to choose a subset of $A$ summing to $11 = 2020 - 2009$ ($11, 10 +1, 9 + 2, 8 +3, 8 + 2 + 1, 7 + 3 + 1, 7 + 4, 6 + 5, 6 + 4 + 1, 6 + 3 + 2, 5 + 4 + 2, 5 + 3 + 2 + 1$), so eliminating $2012, 2010, 2009$ removes $28$ sums, giving the desired $2048 - 28 = 2020$ ways.