Maths Olympiad Prep

Library / /13 of 30

Number theory Difficulty 5.5 AIME, harder Find the answer Italy

Problem:

Let xx be the number of zeros with which 2000!2000! ends when written in base 55, and yy the number of zeros with which 2013!2013! ends when written in base 1010. Compute xyx-y. (Recall that the number n!n!, for nn a positive integer, is the product of all positive integers less than or equal to nn.)

Pick one

Solution

Solution:

The answer is (A). We know that yy is the largest exponent such that 10y10^{y} divides 2013!2013!. Thus yy is the minimum between the number of factors 22 and factors 55 that occur in the factorization of 2013!2013!. Since the number of factors two is clearly greater than the number of factors 55, yy is also the number of factors 55 in the factorization of 2013!2013!.

Similarly, the number of zeros with which 2000!2000! written in base 55 ends is simply the number of factors 55 that appear in the factorization of 2000!2000!.

Let us then write 2000!=5xa2000! = 5^{x} \cdot a, 2013!=5yb2013! = 5^{y} \cdot b for two integers a,ba, b in whose factorization no factors 55 appear.

Let us now observe that 2013!2000!=5yxab\frac{2013!}{2000!} = 5^{y-x} \cdot \frac{a}{b} is an integer, because it coincides with 2001200220132001 \cdot 2002 \cdots 2013.

It follows that ab\frac{a}{b} is an integer with no factors five, and that yxy-x is the number of factors 55 in the factorization of 2001200220132001 \cdot 2002 \cdots 2013. This latter quantity is easy to compute: the only multiples of 55 in this product are 20052005, 20102010, and both contribute exactly one factor five (not being divisible by 2525), so yx=2y-x=2.

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.