Maths Olympiad Prep

Library / /713 of 740

, 2024

Number theory Difficulty 5.8 AIME, harder Prove it United States

Problem:
Paul is in the desert and has a pile of gypsum crystals. No matter how he divides the pile into two nonempty piles, at least one of the resulting piles has a number of crystals that, when written in base 10, has a sum of digits at least 7. Given that Paul's initial pile has at least two crystals, compute the smallest possible number of crystals in the initial pile.

Solution

Solution:
Denote the digit sum of a positive integer mm as s(m)s(m).
Let the pile have nn gypsum crystals, so that nn can be written as 10i1+10i2++10is(n)10^{i_{1}} + 10^{i_{2}} + \cdots + 10^{i_{s(n)}}.

First, s(n)s(n) cannot be 11 (i.e. nn cannot be a power of 1010), since otherwise we could split the gypsum pile into two equal parts each with digit sum 55. We also can't have 1<s(n)121 < s(n) \leq 12, as otherwise n=10i1+10i2++10is(n)n = 10^{i_{1}} + 10^{i_{2}} + \cdots + 10^{i_{s(n)}} can be split into two groups of at most six terms each (which have digit sum at most 66). Hence s(n)s(n) is at least 1313, forcing nn to be at least 4949.

Now we show that n=49n = 49 indeed works. Note that for any splitting into two piles of size a,ba, b with a+b=49a + b = 49, we do not carry any digits when adding aa and bb. Hence we must have s(a)+s(b)=s(n)=13s(a) + s(b) = s(n) = 13. This forces at least one of s(a),s(b)s(a), s(b) to be at least 77, so n=49n = 49 indeed works.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.