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

HMMT February 2004 — Guts Round — Problem 9

[6] A positive integer n is picante if n ! ends in the same number of zeroes whether written in base 7 or in base 8. How many of the numbers 1 , 2 , . . . , 2004 are picante? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HARVARD-MIT MATHEMATICS TOURNAMENT, FEBRUARY 28, 2004 — GUTS ROUND 2 4 6 8

解析

A positive integer n is picante if n ! ends in the same number of zeroes whether written in base 7 or in base 8. How many of the numbers 1 , 2 , . . . , 2004 are picante? Solution: 4 2 The number of zeroes in base 7 is the total number of factors of 7 in 1 · 2 · · · n , which is ⌊ ⌋ ⌊ ⌋ 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 k is one-third the number of factors of 2 in the product n !. Now n/ 2 / 3 ≥ n/ 7 for all k k k , 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 find n = 1 , 2 , 3 , 7 are picante, for a total of 4 values. 2 4 6 8