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

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

Thêm vào BST

Báo xấu

129
lượt xem 12
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 2003 " . Đâ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 2003

10th International Mathematical Competition for University Students Cluj-Napoca, July 2003 Day 1 1. (a) Let a1 , a2 , . . . be a sequence of real numbers such that a1 = 1 and an+1 > 3 an for all n. 2 Prove that the sequence an 3 n−1 2 has a ﬁnite limit or tends to inﬁnity. (10 points) (b) Prove that for all α > 1 there exists a sequence a1 , a2 , . . . with the same properties such that an lim n−1 = α. 3 2 (10 points) an 3 Solution. (a) Let bn = . Then an+1 > 2 an is equivalent to bn+1 > bn , thus the sequence 3 n−1 2 (bn ) is strictly increasing. Each increasing sequence has a ﬁnite limit or tends to inﬁnity. (b) For all α > 1 there exists a sequence 1 = b1 < b2 < . . . which converges to α. Choosing 3 n−1 an = 2 bn , we obtain the required sequence (an ). 2. Let a1 , a2 . . . , a51 be non-zero elements of a ﬁeld. We simultaneously replace each element with the sum of the 50 remaining ones. In this way we get a sequence b1 . . . , b51 . If this new sequence is a permutation of the original one, what can be the characteristic of the ﬁeld? (The characteristic of a ﬁeld is p, if p is the smallest positive integer such that x + x + . . . + x = 0 for any element x p of the ﬁeld. If there exists no such p, the characteristic is 0.) (20 points) Solution. Let S = a1 + a2 + · · · + a51 . Then b1 + b2 + · · · + b51 = 50S. Since b1 , b2 , · · · , b51 is a permutation of a1 , a2 , · · · , a51 , we get 50S = S, so 49S = 0. Assume that the characteristic of the ﬁeld is not equal to 7. Then 49S = 0 implies that S = 0. Therefore bi = −ai for i = 1, 2, · · · , 51. On the other hand, bi = aϕ(i) , where ϕ ∈ S51 . Therefore, if the characteristic is not 2, the sequence a1 , a2 , · · · , a51 can be partitioned into pairs {ai , aϕ(i) } of additive inverses. But this is impossible, since 51 is an odd number. It follows that the characteristic of the ﬁeld is 7 or 2. The characteristic can be either 2 or 7. For the case of 7, x1 = . . . = x51 = 1 is a possible choice. For the case of 2, any elements can be chosen such that S = 0, since then bi = −ai = ai . 3. Let A be an n × n real matrix such that 3A3 = A2 + A + I (I is the identity matrix). Show that the sequence Ak converges to an idempotent matrix. (A matrix B is called idempotent if B 2 = B.) (20 points) Solution. The minimal polynomial of A is a divisor of 3x3 − x2 − x − 1. This polynomial has three diﬀerent roots. This implies that A is diagonalizable: A = C −1 DC where D is a diagonal matrix. The eigenvalues of the matrices A and D are all roots of polynomial 3x3 − x2 − x − 1. One of the three roots is 1, the remaining two roots have smaller absolute value than 1. Hence, the diagonal elements of Dk , which are the kth powers of the eigenvalues, tend to either 0 or 1 and the limit M = lim Dk is idempotent. Then lim Ak = C −1 M C is idempotent as well. 4. Determine the set of all pairs (a, b) of positive integers for which the set of positive integers can be decomposed into two sets A and B such that a · A = b · B. (20 points) Solution. Clearly a and b must be diﬀerent since A and B are disjoint. 1
10th International Mathematical Competition for University Students Cluj-Napoca, July 2003 Day 2 1. Let A and B be n × n real matrices such that AB + A + B = 0. Prove that AB = BA. Solution. Since (A + I)(B + I) = AB + A + B + I = I (I is the identity matrix), matrices A + I and B + I are inverses of each other. Then (A + I)(B + I) = (B + I)(A + I) and AB + BA. 2. Evaluate the limit 2x sinm t lim dt (m, n ∈ N). x→0+ x tn sin t sin t Solution. We use the fact that is decreasing in the interval (0, π) and lim = 1. t t→0+0 t sin 2x sin t For all x ∈ (0, π ) and t ∈ [x, 2x] we have 2 x< < 1, thus 2 t m 2x m 2x 2x m sin 2x t sinm t t < dt < dt, 2x x tn x tn x tn 2x m 2 t n dt = xm−n+1 um−n du. x t 1 m sin 2x The factor tends to 1. If m − n + 1 < 0, the limit of xm−n+1 is inﬁnity; if 2x 2 m − n + 1 > 0 then 0. If m − n + 1 = 0 then xm−n+1 1 um−n du = ln 2. Hence,  2x 0, m≥n sinm t  lim dt = ln 2, n − m = 1 . x→0+0 tn  +∞, n − m > 1.  x 3. Let A be a closed subset of Rn and let B be the set of all those points b ∈ Rn for which there exists exactly one point a0 ∈ A such that |a0 − b| = inf |a − b|. a∈A Prove that B is dense in Rn ; that is, the closure of B is Rn . Solution. Let b0 ∈ A (otherwise b0 ∈ A ⊂ B), / = inf |a − b0 |. The intersection of the ball a∈A of radius + 1 with centre b0 with set A is compact and there exists a0 ∈ A: |a0 − b0 | = . 1
Denote by Br (a) = {x ∈ Rn : |x − a| ≤ r} and ∂Br (a) = {x ∈ Rn : |x − a| = r} the ball and the sphere of center a and radius r, respectively. If a0 is not the unique nearest point then for any point a on the open line segment (a0 , b0 ) we have B|a−a0 | (a) ⊂ B (b0 ) and ∂B|a−a0 | (a) ∂B (b0 ) = {a0 }, therefore (a0 , b0 ) ⊂ B and b0 is an accumulation point of set B. 4. Find all positive integers n for which there exists a family F of three-element subsets of S = {1, 2, . . . , n} satisfying the following two conditions: (i) for any two diﬀerent elements a, b ∈ S, there exists exactly one A ∈ F containing both a, b; (ii) if a, b, c, x, y, z are elements of S such that if {a, b, x}, {a, c, y}, {b, c, z} ∈ F, then {x, y, z} ∈ F. Solution. The condition (i) of the problem allows us to deﬁne a (well-deﬁned) operation ∗ on the set S given by a ∗ b = c if and only if {a, b, c} ∈ F, where a = b. We note that this operation is still not deﬁned completely (we need to deﬁne a ∗ a), but nevertheless let us investigate its features. At ﬁrst, due to (i), for a = b the operation obviously satisﬁes the following three conditions: (a) a = a ∗ b = b; (b) a ∗ b = b ∗ a; (c) a ∗ (a ∗ b) = b. What does the condition (ii) give? It claims that (e’) x ∗ (a ∗ c) = x ∗ y = z = b ∗ c = (x ∗ a) ∗ c for any three diﬀerent x, a, c, i.e. that the operation is associative if the arguments are diﬀerent. Now we can complete the deﬁnition of ∗. In order to save associativity for non- diﬀerent arguments, i.e. to make b = a ∗ (a ∗ b) = (a ∗ a) ∗ b hold, we will add to S an extra element, call it 0, and deﬁne (d) a ∗ a = 0 and a ∗ 0 = 0 ∗ a = a. Now it is easy to check that, for any a, b, c ∈ S ∪ {0}, (a),(b),(c) and (d), still hold, and (e) a ∗ b ∗ c := (a ∗ b) ∗ c = a ∗ (b ∗ c). We have thus obtained that (S ∪ {0}, ∗) has the structure of a ﬁnite Abelian group, whose elements are all of order two. Since the order of every such group is a power of 2, we conclude that |S ∪ {0}| = n + 1 = 2m and n = 2m − 1 for some integer m ≥ 1. Given n = 2m −1, according to what we have proven till now, we will construct a family of three-element subsets of S satisfying (i) and (ii). Let us deﬁne the operation ∗ in the following manner: if a = a0 + 2a1 + . . . + 2m−1 am−1 and b = b0 + 2b1 + . . . + 2m−1 bm−1 , where ai , bi are either 0 or 1, we put a ∗ b = |a0 − b0 | + 2|a1 − b1 | + . . . + 2m−1 |am−1 − bm−1 |. 2
It is simple to check that this ∗ satisﬁes (a),(b),(c) and (e’). Therefore, if we include in F all possible triples a, b, a ∗ b, the condition (i) follows from (a),(b) and (c), whereas the condition (ii) follows from (e’) The answer is: n = 2m − 1. 5. (a) Show that for each function f : Q × Q → R there exists a function g : Q → R such that f (x, y) ≤ g(x) + g(y) for all x, y ∈ Q. (b) Find a function f : R × R → R for which there is no function g : R → R such that f (x, y) ≤ g(x) + g(y) for all x, y ∈ R. Solution. a) Let ϕ : Q → N be a bijection. Deﬁne g(x) = max{|f (s, t)| : s, t ∈ Q, ϕ(s) ≤ ϕ(x), ϕ(t) ≤ ϕ(x)}. We have f (x, y) ≤ max{g(x), g(y)} ≤ g(x) + g(y). 1 b) We shall show that the function deﬁned by f (x, y) = |x−y| for x = y and f (x, x) = 0 satisﬁes the problem. If, by contradiction there exists a function g as above, it results, that 1 g(y) ≥ |x−y| − f (x) for x, y ∈ R, x = y; one obtains that for each x ∈ R, lim g(y) = ∞. y→x We show, that there exists no function g having an inﬁnite limit at each point of a bounded and closed interval [a, b]. For each k ∈ N+ denote Ak = {x ∈ [a, b] : |g(x)| ≤ k}. We have obviously [a, b] = ∪∞ Ak . The set [a, b] is uncountable, so at least one of the k=1 sets Ak is inﬁnite (in fact uncountable). This set Ak being inﬁnite, there exists a sequence in Ak having distinct terms. This sequence will contain a convergent subsequence (xn )n∈N convergent to a point x ∈ [a, b]. But lim g(y) = ∞ implies that g(xn ) → ∞, a contradiction y→x because |g(xn )| ≤ k, ∀n ∈ N. Second solution for part (b). Let S be the set of all sequences of real numbers. The 2 cardinality of S is |S| = |R|ℵ0 = 2ℵ0 = 2ℵ0 = |R|. Thus, there exists a bijection h : R → S. Now deﬁne the function f in the following way. For any real x and positive integer n, let f (x, n) be the nth element of sequence h(x). If y is not a positive integer then let f (x, y) = 0. We prove that this function has the required property. Let g be an arbitrary R → R function. We show that there exist real numbers x, y such that f (x, y) > g(x) + g(y). Consider the sequence (n + g(n))∞ . This sequence is an n=1 element of S, thus (n + g(n))∞ = h(x) for a certain real x. Then for an arbitrary positive n=1 integer n, f (x, n) is the nth element, f (x, n) = n + g(n). Choosing n such that n > g(x), we obtain f (x, n) = n + g(n) > g(x) + g(n). 6. Let (an )n∈N be the sequence deﬁned by n 1 ak a0 = 1, an+1 = . n+1 k=0 n−k+2 Find the limit n ak lim , n→∞ k=0 2k 3
if it exists. Solution. Consider the generating function f (x) = ∞ an xn . By induction 0 < an ≤ 1, n=0 thus this series is absolutely convergent for |x| < 1, f (0) = 1 and the function is positive in the interval [0, 1). The goal is to compute f ( 1 ). 2 By the recurrence formula, ∞ ∞ n n ak f (x) = (n + 1)an+1 x = xn = n=0 n=0 k=0 n−k+2 ∞ ∞ ∞ k xn−k xm = ak x = f (x) . k=0 n=k n−k+2 m=0 m+2 Then ∞ x f xm+1 ln f (x) = ln f (x) − ln f (0) = = = 0 f m=0 (m + 1)(m + 2) ∞ ∞ xm+1 xm+1 1 xm+1 1 1 = − =1+ 1− =1+ 1− ln , m=0 (m + 1) (m + 2) x m=0 (m + 1) x 1−x 1 ln f = 1 − ln 2, 2 1 e and thus f ( ) = . 2 2 4
Let {a, b} be a solution and consider the sets A, B such that a · A = b · B. Denoting d = (a, b) the greatest common divisor of a and b, we have a = d·a1 , b = d·b1 , (a1 , b1 ) = 1 and a1 ·A = b1 ·B. Thus {a1 , b1 } is a solution and it is enough to determine the solutions {a, b} with (a, b) = 1. If 1 ∈ A then a ∈ a · A = b · B, thus b must be a divisor of a. Similarly, if 1 ∈ B, then a is a divisor of b. Therefore, in all solutions, one of numbers a, b is a divisor of the other one. Now we prove that if n ≥ 2, then (1, n) is a solution. For each positive integer k, let f (k) be the largest non-negative integer for which nf (k) |k. Then let A = {k : f (k) is odd} and B = {k : f (k) is even}. This is a decomposition of all positive integers such that A = n · B. 5. Let g : [0, 1] → R be a continuous function and let fn : [0, 1] → R be a sequence of functions deﬁned by f0 (x) = g(x) and x 1 fn+1 (x) = fn (t)dt (x ∈ (0, 1], n = 0, 1, 2, . . .). x 0 Determine lim fn (x) for every x ∈ (0, 1]. (20 points) n→∞ B. We shall prove in two diﬀerent ways that limn→∞ fn (x) = g(0) for every x ∈ (0, 1]. (The second one is more lengthy but it tells us how to calculate fn directly from g.) Proof I. First we prove our claim for non-decreasing g. In this case, by induction, one can easily see that 1. each fn is non-decrasing as well, and 2. g(x) = f0 (x) ≥ f1 (x) ≥ f2 (x) ≥ . . . ≥ g(0) (x ∈ (0, 1]). Then (2) implies that there exists h(x) = lim fn (x) (x ∈ (0, 1]). n→∞ Clearly h is non-decreasing and g(0) ≤ h(x) ≤ fn (x) for any x ∈ (0, 1], n = 0, 1, 2, . . .. Therefore to show that h(x) = g(0) for any x ∈ (0, 1], it is enough to prove that h(1) cannot be greater than g(0). Suppose that h(1) > g(0). Then there exists a 0 < δ < 1 such that h(1) > g(δ). Using the deﬁnition, (2) and (1) we get 1 δ 1 fn+1 (1) = fn (t)dt ≤ g(t)dt + fn (t)dt ≤ δg(δ) + (1 − δ)fn (1). 0 0 δ Hence fn (1) − fn+1 (1) ≥ δ(fn (1) − g(δ)) ≥ δ(h(1) − g(δ)) > 0, so fn (1) → −∞, which is a contradiction. Similarly, we can prove our claim for non-increasing continuous functions as well. Now suppose that g is an arbitrary continuous function on [0, 1]. Let M (x) = sup g(t), m(x) = inf g(t) (x ∈ [0, 1]) t∈[0,x] t∈[0,x] Then on [0, 1] m is non-increasing, M is non-decreasing, both are continuous, m(x) ≤ g(x) ≤ M (x) and M (0) = m(0) = g(0). Deﬁne the sequences of functions Mn (x) and mn (x) in the same way as fn is deﬁned but starting with M0 = M and m0 = m. Then one can easily see by induction that mn (x) ≤ fn (x) ≤ Mn (x). By the ﬁrst part of the proof, limn mn (x) = m(0) = g(0) = M (0) = limn Mn (x) for any x ∈ (0, 1]. Therefore we must have limn fn (x) = g(0). 2
Proof II. To make the notation clearer we shall denote the variable of fj by xj . By deﬁnition (and Fubini theorem) we get that xn+1 xn xn−1 x1 x2 1 1 1 1 fn+1 (xn+1 ) = ... g(x0 )dx0 dx1 . . . dxn xn+1 0 xn 0 xn−1 0 0 x1 0 1 dx0 dx1 . . . dxn = g(x0 ) xn+1 0≤x0 ≤x1 ≤...≤xn ≤xn+1 x1 . . . xn xn+1 1 dx1 . . . dxn = g(x0 ) dx0 . xn+1 0 x0 ≤x1 ≤...≤xn ≤xn+1 x1 . . . xn Therefore with the notation dx1 . . . dxn hn (a, b) = a≤x1 ≤...≤xn ≤b x1 . . . xn and x = xn+1 , t = x0 we have x 1 fn+1 (x) = g(t)hn (t, x)dt. x 0 Using that hn (a, b) is the same for any permutation of x1 , . . . , xn and the fact that the integral is 0 on any hyperplanes (xi = xj ) we get that b b dx1 . . . dxn dx1 . . . dxn n! hn (a, b) = = ... a≤x1 ,...,xn ≤b x1 . . . xn a a x1 . . . xn n b dx = = (log(b/a))n . a x Therefore x 1 (log(x/t))n fn+1 (x) = g(t) dt. x 0 n! Note that if g is constant then the deﬁnition gives fn = g. This implies on one hand that we must have 1 x (log(x/t))n dt = 1 x 0 n! and on the other hand that, by replacing g by g − g(0), we can suppose that g(0) = 0. Let x ∈ (0, 1] and ε > 0 be ﬁxed. By continuity there exists a 0 < δ < x and an M such that |g(t)| < ε on [0, δ] and |g(t)| ≤ M on [0, 1] . Since (log(x/δ))n lim =0 n→∞ n! there exists an n0 sucht that log(x/δ))n /n! < ε whenever n ≥ n0 . Then, for any n ≥ n0 , we have x 1 (log(x/t))n |fn+1 (x)| ≤ |g(t)| dt x 0 n! 1 δ (log(x/t))n 1 x (log(x/δ))n ≤ ε dt + |g(t)| dt x 0 n! x δ n! 1 x (log(x/t))n 1 x ≤ ε dt + M εdt x 0 n! x δ ≤ ε + M ε. Therefore limn f (x) = 0 = g(0). 3
6. Let f (z) = an z n + an−1 z n−1 + . . . + a1 z + a0 be a polynomial with real coeﬃcients. Prove that if all roots of f lie in the left half-plane {z ∈ C : Re z < 0} then ak ak+3 < ak+1 ak+2 holds for every k = 0, 1, . . . , n − 3. (20 points) Solution. The polynomial f is a product of linear and quadratic factors, f (z) = i (ki z + li ) · 2 j (pj z + qj z + rj ), with ki , li , pj , qj , rj ∈ R. Since all roots are in the left half-plane, for each i, ki and li are of the same sign, and for each j, pj , qj , rj are of the same sign, too. Hence, multiplying f by −1 if necessary, the roots of f don’t change and f becomes the polynomial with all positive coeﬃcients. For the simplicity, we extend the sequence of coeﬃcients by an+1 = an+2 = . . . = 0 and a−1 = a−2 = . . . = 0 and prove the same statement for −1 ≤ k ≤ n − 2 by induction. For n ≤ 2 the statement is obvious: ak+1 and ak+2 are positive and at least one of ak−1 and ak+3 is 0; hence, ak+1 ak+2 > ak ak+3 = 0. Now assume that n ≥ 3 and the statement is true for all smaller values of n. Take a divisor of f (z) which has the form z 2 + pz + q where p and q are positive real numbers. (Such a divisor can be obtained from a conjugate pair of roots or two real roots.) Then we can write f (z) = (z 2 + pz + q)(bn−2 z n−2 + . . . + b1 z + b0 ) = (z 2 + pz + q)g(x). (1) The roots polynomial g(z) are in the left half-plane, so we have bk+1 bk+2 < bk bk+3 for all −1 ≤ k ≤ n − 4. Deﬁning bn−1 = bn = . . . = 0 and b−1 = b−2 = . . . = 0 as well, we also have bk+1 bk+2 ≤ bk bk+3 for all integer k. Now we prove ak+1 ak+2 > ak ak+3 . If k = −1 or k = n − 2 then this is obvious since ak+1 ak+2 is positive and ak ak+3 = 0. Thus, assume 0 ≤ k ≤ n − 3. By an easy computation, ak+1 ak+2 − ak ak+3 = = (qbk+1 + pbk + bk−1 )(qbk+2 + pbk+1 + bk ) − (qbk + pbk−1 + bk−2 )(qbk+3 + pbk+2 + bk+1 ) = = (bk−1 bk − bk−2 bk+1 ) + p(b2 − bk−2 bk+2 ) + q(bk−1 bk+2 − bk−2 bk+3 )+ k +p2 (bk bk+1 − bk−1 bk+2 ) + q 2 (bk+1 bk+2 − bk bk+3 ) + pq(b2 − bk−1 bk+3 ). k+1 We prove that all the six terms are non-negative and at least one is positive. Term p2 (bk bk+1 − bk−1 bk+2 ) is positive since 0 ≤ k ≤ n − 3. Also terms bk−1 bk − bk−2 bk+1 and q 2 (bk+1 bk+2 − bk bk+3 ) are non-negative by the induction hypothesis. To check the sign of p(b2 − bk−2 bk+2 ) consider k bk−1 (b2 − bk−2 bk+2 ) = bk−2 (bk bk+1 − bk−1 bk+2 ) + bk (bk−1 bk − bk−2 bk+1 ) ≥ 0. k If bk−1 > 0 we can divide by it to obtain b2 −bk−2 bk+2 ≥ 0. Otherwise, if bk−1 = 0, either bk−2 = 0 k or bk+2 = 0 and thus b2 − bk−2 bk+2 = b2 ≥ 0. Therefore, p(b2 − bk−2 bk+2 ) ≥ 0 for all k. Similarly, k k k pq(b2 − bk−1 bk+3 ) ≥ 0. k+1 The sign of q(bk−1 bk+2 − bk−2 bk+3 ) can be checked in a similar way. Consider bk+1 (bk−1 bk+2 − bk−2 bk+3 ) = bk−1 (bk+1 bk+2 − bk bk+3 ) + bk+3 (bk−1 bk − bk−2 bk+1 ) ≥ 0. If bk+1 > 0, we can divide by it. Otherwise either bk−2 = 0 or bk+3 = 0. In all cases, we obtain bk−1 bk+2 − bk−2 bk+3 ≥ 0. Now the signs of all terms are checked and the proof is complete. 4