tailieunhanh - International Mathematical Olympiad 2011 - IMC2011 day 2

International math Olympiad students in is a great playground for the world's students have the opportunity to meet, exchange, communicate and demonstrate the ability to learn math. | IMC2011 Blagoevgrad Bulgaria Day 2 July 31 2011 Problem 1. Let an n 0 be a sequence with 2 an 1 for all n 0. Define the sequence xn n 0 by _ an 1 xn n xo ao Xn 1 . n 0 . 1 an 1xn What are the possible values of lim xn Can such a sequence diverge n tt Johnson Olaleru Lagos Solution 1. We prove by induction that 1 0 1 Xn .L. . I . n 2n 1 Then we will have 1 xn 0 and therefore xn 1. The case n 0 is true since 1 x0 a0 1. Supposing that the induction hypothesis holds for n from the recurrence relation we get 1 1 an 1 xn 1 an 1 _ X 1 xn 1 1 7 ---- 7 ---- 1 xn . 1 an 1xn 1 an 1 xn By 1 0 1 an 1 1 2 1 1 an 1xn 1 0 2 we obtain 1 1 1 1 0 1 xn 1 7 1 xn 77 I o . n 1 2 n 2 2n 1 2n 2 Hence the sequence converges in all cases and xn 1. Solution 2. As is well-known . tanh u tanhv tanh u v - 1 tanh u tanh v for all real numbers u and v . Setting un ar tanh an we have xn tanh u0 u1 un . Then u0 u1 un n 1 ar tanh 2 and lim xn lim tanh u 1. n u x Remark. If the condition an E 1 1 is replaced by an E 0 1 then the sequence remains increasing and bounded but the limit can be less than 1. Problem 2. An alien race has three genders male female and emale. A married triple consists of three persons one from each gender who all like each other. Any person is allowed to belong to at most one married triple. A special feature of this race is that feelings are always mutual if x likes y then y likes x. The race is sending an expedition to colonize a planet. The expedition has n males n females and n emales. It is known that every expedition member likes at least k persons of each of the two other genders. The problem is to create as many married triples as possible to produce healthy offspring so the colony could grow and prosper. a Show that if n is even and k n then it might be impossible to create even one married triple. b Show that if k 3n then it is always possible to create n disjoint married triples thus marrying all of the expedition members. Fedor Duzhin and Nick Gravin Singapore 1 .