HMMT 十一月 2012 · 团队赛 · 第 3 题

HMMT November 2012 — Team Round — Problem 3

[ 6 ] Find the largest integer less than 2012 all of whose divisors have at most two 1’s in their binary representations. Permutations A permutation π is defined as a function from a set of integers to itself that rearranges the elements of the set. For example, a possible permutation of the numbers from 1 through 4 is the function π given by π (1) = 2, π (2) = 4, π (3) = 3, π (4) = 1.

解析

[ 6 ] Find the largest integer less than 2012 all of whose divisors have at most two 1’s in their binary representations. Answer: 1536 Call a number good if all of its positive divisors have at most two 1’s in their binary k representations. Then, if p is an odd prime divisor of a good number, p must be of the form 2 + 1. The only such primes less than 2012 are 3, 5, 17, and 257, so the only possible prime divisors of n are 2, 3, 5, 17, and 257. i j i + j i j Next, note that since (2 + 1)(2 + 1) = 2 + 2 + 2 + 1, if either i or j is greater than 1, then i j i j there will be at least 3 1’s in the binary representation of (2 + 1)(2 + 1), so (2 + 1)(2 + 1) cannot 1 1 3 divide a good number. On the other hand, if i = j = 1, then (2 + 1)(2 + 1) = 9 = 2 + 1, so 9 is a good number and can divide a good number. Finally, note that since multiplication by 2 in binary just appends additional 0s, so if n is a good number, then 2 n is also a good number. k It therefore follows that any good number less than 2012 must be of the form c · 2 , where c belongs to { 1 , 3 , 5 , 9 , 17 , 257 } (and moreover, all such numbers are good). It is then straightforward to check that 9 the largest such number is 1536 = 3 · 2 .