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

Tham khảo tài liệu đề thi olympic sinh viên thế giới năm 2008, khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Đề thi Olympic sinh viên thế giới năm 2008 nProblem 6. For a permutation σ = (i1 , i2 , ..., in ) of (1, 2, ..., n) define D(σ) = |ik − k|. Let Q(n, d) be IMC2008, Blagoevgrad, Bulgaria k=1the number of permutations σ of (1, 2, ..., n) with d = D(σ). Prove that Q(n, d) is even for d ≥ 2n. Day 1, July 27, 2008Solution. Consider the n × n determinant 1 x . . . xn−1 x 1 . . . xn−2 Problem 1. Find all continuous functions f : R → R such that f (x) − f (y) is rational for all reals x and ∆(x) = . . . . .. . . . . . . y such that x − y is rational. xn−1 xn−2 ... 1 Solution. We prove that f (x) = ax + b where a ∈ Q and b ∈ R. These functions obviously satify the conditions.where the ij-th entry is x|i−j| . From the definition of the determinant we get Suppose that a function f (x) fulfills the required properties. For an arbitrary rational q, consider the function gq (x) = f (x+ q) −f (x). This is a continuous function which attains only rational values, therefore ∆(x) = (−1)inv(i1 ,...,in) xD(i1 ,...,in) gq is constant. (i1 ,...,in)∈Sn Set a = f (1) − f (0) and b = f (0). Let n be an arbitrary positive integer and let r = f (1/n) − f (0). Since f (x + 1/n) − f (x) = f (1/n) − f (0) = r for all x, we havewhere Sn is the set of all permutations of (1, 2, ..., n) and inv(i1 , ..., in ) denotes the number of inversions inthe sequence (i1 , ..., in ). So Q(n, d) has the same parity as the coefficient of xd in ∆(x). f (k/n) − f (0) = (f (1/n) − f (0)) + (f (2/n) − f (1/n)) + . . . + (f (k/n) − f ((k − 1)/n) = kr It remains to evaluate ∆(x). In order to eliminate the entries below the diagonal, subtract the (n−1)-throw, multiplied by x, from the n-th row. Then subtract the (n − 2)-th row, multiplied by x, from the and(n − 1)-th and so on. Finally, subtract the first row, multiplied by x, from the second row. f (−k/n) − f (0) = −(f (0) − f (−1/n)) − (f (−1/n) − f (−2/n)) − . . . − (f (−(k − 1)/n) − f (−k/n) = −kr 1 x . . . xn−2 xn−1 1 x ... xn−2 xn−1 x 1 . . . xn−3 xn−2 0 1 − x2 . . . xn−3 − xn−1 xn−2 − xn for k ≥ 1. In the case k = n we get a = f (1) − f (0) = nr, so r = a/n. Hence, f (k/n) − f (0) = kr = ak/n ∆(x) = . . . . .. . . . = ... = . . . . . .. . . . . = (1 − x2 )n−1 . and then f (k/n) = a · k/n + b for all integers k and n > 0. . . . . . . . . . ...