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

" Đề thi Olympic sinh viên thế giới năm 2000 " . Đâ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...
Nội dung trích xuất từ tài liệu:
Đề thi Olympic sinh viên thế giới năm 2000 Solutions for the first day problems at the IMC 2000 Problem 1. Is it true that if f : [0, 1] → [0, 1] is a) monotone increasing b) monotone decreasing then there exists an x ∈ [0, 1] for which f (x) = x? Solution. a) Yes. Proof: Let A = {x ∈ [0, 1] : f (x) > x}. If f (0) = 0 we are done, if not then A isnon-empty (0 is in A) bounded, so it has supremum, say a. Let b = f (a). I. case: a < b. Then, using that f is monotone and a was the sup, we get b = f (a) ≤f ((a + b)/2) ≤ (a + b)/2, which contradicts a < b. II. case: a > b. Then we get b = f (a) ≥ f ((a + b)/2) > (a + b)/2 contradiction.Therefore we must have a = b. b) No. Let, for example, f (x) = 1 − x/2 if x ≤ 1/2and f (x) = 1/2 − x/2 if x > 1/2 This is clearly a good counter-example. Problem 2. Let p(x) = x5 + x and q(x) = x5 + x2 . Find all pairs (w, z) of complex numbers withw = z for which p(w) = p(z) and q(w) = q(z). Short solution. Let p(x) − p(y) P (x, y) = = x4 + x3 y + x2 y 2 + xy 3 + y 4 + 1 x−yand q(x) − q(y) Q(x, y) = = x4 + x3 y + x2 y 2 + xy 3 + y 4 + x + y. x−yWe need those pairs (w, z) which satisfy P (w, z) = Q(w, z) = 0. From P − Q = 0 we have w + z = 1. Let c = wz. After a short calculation we obtainc2 − 3c + 2 = 0, which has the solutions c = 1 and c = 2. From the system w + z = 1,wz = c we obtain the following pairs: √ √ √ √ 1 ± 3i 1 3i 1 ± 7i 1 7i , and , . 2 2 2 2 1 Solutions for the second day problems at the IMC 2000 Problem 1. a) Show that the unit square can be partitioned into n smaller squares if n is largeenough. b) Let d ≥ 2. Show that there is a constant N (d) such that, whenever n ≥ N (d), ad-dimensional unit cube can be partitioned into n smaller cubes. Solution. We start with the following lemma: If a and b be coprime positive integersthen every sufficiently large positive integer m can be expressed in the form ax + by withx, y non-negative integers. Proof of the lemma. The numbers 0, a, 2a, . . . , (b−1)a give a complete residue systemmodulo b. Consequently, for any m there exists a 0 ≤ x ≤ b − 1 so that ax ≡ m (mod b).If m ≥ (b − 1)a, then y = (m − ax)/b, for which x + by = m, is a non-negative integer, too. Now observe that any dissection of a cube into n smaller cubes may be refined togive a dissection into n + (ad − 1) cubes, for any a ≥ 1. This refinement is achieved bypicking an arbitrary cube in the dissection, and cutting it into ad smaller cubes. To provethe required result, then, it suffices to exhibit two relatively prime integers of form a d − 1.In the 2-dimensional case, a1 = 2 and a2 = 3 give the coprime numbers 22 − 1 = 3 and32 − 1 = 8. In the general case, two such integers are 2d − 1 and (2d − 1)d − 1, as is easyto check. Problem 2. Let f be continuous and nowhere monotone on [0, 1]. Show that the setof points on which f attains local minima is dense in [0, 1]. (A function is nowhere monotone if there exists no interval where the function ismonotone. A set is dense if each non-empty open interval contains at least one element ofthe set.) Solution. Let (x − α, x + α) ⊂ [0, 1] be an arbitrary non-empty open interval. Thefunction f is not monoton in the intervals [x − α, x] and [x, x + α], thus there exist somereal numbers x − α ≤ p < q ≤ x, x ≤ r < s ≤ x + α so that f (p) > f (q) and f (r) < f (s). By Weierstrass’ theorem, f has a global minimum in the interval [p, s]. The values f (p)and f (s) are not the minimum, because they are greater than f (q) and f (s), respectively.Thus the minimum is in the interior of the interval, it is a local minimum. So each non-empty interval (x − α, x + α) ⊂ [0, 1] contains at least one local minimum. Problem 3. Let p(z) be a polynomial of degree n with complex coefficients. Provethat there exist at least n + 1 complex numbers z for which p(z) is 0 or 1. Solution. The statement is not true if p is a constant polynomial. We prove it onlyin the case if n is positive. For an arbitrary polynomial q(z) and complex number c, denote by µ(q, c) the largestexponent α for which q(z) is divisible by (z − c)α . (With other words, if c is a root of q,then µ(q, c) is the root’s multiplicity. Otherwise 0.) 1 Den ...