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

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

Thêm vào BST

Báo xấu

144
lượt xem 20
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 2005 " . Đâ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 đại...

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 2005

12th International Mathematics Competition for University Students Blagoevgrad, July 22 - July 28, 2005 First Day Problem 1. Let A be the n × n matrix, whose (i, j)th entry is i + j for all i, j = 1, 2, . . . , n. What is the rank of A? Solution 1. For n = 1 the rank is 1. Now assume n ≥ 2. Since A = (i)n + (j)n , matrix A is the sum i,j=1 i,j=1 of two matrixes of rank 1. Therefore, the rank of A is at most 2. The determinant of the top-left 2 × 2 minor is −1, so the rank is exactly 2. Therefore, the rank of A is 1 for n = 1 and 2 for n ≥ 2. Solution 2. Consider the case n ≥ 2. For i = n, n − 1, . . . , 2, subtract the (i − 1)th row from the nth row. Then subtract the second row from all lower rows.       1 2 ... n 2 3 ... n + 1 2 3 ... n + 1 1 1 . . . 1   3 4 . . . n + 2  1 1 . . . 1    rank  . .  = rank  . .  = rank 0 0 . . . 0  = 2.      . .. .  . .. .   . . . . . . . .. . .. . . . n + 1 n + 2 ... 2n 1 1 ... 1 0 0 ... 0 Problem 2. For an integer n ≥ 3 consider the sets Sn = {(x1 , x2 , . . . , xn ) : ∀i xi ∈ {0, 1, 2}} An = {(x1 , x2 , . . . , xn ) ∈ Sn : ∀i ≤ n − 2 |{xi , xi+1 , xi+2 }| = 1} and Bn = {(x1 , x2 , . . . , xn ) ∈ Sn : ∀i ≤ n − 1 (xi = xi+1 ⇒ xi = 0)} . Prove that |An+1 | = 3 · |Bn |. (|A| denotes the number of elements of the set A.) Solution 1. Extend the deﬁnitions also for n = 1, 2. Consider the following sets An = {(x1 , x2 , . . . , xn ) ∈ An : xn−1 = xn } , An = An \ An , Bn = {(x1 , x2 , . . . , xn ) ∈ Bn : xn = 0} , Bn = Bn \ Bn and denote an = |An |, an = |An |, an = |An |, bn = |Bn |, bn = |Bn |, bn = |Bn | . It is easy to observe the following relations between the a–sequences   an = an + an a = an ,  n+1 an+1 = 2an + 2an which lead to an+1 = 2an + 2an−1 . For the b–sequences we have the same relations   bn = bn + bn b = bn ,  n+1 bn+1 = 2bn + 2bn therefore bn+1 = 2bn + 2bn−1 . By computing the ﬁrst values of (an ) and (bn ) we obtain a1 = 3, a2 = 9, a3 = 24 b1 = 3, b2 = 8
12th International Mathematics Competition for University Students Blagoevgrad, July 22 - July 28, 2005 Second Day Problem 1. Let f (x) = x2 + bx + c, where b and c are real numbers, and let M = {x ∈ R : |f (x)| < 1}. Clearly the set M is either empty or consists of disjoint open intervals. Denote the sum of their lengths by |M |. Prove that √ |M | ≤ 2 2. 2 2 b Solution. Write f (x) = x + 2 + d where d = c − b4 . The absolute minimum of f is d. If d ≥ 1 then f (x) ≥ 1 for all x, M = ∅ and |M | = 0. If −1 < d < 1 then f (x) > −1 for all x, 2 √ b b −1 < x+ +d
where a, b ∈ R, a1 , . . . , ak , b1 , . . . bl are positive integers and p1 , . . . , pk , q1 , . . . , ql are irre- ducible polynomials with leading coeﬃcients 1. For p3 = q 2 and the factorisation of p3 = q 2 is unique we get that a3 = b2 , k = l and for some (i1 , . . . , ik ) permutation of (1, . . . , k) we have p1 = qi1 , . . . , pk = qik and 3a1 = 2bi1 , . . . , 3ak = 2bik . Hence b1 , . . . , bl are divisible by b /3 b /3 3 let r = b1/3 · q11 · . . . · ql l be a polynomial. Since r3 = q = f 3 we have f = r. p f3 Solution 2. Let q be the simplest form of the rational function f2 . Then the simplest form 2 p2 p2 f3 of its square is q2 . On the other hand q2 = f2 = f 2 is a polynomial therefore q must f3 p be a constant and so f = f2 = q is a polynomial. Problem 3. In the linear space of all real n × n matrices, ﬁnd the maximum possible dimension of a linear subspace V such that ∀X, Y ∈ V trace(XY ) = 0. (The trace of a matrix is the sum of the diagonal entries.) Solution. If A is a nonzero symmetric matrix, then trace(A2 ) = trace(At A) is the sum of the squared entries of A which is positive. So V cannot contain any symmetric matrix but 0. Denote by S the linear space of all real n × n symmetric matrices; dim V = n(n+1) . 2 Since V ∩ S = {0}, we have dim V + dim S ≤ n2 and thus dim V ≤ n2 − n(n+1) = n(n−1) . 2 2 n(n−1) The space of strictly upper triangular matrices has dimension 2 and satisﬁes the condition of the problem. Therefore the maximum dimension of V is n(n−1) . 2 Problem 4. Prove that if f : R → R is three times diﬀerentiable, then there exists a real number ξ ∈ (−1, 1) such that f (ξ) f (1) − f (−1) = − f (0). 6 2 Solution 1. Let f (−1) 2 f (1) 2 g(x) = − x (x − 1) − f (0)(x2 − 1) + x (x + 1) − f (0)x(x − 1)(x + 1). 2 2 It is easy to check that g(±1) = f (±1), g(0) = f (0) and g (0) = f (0). Apply Rolle’s theorem for the function h(x) = f (x) − g(x) and its derivatives. Since h(−1) = h(0) = h(1) = 0, there exist η ∈ (−1, 0) and ϑ ∈ (0, 1) such that h (η) = h (ϑ) = 0. We also have h (0) = 0, so there exist ∈ (η, 0) and σ ∈ (0, ϑ) such that h ( ) = h (σ) = 0. Finally, there exists a ξ ∈ ( , σ) ⊂ (−1, 1) where h (ξ) = 0. Then f (−1) f (1) f (1) − f (−1) f (ξ) = g (ξ) = − · 6 − f (0) · 0 + · 6 − f (0) · 6 = − f (0). 2 2 2
f (1) − f (−1) Solution 2. The expression − f (0) is the divided diﬀerence f [−1, 0, 0, 1] and 2 f (ξ) there exists a number ξ ∈ (−1, 1) such that f [−1, 0, 0, 1] = . 3! Problem 5. Find all r > 0 such that whenever f : R2 → R is a diﬀerentiable function such that |grad f (0, 0)| = 1 and |grad f (u) − grad f (v)| ≤ |u − v| for all u, v ∈ R2 , then the maximum of f on the disk {u ∈ R2 : |u| ≤ r} is attained at exactly one point. (grad f (u) = (∂1 f (u), ∂2 f (u)) is the gradient vector of f at the point u. For a vector √ u = (a, b), |u| = a2 + b2 .) x2 y 2 Solution. To get an upper bound for r, set f (x, y) = x − + . This function satisﬁes 2 2 the conditions, since grad f (x, y) = (1 − x, y), grad f (0, 0) = (1, 0) and |grad f (x1 , y1 ) − grad f (x2 , y2 )| = |(x2 − x1 , y1 − y2 )| = |(x1 , y1 ) − (x2 , y2 )|. In the disk Dr = {(x, y) : x2 + y 2 ≤ r2 } 2 x2 + y 2 1 1 r2 1 f (x, y) = − x− + ≤ + . 2 2 4 2 4 1 r2 If r > 2 then the absolute maximum is 2 + 1 , attained at the points 4 1 2 ,± r2 − 1 4 . 1 1 Therefore, it is necessary that r ≤ 2 because if r > 2 then the maximum is attained twice. Suppose now that r ≤ 1/2 and that f attains its maximum on Dr at u, v, u = v. Since |grad f (z) − grad f (0)| ≤ r, |grad f (z)| ≥ 1 − r > 0 for all z ∈ Dr . Hence f may attain its maximum only at the boundary of Dr , so we must have |u| = |v| = r and grad f (u) = au and grad f (v) = bv, where a, b ≥ 0. Since au = grad f (u) and bv = grad f (v) belong to the disk D with centre grad f (0) and radius r, they do not belong to the interior of Dr . Hence |grad f (u) − grad f (v)| = |au − bv| ≥ |u − v| and this inequality is strict since D ∩ Dr contains no more than one point. But this contradicts the assumption that 1 |grad f (u) − grad f (v)| ≤ |u − v|. So all r ≤ 2 satisﬁes the condition. √ Problem 6. Prove that if p and q are rational numbers and r = p + q 7, then there exists a b 1 0 a matrix =± with integer entries and with ad − bc = 1 such that c d 0 1 ar + b = r. cr + d Solution. First consider the case when q = 0 and r is rational. Choose a positive integer t such that r2 t is an integer and set a b 1 + rt −r2 t = . c d t 1 − rt Then a b ar + b (1 + rt)r − r2 t det = 1 and = = r. c d cr + d tr + (1 − rt)
Now assume q = 0. Let the minimal polynomial of r in Z[x] be ux2 + vx + w. The other √ root of this polynomial is r = p−q 7, so v = −u(r+r) = −2up and w = urr = u(p2 −7q 2 ). The discriminant is v 2 − 4uw = 7 · (2uq)2 . The left-hand side is an integer, implying that also ∆ = 2uq is an integer. The equation ar+b = r is equivalent to cr2 + (d − a)r − b = 0. This must be a multiple cr+d of the minimal polynomial, so we need c = ut, d − a = vt, −b = wt for some integer t = 0. Putting together these equalities with ad − bc = 1 we obtain that (a + d)2 = (a − d)2 + 4ad = 4 + (v 2 − 4uw)t2 = 4 + 7∆2 t2 . Therefore 4 + 7∆2 t2 must be a perfect square. Introducing s = a + d, we need an integer solution (s, t) for the Diophantine equation s2 − 7∆2 t2 = 4 (1) such that t = 0. The numbers s and t will be even. Then a + d = s and d − a = vt will be even as well and a and d √ be really integers. will √ √ √ (8±3 7)n = kn ±ln 7 for each integer n. Then kn −7ln = (kn +ln 7)(kn −ln 7) = Let √ √ 2 2 ((8 + 3 7)n (8 − 3 7))n = 1 and the sequence (ln ) also satisﬁes the linear recurrence ln+1 = 16ln − ln−1 . Consider the residue of ln modulo ∆. There are ∆2 possible residue pairs for (ln , ln+1 ) so some are the same. Starting from such two positions, the recurrence shows that the sequence of residues is periodic in both directions. Then there are inﬁnitely many indices such that ln ≡ l0 = 0 (mod ∆). Taking such an index n, we can set s = 2kn and t = 2ln /∆. Remarks. 1. It is well-known that if D > 0 is not a perfect square then the Pell-like Diophantine equation x2 − Dy 2 = 1 has inﬁnitely many solutions. Using this fact the solution can be generalized to all quadratic algebraic numbers. 2. It is also known that the continued fraction of a real number r is periodic from a certain point if and only if r is a root of a quadratic equation. This fact can lead to another solution.
which leads to a2 = 3b1 a3 = 3b2 Now, reasoning by induction, it is easy to prove that an+1 = 3bn for every n ≥ 1. Solution 2. Regarding xi to be elements of Z3 and working “modulo 3”, we have that (x1 , x2 , . . . , xn ) ∈ An ⇒ (x1 + 1, x2 + 1, . . . , xn + 1) ∈ An , (x1 + 2, x2 + 2, . . . , xn + 2) ∈ An which means that 1/3 of the elements of An start with 0. We establish a bijection between the subset of all the vectors in An+1 which start with 0 and the set Bn by (0, x1 , x2 , . . . , xn ) ∈ An+1 −→ (y1 , y2 , . . . , yn ) ∈ Bn y1 = x1 , y2 = x2 − x1 , y3 = x3 − x2 , . . . , yn = xn − xn−1 (if yk = yk+1 = 0 then xk − xk−1 = xk+1 − xk = 0 (where x0 = 0), which gives xk−1 = xk = xk+1 , which is not possible because of the deﬁnition of the sets Ap ; therefore, the deﬁnition of the above function is correct). The inverse is deﬁned by (y1 , y2 , . . . , yn ) ∈ Bn −→ (0, x1 , x2 , . . . , xn ) ∈ An+1 x 1 = y 1 , x2 = y 1 + y 2 , . . . , x n = y 1 + y 2 + · · · + y n Problem 3. Let f : R → [0, ∞) be a continuously diﬀerentiable function. Prove that 1 1 1 2 3 2 f (x) dx − f (0) f (x) dx ≤ max |f (x)| f (x) dx . 0 0 0≤x≤1 0 Solution 1. Let M = max |f (x)|. By the inequality −M ≤ f (x) ≤ M, x ∈ [0, 1] it follows: 0≤x≤1 −M f (x) ≤ f (x) f (x) ≤ M f (x) , x ∈ [0, 1] . By integration x x 1 1 −M f (t) dt ≤ f 2 (x) − f 2 (0) ≤ M f (t) dt, x ∈ [0, 1] 0 2 2 0 x x 1 1 −M f (x) f (t) dt ≤ f 3 (x) − f 2 (0) f (x) ≤ M f (x) f (t) dt, x ∈ [0, 1] . 0 2 2 0 Integrating the last inequality on [0, 1] it follows that 2 2 1 1 1 1 −M 0 f (x)dx ≤ 0 f 3 (x) dx − f 2 (0) 0 f (x) dx ≤ M 0 f (x)dx ⇔ 2 1 1 1 0 f 3 (x) dx − f 2 (0) 0 f (x) dx ≤ M 0 f (x) dx . 1 1 Solution 2. Let M = max |f (x)| and F (x) = − x f ; then F = f , F (0) = − 0 f and F (1) = 0. 0≤x≤1 Integrating by parts, 1 1 1 f3 = f 2 · F = [f 2 F ]1 − 0 (f 2 ) F = 0 0 0 1 1 1 = f 2 (1)F (1) − f 2 (0)F (0) − 2F f f = f 2 (0) f− 2F f f . 0 0 0 Then 1 1 1 1 1 1 2 3 2 f (x) dx − f (0) f (x) dx = 2F f f ≤ 2F f |f | ≤ M 2F f = M · [F 2 ]1 0 =M f . 0 0 0 0 0 0
Problem 4. Find all polynomials P (x) = an xn + an−1 xn−1 + ... + a1 x + a0 (an = 0) satisfying the following two conditions: (i) (a0 , a1 , ..., an ) is a permutation of the numbers (0, 1, ..., n) and (ii) all roots of P (x) are rational numbers. Solution 1. Note that P (x) does not have any positive root because P (x) > 0 for every x > 0. Thus, we can represent them in the form −αi , i = 1, 2, . . . , n, where αi ≥ 0. If a0 = 0 then there is a k ∈ N, 1 ≤ k ≤ n−1, with ak = 0, so using Viete’s formulae we get ak α1 α2 ...αn−k−1 αn−k + α1 α2 ...αn−k−1 αn−k+1 + ... + αk+1 αk+2 ...αn−1 αn = = 0, an which is impossible because the left side of the equality is positive. Therefore a0 = 0 and one of the roots of the polynomial, say αn , must be equal to zero. Consider the polynomial Q(x) = an xn−1 +an−1 xn−2 +...+a1 . It has zeros −αi , i = 1, 2, . . . , n − 1. Again, Viete’s formulae, for n ≥ 3, yield: a1 α1 α2 ...αn−1 = (1) an a2 α1 α2 ...αn−2 + α1 α2 ...αn−3 αn−1 + ... + α2 α3 ...αn−1 = (2) an an−1 α1 + α2 + ... + αn−1 = . (3) an Dividing (2) by (1) we get 1 1 1 a2 + + ... + = . (4) α1 α2 αn−1 a1 From (3) and (4), applying the AM-HM inequality we obtain an−1 α1 + α2 + ... + αn−1 n−1 (n − 1)a1 = ≥ 1 1 1 = , (n − 1)an n−1 α1 + α2 + ... + αn−1 a2 2 therefore a2 an−1 ≥ (n − 1)2 . Hence n ≥ a2 an−1 ≥ (n − 1)2 , implying n ≤ 3. So, the only polynomials a1 an 2 a1 an possibly satisfying (i) and (ii) are those of degree at most three. These polynomials can easily be found and they are P (x) = x, P (x) = x2 + 2x, P (x) = 2x2 + x, P (x) = x3 + 3x2 + 2x and P (x) = 2x3 + 3x2 + x. 2 Solution 2. Consider the prime factorization of P in the ring Z[x]. Since all roots of P are rational, P can be written as a product of n linear polynomials with rational coeﬃcients. Therefore, all prime factor of P are linear and P can be written as n P (x) = (bk x + ck ) k=1 where the coeﬃcients bk , ck are integers. Since the leading coeﬃcient of P is positive, we can assume bk > 0 for all k. The coeﬃcients of P are nonnegative, so P cannot have a positive root. This implies ck ≥ 0. It is not possible that ck = 0 for two diﬀerent values of k, because it would imply a0 = a1 = 0. So ck > 0 in at least n − 1 cases. Now substitute x = 1. n n(n + 1) P (1) = an + · · · + a0 = 0 + 1 + · · · + n = = (bk + ck ) ≥ 2n−1 ; 2 k=1 therefore it is necessary that 2n−1 ≤ n(n+1) , therefore n ≤ 4. Moreover, the number n(n+1) can be written 2 2 as a product of n − 1 integers greater than 1. If n = 1, the only solution is P (x) = 1x + 0. If n = 2, we have P (1) = 3 = 1 · 3, so one factor must be x, the other one is x + 2 or 2x + 1. Both x(x + 2) = 1x2 + 2x + 0 and x(2x + 1) = 2x2 + 1x + 0 are solutions.
If n = 3, then P (1) = 6 = 1·2·3, so one factor must be x, another one is x+1, the third one is again x+2 or 2x+1. The two polynomials are x(x+1)(x+2) = 1x3 +3x2 +2x+0 and x(x+1)(2x+1) = 2x3 +3x2 +1x+0, both have the proper set of coeﬃcients. In the case n = 4, there is no solution because n(n+1) = 10 cannot be written as a product of 3 integers 2 greater than 1. Altogether we found 5 solutions: 1x+0, 1x2 +2x+0, 2x2 +1x+0, 1x3 +3x2 +2x+0 and 2x3 +3x2 +1x+0. Problem 5. Let f : (0, ∞) → R be a twice continuously diﬀerentiable function such that |f (x) + 2xf (x) + (x2 + 1)f (x)| ≤ 1 for all x. Prove that lim f (x) = 0. x→∞ Solution 1. Let g(x) = f (x) + xf (x); then f (x) + 2xf (x) + (x2 + 1)f (x) = g (x) + xg(x). We prove that if h is a continuously diﬀerentiable function such that h (x) + xh(x) is bounded then lim h = 0. Applying this lemma for h = g then for h = f , the statement follows. ∞ 2 /2 2 /2 Let M be an upper bound for |h (x)+xh(x)| and let p(x) = h(x)ex . (The function e−x is a solution of the diﬀerential equation u (x) + xu(x) = 0.) Then 2 /2 2 /2 |p (x)| = |h (x) + xh(x)|ex ≤ M ex and x x 2 /2 p(x) p(0) + 0 p |p(0)| + M 0 ex dx |h(x)| = x2 /2 = ≤ . e ex2 /2 ex2 /2 x x2 /2 x2 /2 0 e dx Since lim e = ∞ and lim = 0 (by L’Hospital’s rule), this implies limx→∞ h(x) = 0. x→∞ ex2 /2 2 f (x)ex /2 Solution 2. Apply L’Hospital rule twice on the fraction . (Note that L’Hospital rule is valid if ex2 /2 the denominator converges to inﬁnity, without any assumption on the numerator.) 2 2 /2 2 /2 f (x)ex /2 (f (x) + xf (x))ex (f (x) + 2xf (x) + (x2 + 1)f (x))ex lim f (x) = lim = lim = lim = x→∞ x→∞ ex2 /2 x→∞ xex2 /2 x→∞ (x2 + 1)ex2 /2 f (x) + 2xf (x) + (x2 + 1)f (x) = lim = 0. x→∞ x2 + 1 Problem 6. Given a group G, denote by G(m) the subgroup generated by the mth powers of elements of G. If G(m) and G(n) are commutative, prove that G(gcd(m, n)) is also commutative. (gcd(m, n) denotes the greatest common divisor of m and n.) Solution. Write d = gcd(m, n). It is easy to see that G(m), G(n) = G(d); hence, it will suﬃce to check commutativity for any two elements in G(m) ∪ G(n), and so for any two generators am and bn . Consider their commutator z = a−m b−n am bn ; then the relations z = (a−m bam )−n bn = a−m (b−n abn )m show that z ∈ G(m) ∩ G(n). But then z is in the center of G(d). Now, from the relation am bn = bn am z, it easily follows by induction that 2 aml bnl = bnl aml z l . 2 2 Setting l = m/d and l = n/d we obtain z (m/d) = z (n/d) = e, but this implies that z = e as well.