Olympiad Maths Prep

Track / Stage 5 / 242 of 400 #842 of 2000

Problem 842

AIME late
Combinatorics Difficulty 5.6 Find the answer

9. (24th American Mathematics Competition) There are 1990 piles of stones, with the number of stones in each pile being 1,2,,19901, 2, \cdots, 1990. Perform the following operation: each time, you can choose any number of piles and remove the same number of stones from each chosen pile. How many operations are required at minimum to remove all the stones?

Official solution

9. Since 1990=210+29+28+27+26+025+024+023+22+21+0201990=2^{10}+2^{9}+2^{8}+2^{7}+2^{6}+0 \cdot 2^{5}+0 \cdot 2^{4}+0 \cdot 2^{3}+2^{2}+2^{1}+0 \cdot 2^{0}, and writing 1,2,1,2, \cdots, 1989 in binary form, the operation is as follows:

The first time, take away 210=10242^{10}=1024 stones from each pile that has enough; the second time, take away 29=5122^{9}=512 stones from each pile that has enough, \cdots, finally, take away the stones from the piles that have only 20=12^{0}=1 stone left. In this way, a total of 11 times are used, because the pile with one stone must have an operation to take one stone. If the remaining operations take away more than 2 stones each time, then the pile with exactly two stones cannot be taken away. Therefore, 2 operations can take at most 1+2=31+2=3 stones, \cdots, 10 operations can take at most 1+2+22++29=10231+2+2^{2}+\cdots+2^{9}=1023 stones, so 1990 piles of stones must undergo at least 11 operations.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.