Nội dung

51st International Mathematical Olympiad Astana, Kazakhstan 2010 Problems with Solutions Contents Problems Solutions Problem Problem Problem Problem Problem Problem 5 1 2 3 4 5 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 7 8 9 10 11 13 Problems Problem 1. Determine all functions f : R → R such that the equality ( ) ⌊ ⌋ f ⌊x⌋y = f (x) f (y) holds for all x, y ∈ R. (Here ⌊z⌋ denotes the greatest integer less than or equal to z.) Problem 2. Let I be the incentre of triangle ABC and let Γ be its circumcircle. Let the line AI \ and F a point on the side BC such that intersect Γ again at D. Let E be a point on the arc BDC ∠BAF = ∠CAE < 12 ∠BAC. Finally, let G be the midpoint of the segment IF . Prove that the lines DG and EI intersect on Γ. Problem 3. Let N be the set of positive integers. Determine all functions g : N → N such that ( )( ) g(m) + n m + g(n) is a perfect square for all m, n ∈ N. Problem 4. Let P be a point inside the triangle ABC. The lines AP , BP and CP intersect the circumcircle Γ of triangle ABC again at the points K, L and M respectively. The tangent to Γ at C intersects the line AB at S. Suppose that SC = SP . Prove that M K = M L. Problem 5. In each of six boxes B1 , B2 , B3 , B4 , B5 , B6 there is initially one coin. There are two types of operation allowed: Type 1: Choose a nonempty box Bj with 1 ≤ j ≤ 5. Remove one coin from Bj and add two coins to Bj+1 . Type 2: Choose a nonempty box Bk with 1 ≤ k ≤ 4. Remove one coin from Bk and exchange the contents of (possibly empty) boxes Bk+1 and Bk+2 . Determine whether there is a finite sequence of such operations that results in boxes B1 , B2 , B3 , B4 , B5 2010 c c being empty and box B6 containing exactly 20102010 coins. (Note that ab = a(b ) .) Problem 6. Let a1 , a2 , a3 , . . . be a sequence of positive real numbers. Suppose that for some positive integer s, we have an = max{ak + an−k | 1 ≤ k ≤ n − 1} for all n > s. Prove that there exist positive integers ℓ and N , with ℓ ≤ s and such that an = aℓ +an−ℓ for all n ≥ N . 6 Solutions Problem 1. Determine all functions f : R → R such that the equality ( ) ⌊ ⌋ f ⌊x⌋y = f (x) f (y) (1) holds for all x, y ∈ R. (Here ⌊z⌋ denotes the greatest integer less than or equal to z.) Answer. f (x) = const = C, where C = 0 or 1 ≤ C < 2. Solution 1. First, setting x = 0 in (1) we get f (0) = f (0)⌊f (y)⌋ (2) for all y ∈ R. Now, two cases are possible. Case 1. Assume that f (0) ̸= 0. Then from (2) we conclude that ⌊f (y)⌋ = 1 for all y ∈ R. Therefore, equation (1) becomes f (⌊x⌋y) = f (x), and substituting y = 0 we have f (x) = f (0) = C ̸= 0. Finally, from ⌊f (y)⌋ = 1 = ⌊C⌋ we obtain that 1 ≤ C < 2. Case 2. Now we have f (0) = 0. Here we consider two subcases. Subcase 2a. Suppose that there exists 0 < α < 1 such that f (α) ̸= 0. Then setting x = α in (1) we obtain 0 = f (0) = f (α)⌊f (y)⌋ for all y ∈ R. Hence, ⌊f (y)⌋ = 0 for all y ∈ R. Finally, substituting x = 1 in (1) provides f (y) = 0 for all y ∈ R, thus contradicting the condition f (α) ̸= 0. Subcase 2b. Conversely, we have f (α) = 0 for all 0 ≤ α < 1. Consider any real z; there exists an z integer N such that α = ∈ [0, 1) (one may set N = ⌊z⌋ + 1 if z ≥ 0 and N = ⌊z⌋ − 1 otherwise). N Now, from (1) we get f (z) = f (⌊N ⌋α) = f (N )⌊f (α)⌋ = 0 for all z ∈ R. Finally, a straightforward check shows that all the obtained functions satisfy (1). Solution 2. Assume that ⌊f (y)⌋ = 0 for some y; then the substitution x = 1 provides f (y) = f (1)⌊f (y)⌋ = 0. Hence, if ⌊f (y)⌋ = 0 for all y, then f (y) = 0 for all y. This function obviously satisfies the problem conditions. So we are left to consider the case when ⌊f (a)⌋ ̸= 0 for some a. Then we have f (⌊x⌋a) = f (x)⌊f (a)⌋, or f (x) = f (⌊x⌋a) . ⌊f (a)⌋ (3) This means that f (x1 ) = f (x2 ) whenever ⌊x1 ⌋ = ⌊x2 ⌋, hence f (x) = f (⌊x⌋), and we may assume that a is an integer. Now we have ) ⌊ ( )⌋ ( f (a) = f 2a · 12 = f (2a) f 12 = f (2a)⌊f (0)⌋; this implies ⌊f (0)⌋ ̸= 0, so we may even assume that a = 0. Therefore equation (3) provides f (x) = f (0) = C ̸= 0 ⌊f (0)⌋ 8 for each x. Now, condition (1) becomes equivalent to the equation C = C⌊C⌋ which holds exactly when ⌊C⌋ = 1. Problem 2. Let I be the incentre of triangle ABC and let Γ be its circumcircle. Let the line AI \ and F a point on the side BC such that intersect Γ again at D. Let E be a point on the arc BDC ∠BAF = ∠CAE < 12 ∠BAC. Finally, let G be the midpoint of the segment IF . Prove that the lines DG and EI intersect on Γ. Solution 1. Let X be the second point of intersection of line EI with Γ, and L be the foot of the bisector of angle BAC. Let G′ and T be the points of intersection of segment DX with lines IF and AF , respectively. We are to prove that G = G′ , or IG′ = G′ F . By the Menelaus theorem applied to triangle AIF and line DX, it means that we need the relation G′ F T F AD TF ID = · , or = . ′ IG AT ID AT AD Let the line AF intersect Γ at point K ̸= A (see Fig. 1); since ∠BAK = ∠CAE we have d d hence KE ∥ BC. Notice that ∠IAT = ∠DAK = ∠EAD = ∠EXD = ∠IXT , so BK = CE, the points I, A, X, T are concyclic. Hence we have ∠IT A = ∠IXA = ∠EXA = ∠EKA, so IL TF = . IT ∥ KE ∥ BC. Therefore we obtain AT AI IL CL Since CI is the bisector of ∠ACL, we get = . Furthermore, ∠DCL = ∠DCB = AI AC ∠DAB = ∠CAD = 12 ∠BAC, hence the triangles DCL and DAC are similar; therefore we get CL DC = . Finally, it is known that the midpoint D of arc BC is equidistant from points I, B, C, AC AD DC ID hence = . AD AD Summarizing all these equalities, we get TF IL CL DC ID = = = = , AT AI AC AD AD as desired. 1= X A A I B III TTT C G′ D F B L K C E D Fig. 1 J Fig. 2 9 AI AD = is known and can be obtained in many different ways. For instance, IL DI \ to the one can consider the inversion with center D and radius DC = DI. This inversion takes BAC IL AI segment BC, so point A goes to L. Hence = , which is the desired equality. DI AD Comment. The equality Solution 2. As in the previous solution, we introduce the points X, T and K and note that it suffice to prove the equality TF DI T F + AT DI + AD AT AF = ⇐⇒ = ⇐⇒ = . AT AD AT AD AD DI + AD Since ∠F AD = ∠EAI and ∠T DA = ∠XDA = ∠XEA = ∠IEA, we get that the triangles AT D AT AI and AIE are similar, therefore = . AD AE Next, we also use the relation DB = DC = DI. Let J be the point on the extension of segment AD over point D such that DJ = DI = DC (see Fig. 2). Then ∠DJC = ∠JCD = 1 (π − ∠JDC) = 12 ∠ADC = 12 ∠ABC = ∠ABI. Moreover, ∠BAI = ∠JAC, hence triangles ABI 2 AB AI and AJC are similar, so = , or AB · AC = AJ · AI = (DI + AD) · AI. AJ AC On the other hand, we get ∠ABF = ∠ABC = ∠AEC and ∠BAF = ∠CAE, so triangles ABF AB AF and AEC are also similar, which implies = , or AB · AC = AF · AE. AC AE Summarizing we get AI AF AT AF (DI + AD) · AI = AB · AC = AF · AE ⇒ = ⇒ = , AE AD + DI AD AD + DI as desired. Comment. In fact, point J is an excenter of triangle ABC. Problem 3. Let N be the set of positive integers. Determine all functions g : N → N such that ( )( ) g(m) + n m + g(n) is a perfect square for all m, n ∈ N. Answer. All functions of the form g(n) = n + c, where c ∈ N ∪ {0}. Solution. First, it is clear that all functions of nonnegative ( the form)(g(n) = n + ) c with a constant 2 integer c satisfy the problem conditions since g(m) + n g(n) + m = (n + m + c) is a square. We are left to prove that there are no other functions. We start with the following Lemma. Suppose that p g(k) − g(ℓ) for some prime p and positive integers k, ℓ. Then p k − ℓ. Proof. Suppose first that p2 g(k) − g(ℓ), so g(ℓ) = g(k) + p2 a for some integer a. Take some positive integer D > max{g(k), g(ℓ)} which is not divisible by p and ( ) set n = pD − g(k). Then the positive numbers n + g(k) = pD and n + g(ℓ) = pD + g(ℓ) − g(k) = p(D + pa) are both ( divisible )( by p but) 2 not by p . Now, applying the problem conditions, we get that both the numbers g(k) + n g(n) + k ( )( ) 2 and g(ℓ) + n g(n) + ℓ are squares divisible by p (and thus ( by p );)this( means that ) the multipliers g(n) + k and g(n) + ℓ are also divisible by p, therefore p g(n) + k − g(n) + ℓ = k − ℓ as well. On the other hand, if g(k)−g(ℓ) is divisible by p but not by p2 , then choose the same ( number D)and 3 3 3 set n = p D −g(k). Then the positive numbers g(k)+n = p D and g(ℓ)+n = p D + g(ℓ)−g(k) are respectively divisible by p3 (but not by p4 ) and by p (but not by p2 ). Hence ( in analogous ) ( way we ) obtain that the numbers g(n) + k and g(n) + ℓ are divisible by p, therefore p g(n) + k − g(n) + ℓ = k − ℓ.  10 We turn to the problem. First, suppose that g(k) = g(ℓ) for some k, ℓ ∈ N. Then by Lemma we have that k − ℓ is divisible by every prime number, so k − ℓ = 0, or k = ℓ. Therefore, the function g is injective. Next, consider the numbers g(k) and g(k + 1). Since the number (k + 1) − k = 1 has no prime divisors, by Lemma the same holds for g(k + 1) − g(k); thus |g(k + 1) − g(k)| = 1. Now, let g(2) − g(1) = q, |q| = 1. Then we prove by induction that g(n) = g(1) + q(n − 1). The base for n = 1, 2 holds by the definition of q. For the step, if n > 1 we have g(n + 1) = g(n) ± q = g(1) + q(n − 1) ± q. Since g(n) ̸= g(n − 2) = g(1) + q(n − 2), we get g(n) = g(1) + qn, as desired. Finally, we have g(n) = g(1) + q(n − 1). Then q cannot be −1 since otherwise for n ≥ g(1) + 1 we have g(n) ≤ 0 which is impossible. Hence q = 1 and g(n) = (g(1) − 1) + n for each n ∈ N, and g(1) − 1 ≥ 0, as desired. Problem 4. Let P be a point inside the triangle ABC. The lines AP , BP and CP intersect the circumcircle Γ of triangle ABC again at the points K, L and M respectively. The tangent to Γ at C intersects the line AB at S. Suppose that SC = SP . Prove that M K = M L. Solution 1. We assume that CA > CB, so point S lies on the ray AB. PM PA From the similar triangles △P KM ∼ △P CA and △P LM ∼ △P CB we get = and KM CA LM CB = . Multiplying these two equalities, we get PM PB LM CB P A = · . KM CA P B CB PB = . CA PA Denote by E the foot of the bisector of angle B in triangle ABC. Recall that the locus of points X XA CA for which = is the Apollonius circle Ω with the center Q on the line AB, and this circle XB CB passes through C and E. Hence, we have M K = M L if and only if P lies on Ω, that is QP = QC. Hence, the relation M K = M L is equivalent to Ω L C C C K P P P S A E B M Fig. 1