Maths Olympiad Prep

Library / Harvard-MIT Mathematics Tournament /223 of 352

Harvard-MIT Mathematics Tournament

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 1⋅2⋯n1 \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⌋/3≥⌊n7k⌋\left\lfloor \frac{n}{2^k} \right\rfloor / 3 \geq \left\lfloor \frac{n}{7^k} \right\rfloor for all kk, since (n/2k)/3≥n/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⌋)/3≤⌊n/72⌋+2/3⇔⌊n/4⌋≤3⌊n/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 n≥12n \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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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