Đề thi Olympic sinh viên thế giới năm 2004

Chia sẻ: Trần Bá Trung4 | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

128
lượt xem 16
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

" Đề thi Olympic sinh viên thế giới năm 2004 " . Đây là một sân chơi lớn để sinh viên thế giới có dịp gặp gỡ, trao đổi, giao lưu và thể hiện khả năng học toán, làm toán của mình. Từ đó đến nay, các kỳ thi Olympic sinh viênthế giới đã liên tục được mở rộng quy mô rất lớn. Kỳ thi này là một sự kiện quan trọng đối với phong trào học toán của sinh viên thế giới trong trường...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề thi Olympic sinh viên thế giới năm 2004

11th International Mathematical Competition for University Students Skopje, 25–26 July 2004 Solutions for problems on Day 2 1. Let A be a real 4 × 2 matrix and B be a real 2 × 4 matrix such that   1 0 −1 0 0 1 0 −1 AB = −1 0 . 1 0 0 −1 0 1 Find BA. [20 points] A1 Solution. Let A = and B = B1 B2 where A1 , A2 , B1 , B2 are 2 × 2 matrices. Then A2   1 0 −1 0 0  1 0 −1 = A1 B1 B2 = A1 B1 A1 B2 −1 0 1 0 A2 A2 B1 A2 B2 0 −1 0 1 therefore, A1 B1 = A2 B2 = I2 and A1 B2 = A2 B1 = −I2 . Then B1 = A−1 , B2 = −A−1 and A2 = B2 = 1 1 −1 −A1 . Finally, A1 2 0 BA = B1 B2 = B1 A1 + B2 A2 = 2I2 = A2 0 2 2. Let f, g : [a, b] → [0, ∞) be continuous and non-decreasing functions such that for each x ∈ [a, b] we have x x f (t) dt ≤ g(t) dt a a b b and a f (t) dt = g(t) dt. a b b Prove that a 1 + f (t) dt ≥ a 1 + g(t) dt. [20 points] x x Solution. Let F (x) = a f (t) dt and G(x) = a g(t) dt. The functions F, G are convex, F (a) = 0 = G(a) and F (b) = G(b) by the hypothesis. We are supposed to show that b b 2 2 1 + F (t) dt ≥ 1 + G (t) dt a a i.e. The length ot the graph of F is ≥ the length of the graph of G. This is clear since both functions are convex, their graphs have common ends and the graph of F is below the graph of G — the length of the graph of F is the least upper bound of the lengths of the graphs of piecewise linear functions whose values at the points of non-diﬀerentiability coincide with the values of F , if a convex polygon P1 is contained in a polygon P2 then the perimeter of P1 is ≤ the perimeter of P2 . 3. Let D be the closed unit disk in the plane, and let p1 , p2 , . . . , pn be ﬁxed points in D. Show that there exists a point p in D such that the sum of the distances of p to each of p1 , p2 , . . . , pn is greater than or equal to 1. [20 points] Solution. considering as vectors, thoose p to be the unit vector which points into the opposite direction as n pi . Then, by the triangle inequality, i=1 n n n |p − pi | ≥ np − pi = n + pi ≥ n.. i=1 i=1 i=1
4. For n ≥ 1 let M be an n × n complex matrix with distinct eigenvalues λ1 , λ2 , . . . , λk , with multiplicities m1 , m2 , . . . , mk , respectively. Consider the linear operator LM deﬁned by LM (X) = M X + XM T , for any complex n × n matrix X. Find its eigenvalues and their multiplicities. (M T denotes the transpose of M ; that is, if M = (mk,l ), then M T = (ml,k ).) [20 points] Solution. We ﬁrst solve the problem for the special case when the eigenvalues of M are distinct and all sums λr + λs are diﬀerent. Let λr and λs be two eigenvalues of M and vr , vs eigenvectors associated to them, i.e. T M vj = λvj for j = r, s. We have M vr (vs )T +vr (vs )T M T = (M vr )(vs )T +vr M vs = λr vr (vs )T +λs vr (vs )T , so vr (vs ) is an eigenmatrix of LM with the eigenvalue λr + λs . Notice that if λr = λs then vectors u, w are linearly independent and matrices u(w)T and w(u)T are linearly independent, too. This implies that the eigenvalue λr + λs is double if r = s. The map LM maps n2 –dimensional linear space into itself, so it has at most n2 eigenvalues. We already found n2 eigenvalues, so there exists no more and the problem is solved for the special case. In the general case, matrix M is a limit of matrices M1 , M2 , . . . such that each of them belongs to the special case above. By the continuity of the eigenvalues we obtain that the eigenvalues of LM are • 2λr with multiplicity m2 (r = 1, . . . , k); r • λr + λs with multiplicity 2mr ms (1 ≤ r < s ≤ k). (It can happen that the sums λr + λs are not pairwise diﬀerent; for those multiple values the multiplicities should be summed up.) 5. Prove that 1 1 dx dy ≤ 1. [20 points] 0 0 x−1 + | ln y| − 1 Solution 1. First we use the inequality x−1 − 1 ≥ | ln x|, x ∈ (0, 1], which follows from (x−1 − 1) x=1 = | ln x||x=1 = 0, 1 1 (x−1 − 1) = − 2 ≤ − = | ln x| , x ∈ (0, 1]. x x Therefore 1 1 1 1 1 1 dx dy dx dy dx dy −1 + | ln y| − 1 ≤ = . 0 0 x 0 0 | ln x| + | ln y| 0 0 | ln(x · y)| Substituting y = u/x, we obtain 1 1 1 1 1 dx dy dx du du = = | ln u| · = 1. 0 0 | ln(x · y)| 0 u x | ln u| 0 | ln u| Solution 2. Substituting s = x−1 − 1 and u = s − ln y, 1 1 ∞ ∞ ∞ u dx dy es−u es e−u −1 + | ln y| − 1 = duds = ds dsdu. 0 0 x 0 s (s + 1)2 u 0 0 (s + 1)2 u es Since the function (s+1)2 is convex, u es u eu ds ≤ +1 0 (s + 1)2 2 (u + 1)2 so 1 1 ∞ ∞ ∞ dx dy u eu e−u 1 du ≤ +1 du = + e−u du = 1. 0 0 x−1 + | ln y| − 1 0 2 (u + 1)2 u 2 0 (u + 1)2 0
6. For n ≥ 0 deﬁne matrices An and Bn as follows: A0 = B0 = (1) and for every n > 0 An−1 An−1 An−1 An−1 An = and Bn = . An−1 Bn−1 An−1 0 Denote the sum of all elements of a matrix M by S(M ). Prove that S(Ak−1 ) = S(An−1 ) for every n, k ≥ 1. n k [20 points] k−1 Solution. The quantity S(An ) has a special combinatorical meaning. Consider an n × k table ﬁlled with 0’s and 1’s such that no 2 × 2 contains only 1’s. Denote the number of such ﬁllings by Fnk . The ﬁlling of each row of the table corresponds to some integer ranging from 0 to 2n − 1 written in base 2. Fnk equals to the number of k-tuples of integers such that every two consecutive integers correspond to the ﬁlling of n × 2 table without 2 × 2 squares ﬁlled with 1’s. Consider binary expansions of integers i and j in in−1 . . . i1 and jn jn−1 . . . j1 . There are two cases: 1. If in jn = 0 then i and j can be consecutive iﬀ in−1 . . . i1 and jn−1 . . . j1 can be consequtive. 2. If in = jn = 1 then i and j can be consecutive iﬀ in−1 jn−1 = 0 and in−2 . . . i1 and jn−2 . . . j1 can be consecutive. Hence i and j can be consecutive iﬀ (i + 1, j + 1)-th entry of An is 1. Denoting this entry by ai,j , the sum n −1 n −1 S(Ak−1 ) = 21 =0 · · · 2k =0 ai1 i2 ai2 i3 · · · aik−1 ik counts the possible ﬁllings. Therefore Fnk = S(Ak−1 ). n i i n The the obvious statement Fnk = Fkn completes the proof.
11th International Mathematical Competition for University Students Skopje, 25–26 July 2004 Solutions for problems on Day 1 Problem 1. Let S be an inﬁnite set of real numbers such that |s1 + s2 + · · · + sk | < 1 for every ﬁnite subset {s1 , s2 , . . . , sk } ⊂ S. Show that S is countable. [20 points] 1 Solution. Let Sn = S ∩ ( n , ∞) for any integer n > 0. It follows from the inequality that |Sn | < n. Similarly, if we 1 deﬁne S−n = S ∩ (−∞, − n ), then |S−n | < n. Any nonzero x ∈ S is an element of some Sn or S−n , because there 1 1 exists an n such that x > n , or x < − n . Then S ⊂ {0} ∪ (Sn ∪ S−n ), S is a countable union of ﬁnite sets, and n∈N hence countable. Problem 2. Let P (x) = x2 − 1. How many distinct real solutions does the following equation have: P (P (. . . (P (x)) . . . )) = 0 ? [20 points] 2004 Solution. Put Pn (x) = P (P (...(P (x))...)). As P1 (x) ≥ −1, for each x ∈ R, it must be that Pn+1 (x) = P1 (Pn (x)) ≥ n −1, for each n ∈ N and each x ∈ R. Therefore the equation Pn (x) = a, where a < −1 has no real solutions. Let us prove that the equation Pn (x) = a, where a > 0, has exactly two distinct real solutions. To this end we use mathematical induction by n. If n = 1 the assertion follows directly. Assuming that the assertion holds for a n ∈ N we prove that it must also hold for n + 1. Since Pn+1 (x) = a is equivalent to P1 (Pn (x)) = a, we conclude √ √ √ √ that Pn (x) = a + 1 or Pn (x) = − a + 1. The equation Pn (x) = a + 1, as a + 1 > 1, has exactly two distinct √ real solutions by the inductive hypothesis, while the equation Pn (x) = − a + 1 has no real solutions (because √ − a + 1 < −1). Hence the equation Pn+1 (x) = a, has exactly two distinct real solutions. Let us prove now that the equation Pn (x) = 0 has exactly n + 1 distinct real solutions. Again we √ use mathematical induction. If n = 1 the solutions are x = ±1, and if n = 2 the solutions are x = 0 and x = ± 2, so in both cases the number of solutions is equal to n + 1. Suppose that the assertion holds for some n ∈ N . 2 2 Note that Pn+2 (x) = P2 (Pn (x)) = Pn (x)(Pn (x) − 2), so the set of all real solutions of the equation Pn+2 = √ is 0 √ exactly the union of the sets of all real solutions of the equations Pn (x) = 0, Pn (x) = 2 and Pn (x) = − 2. By the inductive hypothesis√ equation Pn (x) = 0 has exactly n + 1 distinct real solutions, while the equations √ the Pn (x) = 2 and Pn (x) = − 2 have two and no distinct real solutions, respectively. Hence, the sets above being pairwise disjoint, the equation Pn+2 (x) = 0 has exactly n + 3 distinct real solutions. Thus we have proved that, for each n ∈ N , the equation Pn (x) = 0 has exactly n + 1 distinct real solutions, so the answer to the question posed in this problem is 2005. n π Problem 3. Let Sn be the set of all sums xk , where n ≥ 2, 0 ≤ x1 , x2 , . . . , xn ≤ 2 and k=1 n sin xk = 1 . k=1 a) Show that Sn is an interval. [10 points] b) Let ln be the length of Sn . Find lim ln . [10 points] n→∞ Solution. (a) Equivalently, we consider the set Y = {y = (y1 , y2 , ..., yn )| 0 ≤ y1 , y2 , ..., yn ≤ 1, y1 + y2 + ... + yn = 1} ⊂ Rn and the image f (Y ) of Y under f (y) = arcsin y1 + arcsin y2 + ... + arcsin yn . Note that f (Y ) = Sn . Since Y is a connected subspace of Rn and f is a continuous function, the image f (Y ) is also connected, and we know that the only connected subspaces of R are intervals. Thus Sn is an interval.
(b) We prove that 1 π ≤ x1 + x2 + ... + xn ≤ . n arcsin n 2 Since the graph of sin x is concave down for x ∈ [0, π ], the chord joining the points (0, 0) and ( π , 1) lies below the 2 2 graph. Hence 2x π ≤ sin x for all x ∈ [0, ] π 2 and we can deduce the right-hand side of the claim: 2 (x1 + x2 + ... + xn ) ≤ sin x1 + sin x2 + ... + sin xn = 1. π The value 1 can be reached choosing x1 = π and x2 = · · · = xn = 0. 2 The left-hand side follows immediately from Jensen’s inequality, since sin x is concave down for x ∈ [0, π ] and 2 0 ≤ x1 +x2 +...+xn < π n 2 1 sin x1 + sin x2 + ... + sin xn x1 + x2 + ... + xn = ≤ sin . n n n 1 Equality holds if x1 = · · · = xn = arcsin n . Now we have computed the minimum and maximum of interval Sn ; we can conclude that Sn = [n arcsin n , π ]. 1 2 Thus ln = π − n arcsin n and 2 1 π arcsin(1/n) π lim ln = − lim = − 1. n→∞ 2 n→∞ 1/n 2 Problem 4. Suppose n ≥ 4 and let M be a ﬁnite set of n points in R3 , no four of which lie in a plane. Assume that the points can be coloured black or white so that any sphere which intersects M in at least four points has the property that exactly half of the points in the intersection of M and the sphere are white. Prove that all of the points in M lie on one sphere. [20 points] −1, if X is white Solution. Deﬁne f : M → {−1, 1}, f (X) = . The given condition becomes X∈S f (X) = 0 1, if X is black for any sphere S which passes through at least 4 points of M . For any 3 given points A, B, C in M , denote by S (A, B, C) the set of all spheres which pass through A, B, C and at least one other point of M and by |S (A, B, C)| the number of these spheres. Also, denote by the sum X∈M f (X). We have 0= f (X) = (|S (A, B, C)| − 1) (f (A) + f (B) + f (C)) + (1) S∈S(A,B,C) X∈S since the values of A, B, C appear |S (A, B, C)| times each and the other values appear only once. If there are 3 points A, B, C such that |S (A, B, C)| = 1, the proof is ﬁnished. If |S (A, B, C)| > 1 for any distinct points A, B, C in M , we will prove at ﬁrst that = 0. Assume that > 0. From (1) it follows that f (A) + f (B) + f (C) < 0 and summing by all n possible 3 choices of (A, B, C) we obtain that n 3 < 0, which means < 0 (contradicts the starting assumption). The same reasoning is applied when assuming < 0. Now, from = 0 and (1), it follows that f (A) + f (B) + f (C) = 0 for any distinct points A, B, C in M . Taking another point D ∈ M , the following equalities take place f (A) + f (B) + f (C) = 0 f (A) + f (B) + f (D) = 0 f (A) + f (C) + f (D) = 0 f (B) + f (C) + f (D) = 0 which easily leads to f (A) = f (B) = f (C) = f (D) = 0, which contradicts the deﬁnition of f . 2k−4 Problem 5. Let X be a set of k−2 + 1 real numbers, k ≥ 2. Prove that there exists a monotone sequence {xi }k ⊆ X such that i=1 |xi+1 − x1 | ≥ 2|xi − x1 | for all i = 2, . . . , k − 1. [20 points]
Solution. We prove a more general statement: Lemma. Let k, l ≥ 2, let X be a set of k+l−4 + 1 real numbers. Then either X contains an increasing sequence k−2 {xi }k ⊆ X of length k and i=1 |xi+1 − x1 | ≥ 2|xi − x1 | ∀i = 2, . . . , k − 1, or X contains a decreasing sequence {xi }l ⊆ X of length l and i=1 |xi+1 − x1 | ≥ 2|xi − x1 | ∀i = 2, . . . , l − 1. Proof of the lemma. We use induction on k + l. In case k = 2 or l = 2 the lemma is obviously true. Now let us make the induction step. Let m be the minimal element of X, M be its maximal element. Let m+M m+M Xm = {x ∈ X : x ≤ }, XM = {x ∈ X : x > }. 2 2 k+l−4 k+(l−1)−4 (k−1)+l−4 Since k−2 = k−2 + (k−1)−2 , we can see that either (k − 1) + l − 4 k + (l − 1) − 4 |Xm | ≥ + 1, or |XM | ≥ + 1. (k − 1) − 2 k−2 In the ﬁrst case we apply the inductive assumption to Xm and either obtain a decreasing sequence of length l with the required properties (in this case the inductive step is made), or obtain an increasing sequence {xi }k−1 ⊆ i=1 Xm of length k − 1. Then we note that the sequence {x1 , x2 , . . . , xk−1 , M } ⊆ X has length k and all the required properties. In the case |XM | ≥ k+(l−1)−4 + 1 the inductive step is made in a similar way. Thus the lemma is proved. k−2 The reader may check that the number k+l−4 + 1 cannot be smaller in the lemma. k−2 Problem 6. For every complex number z ∈ {0, 1} deﬁne / f (z) := (log z)−4 , where the sum is over all branches of the complex logarithm. a) Show that there are two polynomials P and Q such that f (z) = P (z)/Q(z) for all z ∈ C \ {0, 1}. [10 points] b) Show that for all z ∈ C \ {0, 1} z 2 + 4z + 1 f (z) = z . [10 points] 6(z − 1)4 Solution 1. It is clear that the left hand side is well deﬁned and independent of the order of summation, because we have a sum of the type n−4 , and the branches of the logarithms do not matter because all branches are taken. It is easy to check that the convergence is locally uniform on C \ {0, 1}; therefore, f is a holomorphic function on the complex plane, except possibly for isolated singularities at 0 and 1. (We omit the detailed estimates here.) The function log has its only (simple) zero at z = 1, so f has a quadruple pole at z = 1. Now we investigate the behavior near inﬁnity. We have Re(log(z)) = log |z|, hence (with c := log |z|) | (log z)−4 | ≤ | log z|−4 = (log |z| + 2πin)−4 + O(1) ∞ = (c + 2πix)−4 dx + O(1) −∞ ∞ = c−4 (1 + 2πix/c)−4 dx + O(1) −∞ ∞ = c−3 (1 + 2πit)−4 dt + O(1) −∞ ≤ α(log |z|)−3 for a universal constant α. Therefore, the inﬁnite sum tends to 0 as |z| → ∞. In particular, the isolated singularity at ∞ is not essential, but rather has (at least a single) zero at ∞.
The remaining singularity is at z = 0. It is readily veriﬁed that f (1/z) = f (z) (because log(1/z) = − log(z)); this implies that f has a zero at z = 0. We conclude that the inﬁnite sum is holomorphic on C with at most one pole and without an essential singularity at ∞, so it is a rational function, i.e. we can write f (z) = P (z)/Q(z) for some polynomials P and Q which we may as well assume coprime. This solves the ﬁrst part. Since f has a quadruple pole at z = 1 and no other poles, we have Q(z) = (z − 1)4 up to a constant factor which we can as well set equal to 1, and this determines P uniquely. Since f (z) → 0 as z → ∞, the degree of P is at most 3, and since P (0) = 0, it follows that P (z) = z(az 2 + bz + c) for yet undetermined complex constants a, b, c. There are a number of ways to compute the coeﬃcients a, b, c, which turn out to be a = c = 1/6, b = 2/3. Since f (z) = f (1/z), it follows easily that a = c. Moreover, the fact lim (z − 1)4 f (z) = 1 implies a + b + c = 1 z→1 (this fact follows from the observation that at z = 1, all summands cancel pairwise, except the principal branch which contributes a quadruple pole). Finally, we can calculate   1 f (−1) = π −4 n−4 = 2π −4 n−4 = 2π −4  n−4 − n−4  = . 48 nodd n≥1odd n≥1 n≥1even This implies a − b + c = −1/3. These three equations easily yield a, b, c. Moreover, the function f satisﬁes f (z) + f (−z) = 16f (z 2 ): this follows because the branches of log(z 2 ) = log((−z)2 ) are the numbers 2 log(z) and 2 log(−z). This observation supplies the two equations b = 4a and a = c, which can be used instead of some of the considerations above. 1 dz Another way is to compute g(z) = (log z)2 ﬁrst. In the same way, g(z) = (z−1)2 . The unknown coeﬃcient d can be computed from lim (z − 1)2 g(z) = 1; it is d = 1. Then the exponent 2 in the denominator can be increased z→1 by taking derivatives (see Solution 2). Similarly, one can start with exponent 3 directly. A more straightforward, though tedious way to ﬁnd the constants is computing the ﬁrst four terms of the Laurent series of f around z = 1. For that branch of the logarithm which vanishes at 1, for all |w| < 1 we have 2 w2 w3 w4 log(1 + w) = w − + − + O(|w|5 ); 2 3 4 after some computation, one can obtain 1 7 1 = w−4 + 2w−2 + w−2 + w−1 + O(1). log(1 + w)4 6 6 The remaining branches of logarithm give a bounded function. So 7 1 f (1 + w) = w−4 + 2w−2 + w−2 + w−1 6 6 (the remainder vanishes) and 1 + 2(z − 1) + 7 (z − 1)2 + 1 (z − 1)3 6 6 z(z 2 + 4z + 1) f (z) = = . (z − 1)4 6(z − 1)4 Solution 2. ¿From the well-known series for the cotangent function, N 1 i iw lim = cot N →∞ w + 2πi · k 2 2 k=−N and N i log z 1 i i log z i e2i· 2 + 1 1 1 lim = cot = ·i i log z = + . N →∞ log z + 2πi · k 2 2 2 e2i· 2 − 1 2 z−1 k=−N Taking derivatives we obtain 1 1 1 z = −z · + = , (log z)2 2 z−1 (z − 1)2 1 z z z(z + 1) 3 =− · = (log z) 2 (z − 1)2 2(z − 1)3 and 1 z z(z + 1) z(z 2 + 4z + 1) 4 =− · = . (log z) 3 2(z − 1)3 2(z − 1)4