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

" Đề thi Olympic sinh viên thế giới năm 2006 " . Đâ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...
Nội dung trích xuất từ tài liệu:
Đề thi Olympic sinh viên thế giới năm 2006 13th International Mathematics Competition for University Students Odessa, July 20-26, 2006 First DayProblem 1. Let f : R → R be a real function. Prove or disprove each of the following statements. (a) If f is continuous and range(f ) = R then f is monotonic. (b) If f is monotonic and range(f ) = R then f is continuous. (c) If f is monotonic and f is continuous then range(f ) = R.(20 points)Solution. (a) False. Consider function f (x) = x3 − x. It is continuous, range(f ) = R but, for example,f (0) = 0, f ( 1 ) = − 8 and f (1) = 0, therefore f (0) > f ( 2 ), f ( 1 ) < f (1) and f is not monotonic. 2 3 1 2 (b) True. Assume first that f is non-decreasing. For an arbitrary number a, the limits lim f and a−lim f exist and lim f ≤ lim f . If the two limits are equal, the function is continuous at a. Otherwise,a+ a− a+if lim f = b < lim f = c, we have f (x) ≤ b for all x < a and f (x) ≥ c for all x > a; therefore a− a+range(f ) ⊂ (−∞, b) ∪ (c, ∞) ∪ {f (a)} cannot be the complete R. For non-increasing f the same can be applied writing reverse relations or g(x) = −f (x). (c) False. The function g(x) = arctan x is monotonic and continuous, but range(g) = (−π/2, π/2) = R.Problem 2. Find the number of positive integers x satisfying the following two conditions: 1. x < 102006 ; 2. x2 − x is divisible by 102006 .(20 points)Solution 1. Let Sk = 0 < x < 10k x2 − x is divisible by 10k and s (k) = |Sk | , k ≥ 1. Let x =ak+1 ak . . . a1 be the decimal writing of an integer x ∈ Sk+1 , k ≥ 1. Then obviously y = ak . . . a1 ∈ Sk . Now, 2let y = ak . . . a1 ∈ Sk be fixed. Considering ak+1 as a variable digit, we have x2 − x = ak+1 10k + y − ak+1 10k + y = (y 2 − y) + ak+1 10k (2y − 1) + a2 102k . Since y 2 − y = 10k z for an iteger z, it follows that k+1x2 − x is divisible by 10k+1 if and only if z + ak+1 (2y − 1) ≡ 0 (mod 10). Since y ≡ 3 (mod 10) is obviouslyimpossible, the congruence has exactly one solution. Hence we obtain a one-to-one correspondence betweenthe sets Sk+1 and Sk for every k ≥ 1. Therefore s (2006) = s (1) = 3, because S1 = {1, 5, 6} .Solution 2. Since x2 − x = x(x − 1) and the numbers x and x − 1 are relatively prime, one of them mustbe divisible by 22006 and one of them (may be the same) must be divisible by 52006 . Therefore, x mustsatisfy the following two conditions: x ≡ 0 or 1 (mod 22006 ); x ≡ 0 or 1 (mod 52006 ).Altogether we have 4 cases. The Chinese remainder theorem yields that in each case there is a uniquesolution among the numbers 0, 1, . . . , 102006 − 1. These four numbers are different because each two givesdifferent residues modulo 22006 or 52006 . Moreover, one of the numbers is 0 which is not allowed. Therefore there exist 3 solutions.Problem 3. Let A be an n × n-matrix with integer entries and b1 , . . . , bk be integers satisfying det A =b1 · . . . · bk . Prove that there exist n × n-matrices B1 , . . . , Bk with integer entries such that A = B1 · . . . · Bkand det Bi = bi for all i = 1, . . . , k.(20 points)Solution. By induction, it is enough to consider the case m = 2. Furthermore, we can multiply A withany integral matrix with determinant 1 from the right or from the left, without changing the problem.Hence we can assume A to be upper triangular. 1 13th International Mathematics Competition for University Students Odessa, July 20-26, 2006 Second DayProblem 1. Let V be a convex polygon with n vertices. (a) Prove that if n is divisible by 3 then V can be triangulated (i.e. dissected into non-overlappingtriangles whose vertices are vertices of V ) so that each vertex of V is the vertex of an odd numberof triangles. (b) Prove that if n is not divisible by 3 then V can be triangulated so that there are exactly twovertices that are the vertices of an even number of the triangles.(20 points)Solution. Apply induction on n. For the initial cases n = 3, 4, 5, chose the triangulations shown inthe Figure to prove the statement. odd even odd odd ...