HMMT 二月 2004 · 冲刺赛 · 第 9 题

英文解析

9. A positive integer n is picante if n ! ends in the same number of zeroes whether writtenin base 7 or in base 8. How many of the numbers 1 , 2 , . . . , 2004 are picante?
   Solution: 4
   The number of zeroes in base 7 is the total number of factors of 7 in 1 · 2 · · · n , which is 2
   ⌊ ⌋ ⌊ ⌋
   2 3
   b n/ 7 c + n/ 7 + n/ 7 + · · · .
   The number of zeroes in base 8 is b a c , where
   ⌊ ⌋ ⌊ ⌋
   2 3
   a = ( b n/ 2 c + n/ 2 + n/ 2 + · · · ) / 3
   ⌊ ⌋ ⌊ ⌋
   k kis one-third the number of factors of 2 in the product n !. Now n/ 2 / 3 ≥ n/ 7 for allk kk , since ( n/ 2 ) / 3 ≥ n/ 7 . But n can only be picante if the two sums differ by at most
   2 2
   2 / 3, so in particular this requires ( b n/ 2 c ) / 3 ≤ b n/ 7 c + 2 / 3 ⇔ b n/ 4 c ≤ 3 b n/ 49 c + 2.
   This cannot happen for n ≥ 12; checking the remaining few cases by hand, we findn = 1 , 2 , 3 , 7 are picante, for a total of 4 values.
   2 4 6 8