Baron Munchhausen has a collection of stones, such that they are of $1000$ distinct whole weights, $2^{1000}$ stones of every weight. Baron states that if one takes exactly one stone of every weight, then the weight of all these $1000$ stones chosen will be less than $2^{1010}$, and there is no other way to obtain this weight by picking another set of stones of the collection. Can this statement happen to be true? (М. Антипов)
HIDE: Thanks Thanks to the user Vlados021 for translating the problem.Problem
Source: Saint Petersburg 2019
Tags: combinatorics, number theory
14.04.2019 23:40
Surprisingly (at least for me), the answer is yes! Baron Munchhausen's $1000$ distinct weights could be $2^{1000} + 1, 2^{1000}+2, 2^{1000} + 4, \cdots, 2^{1000} + 2^{999}.$ The sum of these weights is $1001 \cdot 2^{1000} - 1.$ We claim that there is no other way to attain this sum other than simply taking one of each distinct weight. We'll prove this by contradiction, supposing that there was some way other than one of each weight which achieved a total weight of $1001 \cdot 2^{1000} -1.$ Clearly, since every weight is $>2^{1000}$, there can be at most $1000$ weights in any such representation. Hence, we can suppose that there are $1000-c$ weights, for some nonnegative integer $c$. Let these weights be $2^{1000} + 2^{b_1}, 2^{1000} + 2^{b_2}, \cdots, 2^{1000} + 2^{b_{1000-c}}$. We then know that: $$2^{1000} \cdot c + 2^0 + 2^1 + \cdots + 2^{999} = 2^{b_1} + 2^{b_2} + \cdots + 2^{b_{1000-c}},$$ where the $b_i$'s are all nonnegative integers in $[0, 999].$ If the $b_i$'s are all distinct, then clearly $2^{b_1} + 2^{b_2} + \cdots + 2^{b_{1000-c}} \le 2^0 + 2^1 + \cdots + 2^{999},$ and so the only case where equality is possible is in the case where $c = 0$ and we pick one of each weight. However, we assumed that there was some other way, so suppose that the $b_i$'s are not pairwise distinct. Hence, we may suppose that some two $b_i$'s are initially equal. We will consider the following process: Look at all the $0$'s among the $b_i$'s. As long as there are at least $2$ zeroes, remove $2$ $0$'s and turn them into a single $1.$ After we can no longer do the above, repeat with the $1$'s, turning them into $2$'s one pair at a time. $\cdots$ Finally, look at the $999$'s and "merge" them in pairs into $1000$'s. Observe that the "sum base $2$" of the integers is always invariant, for the simple reason that $2^k + 2^k = 2^{k+1}.$ At the end of this, we have some number of $1000$'s and the rest are distinct nonnegative integers in $[0, 999].$ By modulo $2^{1000}$ and the invariance of the sum, it's clear that at the end, there must be exactly one of $2^0, 2^1, 2^2, \cdots, 2^{999}.$ Hence, there are at least $1000$ things in the end. However, since we did at least one "merging" (due to the $b_i$'s not being pairwise distinct), there were at least $1001$ things initially (since each "merging" decreases the number of terms by one). However, $b_1, b_2, \cdots, b_{1000-c}$ is clearly $<1001$ total integers, contradiction. $\square$