HMMT 二月 2012 · TEAM1 赛 · 第 9 题

英文解析

9. [ 40 ] For any positive integer n , let N = ϕ (1) + ϕ (2) + . . . + ϕ ( n ). Show that there exists a sequencea , a , . . . , a
   1 2 Ncontaining 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 bebb 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 Nclaim 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
   1 i +1 bbi
   Now, it will suffice to show that = − . Once we have shown this, the above sum willa a a ai i +1 i +1 ib
   N +1 btelescope to − = 1 − 0 = 1.1
   a a
   N +1 1
   1 i +1 bbi
   To see why = − holds, we note that this is equivalent to 1 = b a − b a . Wei +1 i i i +1
   a a a ai i +1 i +1 ican prove this fact geometrically: consider the triangle in the plane with vertices (0 , 0), ( a , b ), andi i
   Team A
   ( a , b ). This triangle contains these three boundary points, but it contains no other boundary ori +1 i +1
   interior points since a and a are relatively prime to b and b , respectively, and since no otheri i +1 i i +1
   b i +1 bifraction with denominator at most n lies between and . Thus, by Pick’s theorem, this trianglea ai i +1
   has area 1 / 2. But the area of the triangle can also be computed as the cross product ( b a − b a );1
   i +1 i i i +1
   hence b a − b a = 1 and we are done.2
   i +1 i i i +1