HMMT 二月 2016 · 代数 · 第 6 题
HMMT February 2016 — Algebra — Problem 6
题目详情
- Call a positive integer N ≥ 2 “special” if for every k such that 2 ≤ k ≤ N , N can be expressed as a sum of k positive integers that are relatively prime to N (although not necessarily relatively prime to each other). How many special integers are there less than 100?
解析
- Call a positive integer N ≥ 2 “special” if for every k such that 2 ≤ k ≤ N , N can be expressed as a sum of k positive integers that are relatively prime to N (although not necessarily relatively prime to each other). How many special integers are there less than 100? Proposed by: Casey Fu Answer: 50 We claim that all odd numbers are special, and the only special even number is 2. For any even N > 2, the numbers relatively prime to N must be odd. When we consider k = 3, we see that N can’t be expressed as a sum of 3 odd numbers. a a 1 2 Now suppose that N is odd, and we look at the binary decomposition of N , so write N = 2 + 2 + a j ... + 2 as a sum of distinct powers of 2. Note that all these numbers only have factors of 2 and are therefore relatively prime to N . We see that j < log N + 1. 2 We claim that for any k ≥ j , we can write N as a sum of k powers of 2. Suppose that we have N a a a a 1 2 k 1 written as N = 2 + 2 + ... + 2 . Suppose we have at least one of these powers of 2 even, say 2 . a − 1 a − 1 a a 1 1 2 k We can then write N = 2 + 2 + 2 + ... + 2 , which is k + 1 powers of 2. The only way this process cannot be carried out is if we write N as a sum of ones, which corresponds to k = N . Therefore, this gives us all k > log N . 2 a a Now we consider the case k = 2. Let 2 be the largest power of 2 such that 2 < N . We can write a a a a N = 2 + ( N − 2 ). Note that since 2 and N are relatively prime, so are N − 2 and N . Note that a a < log N . Now similar to the previous argument, we can write 2 as a sum of k powers of 2 for 2 N N a a 1 < k < 2 , and since 2 > , we can achieve all k such that 2 ≤ k < + 1. 2 2 N Putting these together, we see that since + 1 > log N for N ≥ 3, we can achieve all k from 2 2 2 through N , where N is odd.