HMMT 二月 2012 · 冲刺赛 · 第 1 题

英文解析

1 . 7
( U/L )
Answer: 1231288 For x to be such a number is equivalent to x being an k root of unity for someththk up to 2012. For each k , there are ϕ ( k ) primitive k roots of unity, so the total number of roots is
∑
2012
ϕ ( k ).
k =1
We will give a good approximation of this number using well known facts about the M¨ obius function,
{
∑
0 if n is not squarefreedefined by μ ( n ) = . It turns out that if f ( n ) = g ( d ),
d | nr
( − 1) if n has r distinct prime factors
∑ ∑ ∑
n nthen g ( n ) = μ ( d ) f ( ). Using this fact, since n = ϕ ( d ), we have that ϕ ( n ) = μ ( d ) .
d | n d | n d | nd d
∑ ∑ ∑ ∑
2012 2012
k k
Now we have reduced the problem to estimating μ ( d ) . Let a = , so we obtain aμ ( d ).
k =1 d | k k =1 d | kd d
Guts
We can interchange the order of summation by writing
2012
⌊ ⌋ ( )
2012 2012
d 2
∑ ∑ ∑
1 2012
aμ ( d ) ≈ μ ( d ) ⌊ ⌋
2 da =1
d =1 d =1
2012
∑2
2012
≈ μ ( d )
2 d 2
d =1
2012
∑2
2012 μ ( d )
2=
2 dd =1
∞
∑2
2012 μ ( d )
≈
2 d 2
d =1
{
∑
1 if n = 1
The M¨ obius function also satisfies the property that μ ( d ) = , which can be seend | n
0 otherwise
{
1 if n = 1
as a special case of the theorem above (letting f ( n ) = 1 , g ( n ) = ). We can then see that
0 otherwise
( )
(∑ )
∑ ∑ ∑
∞ μ ( d ) ∞ ∞ μ ( d ) 2012
1 1 6 3 = = 1, so = . Therefore, we have ϕ ( k ) ≈ · 2012 =2
2 2 2 2 2 2
d =1 c =1 d =1 k =1
d c 1 d π π
1230488 . 266... 2012 is large enough that all of our approximations are pretty accurate and we should be comfortable perturbing this estimate by a small factor to give bounding values.