# Task No. 7.1

## Condition:

Artist Ivan Konstantinovich decided to sell several of his paintings at the Broken Auction. The rules of the Broken Auction are as follows: first, Ivan Konstantinovich names a certain starting price for his painting, after which the participants who want to buy this painting begin to bid on it - increasing the price, but only by a factor of two, - that is, the new price can only be twice the last one offered; the participant after whom no one dares to raise the price by another factor of two gets the painting; if no one bids on the painting, that is, no one offers a price higher than the initial one, the painting remains unsold. For each of his paintings, Ivan Konstantinovich decided to set the starting price at 1000 rubles. How many paintings did he sell at the Broken Auction if all his paintings were bought for different prices, and his total revenue from all the sold paintings amounted to 250000 rubles?
Answer: 6

Exact match of the answer -1 point

## Solution.

It is claimed that each painting by Ivan Konstantinovich was sold for $1000 \times 2^{\text {x }}$ rubles, where $\mathrm{x}$ is some natural number. Indeed, initially, the painting's price is 1000 rubles, and each participant doubles its price, meaning the price is multiplied by 2. Therefore, when the painting reaches the last participant and is sold, its price is multiplied by 2 several times (possibly once) and becomes $1000 \times 2 \times \ldots \times 2$, or $1000 \times 2^{x}$ rubles. Here, $\mathrm{x}$ cannot be 0 because the painting cannot be sold for 1000 rubles if no one doubles the price; the painting would remain unsold, and the problem only concerns sold paintings.

Thus, Ivan Konstantinovich's total revenue is the sum of several such numbers of the form $1000 \times 2^{\mathrm{a}}$, where the exponent of 2 is some natural number. This means it is 1000 multiplied by some sum of powers of 2. Since all prices, according to the problem, were different, no power of 2 in this sum is repeated. We need to represent the number $250000 / 1000=250$ as a sum of different powers of 2, and the number of terms in such a decomposition will show us the number of paintings sold. Let's do this: $250=128+64+32+16+8+2 \Rightarrow 6$ terms $\Rightarrow$ 6 paintings were sold.

The uniqueness of such a decomposition can be explained using simple reasoning about what can and cannot be in the decomposition: there are no powers of 2 greater than 128 in the sum, as otherwise the sum would be at least 256, but it should be 250. Moreover, 128 must be included, otherwise the maximum sum would be $64+32+16+8+4+2=126$, since all numbers in the sum are different (as the prices are different by condition). It remains to make up the difference of 250$128=122$. Similarly, it can be shown that 64, 32, 16, and 8 must be included in the sum. After that, only 2 remains to be added, which is exactly the number 2.

#