HMMT 十一月 2011 · 冲刺赛 · 第 15 题

HMMT November 2011 — Guts Round — Problem 15

[8] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . TH 4 ANNUAL HARVARD-MIT NOVEMBER TOURNAMENT, 12 NOVEMBER 2011— GUTS ROUND School Team Team ID#

解析

[ 8 ] For positive integers n , let L ( n ) be the largest factor of n other than n itself. Determine the number of ordered pairs of composite positive integers ( m, n ) for which L ( m ) L ( n ) = 80. Answer: 12 Let x be an integer, and let p be the smallest prime factor of x . Then, if L ( a ) = x , x px we note that we must have a = px for some prime p ≤ p . (Otherwise, if p > p , then > x . If p is x x p x composite, then kx > x for some factor k of x .) So we have: • L ( a ) = 2 , 4 , 8 , 10 , 16 , 20 , 40 ⇒ 1 value for a • L ( a ) = 5 ⇒ 3 values for a Hence, we note that, since m and n are composite, we cannot have L ( m ) = 1 or L ( n ) = 1, so the possible pairs ( L ( m ) , L ( n )) are (2 , 40) , (4 , 20) , (5 , 16) , (8 , 10) and vice-versa. We add the number of choices for each pair, and double since m and n are interchangeable, to get 2(1 × 1 + 1 × 1 + 3 × 1 + 1 × 1) = 12 possible ordered pairs ( m, n ).