Maths Olympiad Prep

Library / /242 of 377

Number theory Difficulty 5.2 AIME, harder Prove it United States

Problem:
A positive integer nn is picante if n!n! ends in the same number of zeroes whether written in base 77 or in base 88. How many of the numbers 1,2,,20041, 2, \ldots, 2004 are picante?

Solution

Solution:
The number of zeroes in base 77 is the total number of factors of 77 in 12n1 \cdot 2 \cdots n, which is
n7+n72+n73+. \left\lfloor \frac{n}{7} \right\rfloor + \left\lfloor \frac{n}{7^2} \right\rfloor + \left\lfloor \frac{n}{7^3} \right\rfloor + \cdots.
The number of zeroes in base 88 is a\lfloor a \rfloor, where
a=(n2+n22+n23+)/3 a = \left( \left\lfloor \frac{n}{2} \right\rfloor + \left\lfloor \frac{n}{2^2} \right\rfloor + \left\lfloor \frac{n}{2^3} \right\rfloor + \cdots \right) / 3
is one-third the number of factors of 22 in the product n!n!. Now n2k/3n7k\left\lfloor \frac{n}{2^k} \right\rfloor / 3 \geq \left\lfloor \frac{n}{7^k} \right\rfloor for all kk, since (n/2k)/3n/7k\left( n / 2^k \right) / 3 \geq n / 7^k. But nn can only be picante if the two sums differ by at most 2/32/3, so in particular this requires (n/22)/3n/72+2/3n/43n/49+2\left( \left\lfloor n / 2^2 \right\rfloor \right) / 3 \leq \left\lfloor n / 7^2 \right\rfloor + 2/3 \Leftrightarrow \left\lfloor n / 4 \right\rfloor \leq 3 \left\lfloor n / 49 \right\rfloor + 2. This cannot happen for n12n \geq 12; checking the remaining few cases by hand, we find n=1,2,3,7n = 1, 2, 3, 7 are picante, for a total of 44 values.

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.