imc1994-solutions

International Competition in Mathematics for Universtiy Students in Plovdiv, Bulgaria 1994 1 PROBLEMS AND SOLUTIONS First day — July 29, 1994 Problem 1. (13 points) a) Let A be a n × n, n ≥ 2, symmetric, invertible matrix with real positive elements. Show that zn ≤ n 2 − 2n, where zn is the number of zero elements in A−1. b) How many zero elements are there in the inverse of the n× n matrix A =   1 1 1 1 . . . 1 1 2 2 2 . . . 2 1 2 1 1 . . . 1 1 2 1 2 . . . 2 . . . . . . . . . . . . . . . . . . . . 1 2 1 2 . . . . . .   ? Solution. Denote by aij and bij the elements of A and A −1, respectively. Then for k 6= m we have n∑ i=0 akibim = 0 and from the positivity of aij we conclude that at least one of {bim : i = 1, 2, . . . , n} is positive and at least one is negative. Hence we have at least two non-zero elements in every column of A−1. This proves part a). For part b) all bij are zero except b1,1 = 2, bn,n = (−1) n, bi,i+1 = bi+1,i = (−1) i for i = 1, 2, . . . , n− 1. Problem 2. (13 points) Let f ∈ C1(a, b), lim x→a+ f(x) = +∞, lim x→b− f(x) = −∞ and f ′(x)+ f2(x) ≥ −1 for x ∈ (a, b). Prove that b−a ≥ pi and give an example where b− a = pi. Solution. From the inequality we get d dx (arctg f(x) + x) = f ′(x) 1 + f2(x) + 1 ≥ 0 for x ∈ (a, b). Thus arctg f(x)+x is non-decreasing in the interval and using the limits we get pi 2 + a ≤ − pi 2 + b. Hence b− a ≥ pi. One has equality for f(x) = cotg x, a = 0, b = pi. Problem 3. (13 points) 2 Given a set S of 2n − 1, n ∈ N, different irrational numbers. Prove that there are n different elements x1, x2, . . . , xn ∈ S such that for all non- negative rational numbers a1, a2, . . . , an with a1 + a2 + · · ·+ an > 0 we have that a1x1 + a2x2 + · · ·+ anxn is an irrational number. Solution. Let I be the set of irrational numbers, Q – the set of rational numbers, Q+ = Q∩ [0,∞). We work by induction. For n = 1 the statement is trivial. Let it be true for n − 1. We start to prove it for n. From the induction argument there are n − 1 different elements x1, x2, . . . , xn−1 ∈ S such that (1) a1x1 + a2x2 + · · · + an−1xn−1 ∈ I for all a1, a2, . . . , an ∈ Q + with a1 + a2 + · · ·+ an−1 > 0. Denote the other elements of S by xn, xn+1, . . . , x2n−1. Assume the state- ment is not true for n. Then for k = 0, 1, . . . , n − 1 there are rk ∈ Q such that (2) n−1∑ i=1 bikxi + ckxn+k = rk for some bik, ck ∈ Q +, n−1∑ i=1 bik + ck > 0. Also (3) n−1∑ k=0 dkxn+k = R for some dk ∈ Q +, n−1∑ k=0 dk > 0, R ∈ Q. If in (2) ck = 0 then (2) contradicts (1). Thus ck 6= 0 and without loss of generality one may take ck = 1. In (2) also n−1∑ i=1 bik > 0 in view of xn+k ∈ I. Replacing (2) in (3) we get n−1∑ k=0 dk ( − n−1∑ i=1 bikxi + rk ) = R or n−1∑ i=1 ( n−1∑ k=0 dkbik ) xi ∈ Q, which contradicts (1) because of the conditions on b′s and d′s. Problem 4. (18 points) Let α ∈ R \ {0} and suppose that F and G are linear maps (operators) from Rn into Rn satisfying F ◦G−G ◦ F = αF . a) Show that for all k ∈ N one has F k ◦G−G ◦ F k = αkF k. b) Show that there exists k ≥ 1 such that F k = 0. 3 Solution. For a) using the assumptions we have F k ◦G−G ◦ F k = k∑ i=1 ( F k−i+1 ◦G ◦ F i−1 − F k−i ◦G ◦ F i ) = = k∑ i=1 F k−i ◦ (F ◦G−G ◦ F ) ◦ F i−1 = = k∑ i=1 F k−i ◦ αF ◦ F i−1 = αkF k. b) Consider the linear operator L(F ) = F ◦G−G◦F acting over all n×n matrices F . It may have at most n2 different eigenvalues. Assuming that F k 6= 0 for every k we get that L has infinitely many different eigenvalues αk in view of a) – a contradiction. Problem 5. (18 points) a) Let f ∈ C[0, b], g ∈ C(R) and let g be periodic with period b. Prove that ∫ b 0 f(x)g(nx)dx has a limit as n →∞ and lim n→∞ ∫ b 0 f(x)g(nx)dx = 1 b ∫ b 0 f(x)dx · ∫ b 0 g(x)dx. b) Find lim n→∞ ∫ pi 0 sinx 1 + 3cos 2nx dx. Solution. Set ‖g‖1 = ∫ b 0 |g(x)|dx and ω(f, t) = sup {|f(x)− f(y)| : x, y ∈ [0, b], |x− y| ≤ t} . In view of the uniform continuity of f we have ω(f, t) → 0 as t → 0. Using the periodicity of g we get ∫ b 0 f(x)g(nx)dx = n∑ k=1 ∫ bk/n b(k−1)/n f(x)g(nx)dx = n∑ k=1 f(bk/n) ∫ bk/n b(k−1)/n g(nx)dx + n∑ k=1 ∫ bk/n b(k−1)/n {f(x)− f(bk/n)}g(nx)dx = 1 n n∑ k=1 f(bk/n) ∫ b 0 g(x)dx + O(ω(f, b/n)‖g‖1) 4 = 1 b n∑ k=1 ∫ bk/n b(k−1)/n f(x)dx ∫ b 0 g(x)dx + 1 b n∑ k=1 ( b n f(bk/n)− ∫ bk/n b(k−1)/n f(x)dx )∫ b 0 g(x)dx + O(ω(f, b/n)‖g‖1) = 1 b ∫ b 0 f(x)dx ∫ b 0 g(x)dx + O(ω(f, b/n)‖g‖1). This proves a). For b) we set b = pi, f(x) = sinx, g(x) = (1 + 3cos 2x)−1. From a) and ∫ pi 0 sinxdx = 2, ∫ pi 0 (1 + 3cos 2x)−1dx = pi 2 we get lim n→∞ ∫ pi 0 sinx 1 + 3cos 2nx dx = 1. Problem 6. (25 points) Let f ∈ C2[0, N ] and |f ′(x)| < 1, f ′′(x) > 0 for every x ∈ [0, N ]. Let 0 ≤ m0 < m1 < · · · < mk ≤ N be integers such that ni = f(mi) are also integers for i = 0, 1, . . . , k. Denote bi = ni − ni−1 and ai = mi − mi−1 for i = 1, 2, . . . , k. a) Prove that −1 < b1 a1 < b2 a2 < · · · < bk ak < 1. b) Prove that for every choice of A > 1 there are no more than N/A indices j such that aj > A. c) Prove that k ≤ 3N 2/3 (i.e. there are no more than 3N 2/3 integer points on the curve y = f(x), x ∈ [0, N ]). Solution. a) For i = 1, 2, . . . , k we have bi = f(mi)− f(mi−1) = (mi −mi−1)f ′(xi) for some xi ∈ (mi−1,mi). Hence bi ai = f ′(xi) and so −1 < bi ai < 1. From the convexity of f we have that f ′ is increasing and bi ai = f ′(xi) < f ′(xi+1) = bi+1 ai+1 because of xi < mi < xi+1. 5 b) Set SA = {j ∈ {0, 1, . . . , k} : aj > A}. Then N ≥ mk −m0 = k∑ i=1 ai ≥ ∑ j∈SA aj > A|SA| and hence |SA| < N/A. c) All different fractions in (−1, 1) with denominators less or equal A are no more 2A2. Using b) we get k < N/A + 2A2. Put A = N 1/3 in the above estimate and get k < 3N 2/3. Second day — July 30, 1994 Problem 1. (14 points) Let f ∈ C1[a, b], f(a) = 0 and suppose that λ ∈ R, λ > 0, is such that |f ′(x)| ≤ λ|f(x)| for all x ∈ [a, b]. Is it true that f(x) = 0 for all x ∈ [a, b]? Solution. Assume that there is y ∈ (a, b] such that f(y) 6= 0. Without loss of generality we have f(y) > 0. In view of the continuity of f there exists c ∈ [a, y) such that f(c) = 0 and f(x) > 0 for x ∈ (c, y]. For x ∈ (c, y] we have |f ′(x)| ≤ λf(x). This implies that the function g(x) = ln f(x)− λx is not increasing in (c, y] because of g ′(x) = f ′(x) f(x) −λ ≤ 0. Thus ln f(x)−λx ≥ ln f(y)− λy and f(x) ≥ eλx−λyf(y) for x ∈ (c, y]. Thus 0 = f(c) = f(c + 0) ≥ eλc−λyf(y) > 0 — a contradiction. Hence one has f(x) = 0 for all x ∈ [a, b]. Problem 2. (14 points) Let f : R2 → R be given by f(x, y) = (x2 − y2)e−x 2 −y2 . a) Prove that f attains its minimum and its maximum. b) Determine all points (x, y) such that ∂f ∂x (x, y) = ∂f ∂y (x, y) = 0 and determine for which of them f has global or local minimum or maximum. Solution. We have f(1, 0) = e−1, f(0, 1) = −e−1 and te−t ≤ 2e−2 for t ≥ 2. Therefore |f(x, y)| ≤ (x2 + y2)e−x 2 −y2 ≤ 2e−2 < e−1 for (x, y) /∈ M = {(u, v) : u2 + v2 ≤ 2} and f cannot attain its minimum and its 6 maximum outside M . Part a) follows from the compactness of M and the continuity of f . Let (x, y) be a point from part b). From ∂f ∂x (x, y) = 2x(1 − x2 + y2)e−x 2 −y2 we get (1) x(1− x2 + y2) = 0. Similarly (2) y(1 + x2 − y2) = 0. All solutions (x, y) of the system (1), (2) are (0, 0), (0, 1), (0,−1), (1, 0) and (−1, 0). One has f(1, 0) = f(−1, 0) = e−1 and f has global maximum at the points (1, 0) and (−1, 0). One has f(0, 1) = f(0,−1) = −e−1 and f has global minimum at the points (0, 1) and (0,−1). The point (0, 0) is not an extrema point because of f(x, 0) = x2e−x 2 > 0 if x 6= 0 and f(y, 0) = −y2e−y 2 < 0 if y 6= 0. Problem 3. (14 points) Let f be a real-valued function with n + 1 derivatives at each point of R. Show that for each pair of real numbers a, b, a < b, such that ln ( f(b) + f ′(b) + · · ·+ f (n)(b) f(a) + f ′(a) + · · ·+ f (n)(a) ) = b− a there is a number c in the open interval (a, b) for which f (n+1)(c) = f(c). Note that ln denotes the natural logarithm. Solution. Set g(x) = ( f(x) + f ′(x) + · · ·+ f (n)(x) ) e−x. From the assumption one get g(a) = g(b). Then there exists c ∈ (a, b) such that g′(c) = 0. Replacing in the last equality g ′(x) = ( f (n+1)(x)− f(x) ) e−x we finish the proof. Problem 4. (18 points) Let A be a n× n diagonal matrix with characteristic polynomial (x− c1) d1(x− c2) d2 . . . (x− ck) dk , where c1, c2, . . . , ck are distinct (which means that c1 appears d1 times on the diagonal, c2 appears d2 times on the diagonal, etc. and d1+d2+· · ·+dk = n). 7 Let V be the space of all n×n matrices B such that AB = BA. Prove that the dimension of V is d21 + d 2 2 + · · ·+ d 2 k. Solution. Set A = (aij) n i,j=1, B = (bij) n i,j=1, AB = (xij) n i,j=1 and BA = (yij) n i,j=1. Then xij = aiibij and yij = ajjbij . Thus AB = BA is equivalent to (aii − ajj)bij = 0 for i, j = 1, 2, . . . , n. Therefore bij = 0 if aii 6= ajj and bij may be arbitrary if aii = ajj. The number of indices (i, j) for which aii = ajj = cm for some m = 1, 2, . . . , k is d 2 m. This gives the desired result. Problem 5. (18 points) Let x1, x2, . . . , xk be vectors of m-dimensional Euclidian space, such that x1+x2+ · · ·+xk = 0. Show that there exists a permutation pi of the integers {1, 2, . . . , k} such that ∥∥∥∥∥ n∑ i=1 xpi(i) ∥∥∥∥∥ ≤ ( k∑ i=1 ‖xi‖ 2 )1/2 for each n = 1, 2, . . . , k. Note that ‖ · ‖ denotes the Euclidian norm. Solution. We define pi inductively. Set pi(1) = 1. Assume pi is defined for i = 1, 2, . . . , n and also (1) ∥∥∥∥∥ n∑ i=1 xpi(i) ∥∥∥∥∥ 2 ≤ n∑ i=1 ‖xpi(i)‖ 2. Note (1) is true for n = 1. We choose pi(n + 1) in a way that (1) is fulfilled with n + 1 instead of n. Set y = n∑ i=1 xpi(i) and A = {1, 2, . . . , k} \ {pi(i) : i = 1, 2, . . . , n}. Assume that (y, xr) > 0 for all r ∈ A. Then ( y, ∑ r∈A xr ) > 0 and in view of y + ∑ r∈A xr = 0 one gets −(y, y) > 0, which is impossible. Therefore there is r ∈ A such that (2) (y, xr) ≤ 0. Put pi(n + 1) = r. Then using (2) and (1) we have ∥∥∥∥∥ n+1∑ i=1 xpi(i) ∥∥∥∥∥ 2 = ‖y + xr‖ 2 = ‖y‖2 + 2(y, xr) + ‖xr‖ 2 ≤ ‖y‖2 + ‖xr‖ 2 ≤ 8 ≤ n∑ i=1 ‖xpi(i)‖ 2 + ‖xr‖ 2 = n+1∑ i=1 ‖xpi(i)‖ 2, which verifies (1) for n + 1. Thus we define pi for every n = 1, 2, . . . , k. Finally from (1) we get∥∥∥∥∥ n∑ i=1 xpi(i) ∥∥∥∥∥ 2 ≤ n∑ i=1 ‖xpi(i)‖ 2 ≤ k∑ i=1 ‖xi‖ 2. Problem 6. (22 points) Find lim N→∞ ln2 N N N−2∑ k=2 1 ln k · ln(N − k) . Note that ln denotes the natural logarithm. Solution. Obviously (1) AN = ln2 N N N−2∑ k=2 1 ln k · ln(N − k) ≥ ln2 N N · N − 3 ln2 N = 1− 3 N . Take M , 2 ≤ M < N/2. Then using that 1 ln k · ln(N − k) is decreasing in [2, N/2] and the symmetry with respect to N/2 one get AN = ln2 N N   M∑ k=2 + N−M−1∑ k=M+1 + N−2∑ k=N−M   1ln k · ln(N − k) ≤ ≤ ln2 N N { 2 M − 1 ln 2 · ln(N − 2) + N − 2M − 1 lnM · ln(N −M) } ≤ ≤ 2 ln 2 · M lnN N + ( 1− 2M N ) lnN lnM + O ( 1 lnN ) . Choose M = [ N ln2 N ] + 1 to get (2) AN ≤ ( 1− 2 N ln2 N ) lnN lnN − 2 ln lnN +O ( 1 lnN ) ≤ 1+O ( ln lnN lnN ) . Estimates (1) and (2) give lim N→∞ ln2 N N N−2∑ k=2 1 ln k · ln(N − k) = 1.