HMMT 二月 2012 · TEAM1 赛 · 第 9 题
HMMT February 2012 — TEAM1 Round — Problem 9
题目详情
- [ 40 ] For any positive integer n , let N = φ (1) + φ (2) + ... + φ ( n ). Show that there exists a sequence a , a , ...a 1 2 N containing exactly φ ( k ) instances of k for all positive integers k ≤ n such that 1 1 1
-
- ... + = 1. a a a a a a 1 2 2 3 N 1
解析
- [ 40 ] For any positive integer n , let N = ϕ (1) + ϕ (2) + . . . + ϕ ( n ). Show that there exists a sequence a , a , . . . , a 1 2 N containing exactly ϕ ( k ) instances of k for all positive integers k ≤ n such that 1 1 1
-
- · · · + = 1. a a a a a a 1 2 2 3 N 1 Answer: see below We write all fractions of the form b/a , where a and b are relatively prime, and 0 ≤ b ≤ a ≤ n , in ascending order. For instance, for n = 5, this is the sequence 0 1 1 1 2 1 3 2 3 4 1 , , , , , , , , , , . 1 5 4 3 5 2 5 3 4 5 1 This sequence is known as the Farey sequence . Now, if we look at the the sequence of the denominators of the fractions, we see that k appears ϕ ( k ) times when k > 1, although 1 appears twice. Thus, there are N + 1 elements in the Farey sequence. Let the Farey sequence be b b b N +1 1 2 , , . . . , a a a 1 2 N +1 Now, a = 1, so the sequence a , a , . . . , a contains ϕ ( k ) instances of k for every 1 ≤ k ≤ n . We N +1 1 2 N claim that this sequence also satisfies 1 1 1
-
- · · · + = 1. a a a a a a 1 2 2 3 N 1 Since a = a = 1, we have 1 N +1 1 1 1 1 1 1
-
- · · · + = + + · · · + . a a a a a a a a a a a a 1 2 2 3 N 1 1 2 2 3 N N +1 b 1 i +1 b i Now, it will suffice to show that = − . Once we have shown this, the above sum will a a a a i i +1 i +1 i b N +1 b 1 telescope to − = 1 − 0 = 1. a a N +1 1 b b 1 i +1 i To see why = − holds, we note that this is equivalent to 1 = b a − b a . We i +1 i i i +1 a a a a i i +1 i +1 i can prove this fact geometrically: consider the triangle in the plane with vertices (0 , 0), ( a , b ), and i i Team A ( a , b ). This triangle contains these three boundary points, but it contains no other boundary or i +1 i +1 interior points since a and a are relatively prime to b and b , respectively, and since no other i i +1 i i +1 b b i +1 i fraction with denominator at most n lies between and . Thus, by Pick’s theorem, this triangle a a i i +1 1 has area 1 / 2. But the area of the triangle can also be computed as the cross product ( b a − b a ); i +1 i i i +1 2 hence b a − b a = 1 and we are done. i +1 i i i +1