Maths Olympiad Prep

Library / /21 of 37

Algebra Difficulty 5.5 AIME, harder Find the answer Italy

Problem:

Let NN be the maximum number obtainable as a product of positive integers, all distinct, whose sum is 20242024. With how many digits "0" does the decimal representation of NN end?

Pick one

Solution

Solution:

The answer is (D). I call AA the set of numbers that sum to 20242024 and whose product is given by the maximum possible value, that is NN. I call "hole" a number nn that is not in AA, but such that AA contains both a number greater than nn and a number smaller than nn.

I prove that AA does not contain 11: let MM be the maximum integer contained in AA; if AA contained 11, then the set BB obtained from AA by removing 11 and adding M+1M+1 would still respect all the conditions imposed by the problem, but the product of the numbers contained in it would be N(M+1)>NN \cdot (M+1) > N, contradicting the fact that NN was the maximum possible.

I prove by contradiction that AA has at most one hole: suppose that a<ba < b, with a,bAa, b \in A and such that a+1a+1 and b1b-1 are two distinct holes; since (a+1)(b1)>ab(a+1)(b-1) > a b, the set CC obtained from AA by removing a,ba, b and adding a+1a+1 and b1b-1 still respects all the hypotheses of the problem. Moreover, the product of the numbers contained in CC would be given by N(a+1)(b1)ab>NN \frac{(a+1)(b-1)}{a b} > N, contradicting the maximality of NN.

Furthermore, AA cannot fail to contain 22 while at the same time having a hole nn such that n+2An+2 \in A. Indeed, if this were the case, the set DD, obtained from AA by adding 22 and nn and removing n+2n+2, still respects the hypotheses of the problem. Once again, the product of the numbers contained in DD is given by N2nn+2>NN \frac{2 n}{n+2} > N, which implies that NN was not the maximum possible.

The only way to write 20242024 as a sum of distinct numbers respecting the previous conditions is by using the numbers from 22 to 6464, skipping 5555. It follows that N=64!55N = \frac{64!}{55}, which ends with 1313 digits '0'. To count the number of trailing zero digits it is enough to count the number of factors 22 and the number of factors 55 that appear in the factorization of NN, and then take the minimum of these two quantities. It is easy to verify that there are fewer factors 55 than factors 22; finally, to compute the number of factors 55, one can observe that these are the same as those of the product 5101550605 \cdot 10 \cdot 15 \cdots 50 \cdot 60: this product has 1+1+1+1+2+1+1+1+1+2+1=131+1+1+1+2+1+1+1+1+2+1=13 factors 55 (indeed every multiple of 55 between 55 and 6060 contains only one factor 55, except for 2525 and 5050 which contain 22 each).

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 translated into English from it; metadata (topic, difficulty) added by this project.