From hip-hop!benjie@amdahl.com Sun Feb 27 11:35:00 1994 From: Pertsel Vladimir Subject: Russian mathematical competitions (part 1) I have already posted this stuff in a number of articles in rec.puzzles. The responses I have got concerned mainly the educational, not the recreational side of those competitions, so I have decided to post this material here, having provided it with the answers on the common questions. ==================collected articles start====================== I'm going to send some problems from the book Vasil'ev N.B, Egorov A.A. "The problems of the All-Soviet-Union mathematical competitions",-Moscow.:Nauka. 1988 ISBN 5-02-013730-8. (in Russian). Those problems were submitted for the solving on the competition between the pupils of 8, 9, or 10 forms for 4 hours. So they do not contain something of the advanced topics, -- all of them can be solved by a schoolboy. They can not go out of the common school plan bounds. Most of the problems are original and the book contains all the necessary references. I am not going to translate all the book, so I shall not send the solutions. Please, accept those messages as they are, to say more exactly -- as I can. I have to do my job, and this is hobby only, but nevertheless, that should be enjoyable to solve those problems. And, maybe, there will be somebody, that will translate all the book with the solutions or one of the following wonderful books: "Problems of the Moscow mathematical competitions",-compiled by G.A.Galperin, A.K.Tolpygo.,-Moscow, Prosveshchenie, 1986. A.A.Leman "Collection of Moscow mathematical competitions problems" ,-Moscow, Prosveshchenie, 1965. I, myself, for example is interested in the problems of the Hungarian mathematical competitions --- they have achieved terrific results. Or, maybe, somebody from the Russia will send something new from the QUANT (quantum) journal, especially from the "QUANT for the JUNIORS" page. The things are simple, but tricky. "Nobody can embrace the unembraceable" Kozma Prutkov. (beginning of the XIX c.) ==============answers on the common questions============ WHAT IS THE AGE OF THE PARTICIPANTS? The Russian pupils start studying being 6-7 years old, so the pupils of the 8th form are about 14. WHO PARTICIPATE? The competition helds in 3 - 4 stages 1. At school - if there are many volunteers. 2. Subregional - if the region is big enough. 3. Regional (in some regions, as in Moscow, Leningrad=Sankt-Peterburg, Sverdlovsk=Ekaterinburg or Novosibirsk they are even more interesting and more difficult) 4. Final part, considered in the report. WHAT A THE BEST AND AVERAGE RESULTS? The winners (2-5) usually give the perfect solution of all the problems with some shortages. My personal experience refers to that times, when there were two days of the final competition. Than the winners solved all the problems of two days except one problem. It is very difficult to speak about the average level, because it depends very much on a region, but most of the participants of that time solved at least one problem. The problem is not only the difficulties in the problems themselves, but also in the shortage of time. They successfully solved the problems before the official explanation two days later. MAY I USE THOSE PROBLEMS IN THE SCHOOL PROJECTS? You don't need MY permission for using those problems. As concerns the copyright, the usage of all the information in the non-commercial purposes was never restricted in Russia if it is not related to the state security. Moreover, the spirit of the competition encourages everybody to distribute those problems in order to enhance the mathematical culture of the pupils. ============collected articles continue================== So... First one -- Moscow, 1961. form 8 001 002 003 004 005a 9 006a 007 008 009 010 10 011 012 007 006b 005b 001. Given a figure, containing of 16 segments. +-------------+--------------+ | | | | | | +-------+-----+----+---------+ | | | | | | | | +----------------------------+ You should prove that there is no curve, that intersect each segment exactly once. The curve may be not closed, may intersect itself, but it is not allowed to touch the segments or to come through the vertices. 002. Given a rectangle A_1 A_2 A_3 A_4 Four circles with A_i as a centres have their radiuses r_1,r_2,r_3,r_4, and r_1 + r_3 = r_2 + r_4 < d, where d is a diagonal of the rectangle. Two pairs of the outer common tangents to {the first and the third} and {the second and the fourth} circumferences make a quadrangle. Prove, that You can inscribe a circle into that quadrangle. 003. Prove, that among 39 successive natural numbers there always is such a one, that the sum of its digits divides by 11. 004. Given a table 4x4. a) Find, how 7 stars can be put in its squares in such a way, that erasing of two arbitrary lines and two columns will always leave at list one of the stars. b)Prove, that if there are less than 7 stars, You can always find two columns and two rows, that if You erase them, no star will remain in th table. 005. a) Given 4 positive numbers. (a,b,c,d). It is transformed to the new one according to the rule: a'=ab; b' =bc; c'=cd; d' =da. The second one is transformed to the third according to the same rule and so on. Prove, that if at least one initial number does not equal to 1, than You can never obtain the initial set. b) Given a set of 2**k (k-th power of two) numbers, equal either to 1 or to -1. It is transformed as that was in the a) problem (each one is multiplied by the next, and the last -- by the first. Prove, that You will always finally obtain the set of positive units. 006. a) Points A and B move uniformly and with equal angle speed on the circumferences with the centres O_a and O_b (both clockwise). Prove, that a vertex C of the right triangle ABC also moves on a certain circumference uniformly. b) The distance from the point P to the vertices of the right triangle ABC equal AP=2, BP=3. Find the maximal value of CP. 007. Given m to n table, and some numbers in its squares. You are allowed to change the sign in one row or one column simultaneously. Prove, that You can obtain a table, with nonnegative sums over each row and over each column. 008. Given n points connected by nonintersecting segments. You can reach every point from every one, moving through(?) the segments, and there is no couple, connected by two different ways. Prove, that the total number of the segments is (n-1). 009. Given a,b,p -arbitrary integers. Prove, that there always exist relatively prime (i.e. that have no common divisor) k and l, that (ak + bl) is dividable by p. 010. Nickolas and Peter are dividing (2n+1) nuts. Each one want to get more. Three ways for that were suggested. (Each consist of three stages). First two stages are common. --------- 1 stage: Peter divides nuts onto 2 heaps, each contain not less than 2 nuts. --------- 2 stage: Nickolas divides both heaps onto 2 heaps, each contain not less than 1 nut --------- 3 stage: ---------------- 1 way: Nickolas takes the biggest and the least heaps. ---------------- 2 way: Nickolas takes two middle size heaps. ---------------- 3 way: Nickolas takes either the biggest and the least heaps or two middle size heaps, but gives for the right of choice one nut to the Peter. ---------------- Find what is the most and the least profitable method for the Nickolas. 011. Prove, that for the three arbitrary infinite sequences a_1, a_2, ... , a_n, ... b_1, b_2, ... , b_n, ... c_1, c_2, ... , c_n, ... there exist such a numbers p and q such, that a_p >= a_q; b_p >= b_q and c_p >= c_q. 012. In the rectangle 20x25 are arbitraryly situated 120 unit squares. Prove, that You can place a circle with its diameter equal to one without intersecting any of the squares. The second competition -- Moscow, 1962. form 8 013 014 015 016 017 9 018 019 020 021 017 10 022 023 024 025 026 013. On the continuation of the sides [AB],[BC],[CD],[DA] of the convex quadrangle ABCD given points A',B',C',D' such, that \vec{BB'}=\vec{AB},\vec{CC'}=\vec{BC},\vec{DD'}=\vec{CD}, \vec{AA'}=\vec{DA}. Prove that the square of the quadrangle A'B'C'D' is five times more than of the quadrangle ABCD. 014. Given the circumference s and the straight line l, passing through the cenre O of s. Another circumference s' passes through the point O and has its centre on the l. Describe the set of the points M, where the common tangent of s and s' touches s'. 015. Given positive numbers a_1, a_2, ..., a_99, a_100. It is known, that a_1 > a_0; a_2 = 3a_1 - 2a_0, a_3 = 3a_2 - 2a_1, ..., a_100 = 3a_99 - 2a _98. Prove, that a_100 > 2**99. 016. Prove, that there are no integers a,b,c,d such that the polinom ax**3 + bx**2 + cx + d equals to 1 at the point x=19, and equals to 2 at x=62. 017. Given a table nxn, where n is odd. There is either 1 or -1 in its every square. Under all of the columns is written a product of the numbers in that column. To the right of every row is written a product of the numbers in that row. Prove, that the sum of 2n products doesn't equal to 0. 018. Given two sides of the triangle. Build that triangle, if medians to those sides are ortogonal. 019. Given positive numbers a,b,c,d, and is known, that their product equals to 1. Prove that a**2 + b**2 + c**2 + d**2 + ab + ac + ad + bc + bd + dc >= 10 020. Given right pentagon ABCDE. M is an arbitrary point inside ABCDE or on its side. Let the distances |MA|, |MB|, ... are renumerated and denoted with r_1 <= r_2 <= r_3 <= r_4 <= r_5. Find all the positions of the M, giving the minimal possible value. Find all the positions of the M, giving the maximal possible value. 021. Given 1962 -digit number. It is dividable by 9. Let a be the sum of its digits. Let the sum of the digits of a be b. Let the sum of the digits of b be c. Find c. 022. A perpendicular MH is drawn from the M - middle of the base of isosceles (equilateral?) triangle to the side BC. Point P is the middle of the segment MH. Prove that AH is ortogonal to BP 023. What maximal square can have a triangle if its sides a,b,c satisfy unequality 0 <= a <= 1 <= b <= 2 <= c <= 3? 024. Given x,y,z, three different integers. Prove that ( (x-y)**5 + (y-z)**5 + (z-x)**5 ) is dividable by 5(x-y)(y-z)(z-x). 025. Given a_0, a_1, ... , a_n. It is known that a_1 = a_n = 0; a_{k-1} - 2a_k + a_{k+1} >=0 at all k = 1, 2, ... , k-1. Prove that all the numbers are nonnegative. 026. Given positive numbers a_1, a_2, ..., a_m; b_1, b_2, ..., b_n; and is known that a_1 + a_2 + ... + a_m = b_1 + b_2 + ... + b_n. Prove, that You can fill an empty table with m rows and n columns with no more than (m+n-1) positive number in such a way, that for all i,j the sum of the numbers in the i-th row will equal to a_i, and the sum in the numbers in the j-th column --- to b_j. The third competition -- Moscow, 1963. form 8 027 028 029a 030 031a 9 032 033 034 031b 028 10 035 036 037 029b 028 11 038 028 039 040 029b 027. Given 5 circumferences. It is known, that every four of them have a common point. Prove, that there exist a point that belong to all five. 028. Eight men had participated in the chess tournament. (Each meets each; draws are allowed, giving 1/2 of pont; winner gets 1.) Everyone has different number of points. The second one got as many points as the the four weakest together. What was the result of the play between the third prizer and the chessplayer that have occupied the seventh place? 029. a) Both diagonals of the quadrangle halves its area. Prove, that it is a parallelogram. b) Three main diagonals of the hexagon halves its area. Prove, that they intersect in one point. 030. Natural numbers a and b are relatively prime. Prove that the greatest common divisor of (a+b) and (a**2+b**2) is either 1 or 2. 031. Given two fixed points A and B .The point M runs along the circumference containing A and B. K is the middle of the segment [MB]. [KP] is a perpendicular to the line (MA). a) Prove that all the possible lines (KP) pass through one point. b) Find the set of all the possible points P. 032. Given right triangle with the side l. What is the minimal length d of a brush (segment), that will paint all the triangle, moving with its ends on the sides of the triangle. 033. A chessboard 6x6 is tiled with the 2x1 dominoes. Prove, that You can cut the board onto two parts with a straight line that does not cut dominoes. 034. Given n different positive numbers a_1, a_2, ... , a_n. We construct all the possible sums (from 1 to n terms). Prove, that there are at least n(n+1)/2 different among those sums. 035. Given a triangle ABC. We build two angle bisectors in the corners A and B. Than we build two lines parallel to those _ones_ through the point C. D and E are intersections of those lines with those _ones_. DE is parallel to AB. Prove, that the triangle is isosceles. 036. Given the endless arithmetic progression with the positive integer members. One of those is an exact square. Prove, that the progression contain the infinite number of the exact squares. 037. Given right 45-angle. Can You mark its corners with the digits {0,1,...,9} in such a way, that for every pair of digits there would be a side with both ends marked with those digits? 038. Find such real p,q,a,b, that equality (2x-1)**20 - (ax+b)**20 = (x**2+px+q)**10 helds for all x. 039. On the ends of the diameter are drawn _1_s. Each of the semicircles is divided onto two parts and the sum of the numbers of its ends (i.e. 2) is drawn at the point. Then every of the four arcs is halved and in its middle is drawn the sum of the numbers on the ends. Find the total sum of the numbers on the circumference after n steps. 040. Given an isosceles triangle. Find the set of the points inside the triangle such that the distance from that point to the base equals to the geometric mean of the distances to the sides. The fifth competition -- Moscow, 1965. form 8 056a 057 058 059 060 9 061 062 063 064 065 10 056b 066 067a 068a 069 11 063 067b 070 068b 071 056. a) Each of the numbers x_1, x_2, ... ,x_n can be 1, 0, or -1. What is the minimal possible value of the sum of all products of couples of those numbers. b) Each absolute value of the numbers x_1, x_2, ... ,x_n is less than 1. What is the minimal possible value of the sum of all products of couples of those numbers. 057. Given a board 3x3 and 9 cards with some numbers (known to the players). Two players consequently put those cards on the board. The first wins if the sum of the numbers in the first and the third row is greater than in the first and the third column. Prove that it doesn't matter what numbers are on the cards, but if the first plays the best way, the second can not win. 058. A circle is outscribed around the triangle ABC. Chords, from the middle of the arc AC to the middles of the arcs AB and BC intersect sides [AB] and [BC] in the points D and E. Prove that (DE) is parallel to (AC) and goes through the centre of the inscribed circle. 059. A bus ticket is considered to be lucky if the sum of the first three digits equals to the sum of the last three (6 digits total in Russian busses). Prove that the sum of all the lucky numbers is dividable by 13. 060. There is a lighthouse on a small island. Its lamp enlights a segment of a sea to the distance a. The light is turning uniformly, and the end of the segment moves with the speed v. Prove that a ship, whose speed doesn't exceed v/8 cannot arrive to the island without being enlightened. 061. A society created in the help to the police contains 100 man exactly. Every evening 3 men are on duty. Prove, that You can not organize duties in such a way, that every couple will meet on duty once exactly. 062. What is the maximal possible length of the segment, being cut out by the sides of the triangle on the tangent to the inscribed circle, being drawn parallel to the base, if the triangle's perimeter equals to 2p? 063. Given n**2 numbers x_{i,j} (i,j = 1,2,...,n) satisfying the system of n**3 equations x_{i,j} + x_{j,k} + x{k,i} = 0 (i,j,k = 1,...,n). Prove, that there exist such a numbers a_1, a_2, ... , a_n; that for all i,j = 1,...n x{i,j}= a_i - a_j. 064. Is it possible to pose 1965 points inside the unit square to make every rectangle with the square 0.005 and sides parallel to the side of the square to contain at least one of those points? 065. Quasirounding is a substitution one of the two closest integers instead of the given number. Given n numbers. Prove, that You can quasiround them in such a way, that a sum of every subset of quasirounded numbers will deviate from the sum of the same subset of initial numbers less than (n+1)/4. 066. The tourist has come to the Moscow by train. All-day-long he wandered randomly through the streets. Than he had a supper in the caffee on the square and decided to return to the station only through the streets that he has passed an odd number of times. Prove that he is always able to do that. 067. a) A certain committee has gathered 40 times. There were 10 members on the every meeting. Not a single couple has met on the meetings twice. Prove that there were no less then 60 members in the committee. b) Prove, that You can not construct more then 30 subcommittees of 5 members from the committee of 25 members, with no couple of subcommittees having more than one common member. 068. Given two relatively prime numbers p>0 and q>0. An integer n is called "good" if we can represent it as n = px + qy with nonnegative integers x and y, and "bad" in the opposite case. a) Prove that there exist integer c such that in a pair {n, c-n} always one is "good" and one is "bad" b) How many there exist "bad" numbers. 069. An airplane-spy flies on the circumference with the centre A ant radius 10 km. Its speed is 1000 km/h. At the certain moment a rocket with the same speed starts from the point A and moves remaining on one line with the plain and A. What time is necessary for it to hit the plane? /* remember, no advanced math. were known to the participants -VAP */ 070. Prove that the sum of the lengths of the polyhedron edges exceeds its tripled diameter (distance between two farest vertices). 071. On the surface of the planet lives one inhabitant, that can move with the speed not greater than u. A spaceship approaches to the planet wit its speed v. Prove that if v/u > 10 , the spaceship can find the inhabitant, even it is trying to hide. The sixth competition -- Voronezh, 1966. form 8 072 073a 074 075a 076 9 077 073b 075b 078 079 10,11 075b 080 081 082 083 072. There is exactly one astronomer on every planet of a certain system. He watches the closest planet. The number of the planets is odd and all of the distances are different. Prove that there one planet being not watched. 073. a) Points B and C are inside the segment [AD]. |AB|=|CD|. Prove that for all of the points P on the plane holds unequality |PA|+|PD| > |PB|+|PC|. b) Given four points A,B,C,D on the plane. For all of the points P on the plane holds unequality |PA|+|PD| > |PB|+|PC|. Prove, that points B and C are inside the segment [AD] and |AB|=|CD|. 074. Answer, if there exist a pair of natural x and y such that both (x**2+y) and (y**2+x) are exact squares. 075. a) Pupils of the 8-th form are standing in a row. There is the pupil of the 7-th form in before each, and he is smaller (in height) than the elder. Prove, that if You will sort the pupils in each of rows with respect to their height, every 8-former will still be taller than the 7-former standing before him. b) An infantry detachment soldiers stand in the rectangle, being arranged in columns with respect to their height. Prove, that if You rearrange them with respect to their height in every separate row, they will still be staying with respect to their height in columns. 076. A rectangle ABCD is drawn on the cross-lined paper with its sides laying on the lines, and |AD| is k times more than |AB| (k is an integer). All the shortest paths from A to C coming along the lines are considered. Prove, that the number of those with the first link on [AD] is k times more then of those with the first link on [AB]. 077. Given the numbers a_1, a_2, ... , a_n, such that held 0 <= a_1 <= a_2 <= 2a_1, a_2 <= a_3 <= 2a_2, ... , a_{n-1} <= a_n <= 2a_{n-1}, Prove that in the sum s = +-a_1 +-a_2 +- ... +- a_n You can choose appropriate signs to make 0 <= s <= a_1. 078. Prove that You can always pose a circle of radius S/P inside a convex polygon with the perimeter P and square S. 079. For three arbitrary crossroads A,B,C in a certain city there exist a way from A to B not coming through C. Prove that for every couple of the crossroads there exist at least two non-intersecting ways connecting them. (there are at least two crossroads in the city) 080. Given a triangle ABC. Consider all the tetrahedrons PABC with PH -- the smallest of all its heights. Describe the set of all possible points P. 081. Given 100 points on the plain. Prove that You can cover them with a family of circles with the sum of their diameters less than 100 and the distance between any two of the circles more than one. 082. The distance from A to B is d kilometers. A plain flying with the constant speed in the constant direction along and over the line (AB) is being watched from those points. Observers have reported that the angle to the plain from the point A has changed for \alpha degrees and from B --- for \betha degrees within one second. What can be the minimal speed of the plain? 083. 20 Numbers are written on the board: 1, 2, ... ,20. Two players are putting signs before the numbers in turn (+ or -). The first wants to obtain the minimal possible absolute value of the sum. What is the maximal value of the absolute value of the sum that can be achieved by the second player? "Where is the beginning of that end, that ends the beginning?" Kozma Prutkov. "If You see a title 'buffalo' on the elephant's cage -- don't believe to Your eyes!" Kozma Prutkov. The name has been changed -- the numeration was resumed. The first competition -- Tbilisi, 1967. form 8 084a 085a 086a 087 088 9 087b 086a 085b 084b 088 10 090 086b 091 092 093 084. a) The maximal height AH of the acute-angled triangle ABC equals to the median BM. Prove that the angle ABC is not greater than 60 degrees. b) The height AH of the acute-angled triangle ABC equals to the median BM and to the angle bisector CD. Prove that the angle ABC is right. 085. a) The digits of a natural number were rearranged. Prove that the sum of the given and obtained numbers can not equal to 999...9 (1967 of nines). b) The digits of a natural number were rearranged. Prove that if the sum of the given and obtained numbers equals to {10}**{10}, than the given number was dividable by 10. 086. a) A lamp of a lighthouse enlights an angle of 90 degrees. Prove that You can turn the lamps of four arbitrary posed lighthouses so, that all the plane will enlighted. b) There are eight lamps in eight points of the space. Each can enlight an octant (three-faced space angle with three mutually orthogonal edges). Prove, that You can turn them so, that all the space will be enlighted. 087. a) Can You pose the numbers 0,1,...,9 on the circumference in such a way, that the difference between every two neighbours would be either 3 or 4 or 5? b) Can You pose the numbers 0,1,...,13 on the circumference in such a way, that the difference between every two neighbours would be either 3 or 4 or 5? 088. Prove that there exists a number dividable by 5**{1000} not containing a single zero in its decimal notation. 089. Find all the integers x,y satisfying equation x**2 + x = y**4 + y**3 + y**2 + y. 090. In the sequence of the natural (i.e. positive integers) numbers every member from the third equals the absolute value of the difference of the two previous. What is the maximal possible length of such a sequence, if every member is less or equal to 1967? 091. "KING-THE SUICIDER" Given a chessboard 1000x1000, 499 white castles and a black king. Prove that it does not matter neither the initial situation nor the way white plays, but the king can always move and stay under the check. 092. Three vertices KLM of the rhombus (diamond) KLMN lays on the sides [AB], [BC] and [CD] of the given unit square. Find the square of the set of all the possible vertices N. 093. Given natural number k with a property "if n is dividable by k, than the number, obtained from n by reversing the order of its digits is also dividable by k". Prove, that the k is a divisor of 99. The second competition -- Leningrad, 1968. form first day second day 8 094 095 096 097 098 | 105a 106 107 108 109 9 099 100 101 097 102 | 110 111 105a 108 109 10 103 095 104 097 096 | 105b 112 113 114 109 094. Given an octagon with the equal angles. The lengths of all the sides are integers. Prove that the opposite sides are equal in pairs. 095. What is more, {31}**{11} or {17}**{14}? /* calculators were not available - VAP */ 096. The circumference with the radius 100cm is drawn on the cross-lined paper with the side of the squares 1cm. It neither comes through the vertices of the squares, nor touches the lines. How many squares can it pass through? 097. Some students on the faculty speak several languages and some - Russian only. 50 of them know English, 50 -- French and 50 -- Spanish. Prove that it is possible to divide them onto 5 groups, not necessary equal, to get 10 of them knowing English, 10 -- French and 10 -- Spanish in each group. 098. Prove the equality 2 4 6 20 -------- + -------- + -------- + ... + --------- = x**2 - 1 x**2 - 4 x**2 - 9 x**2 - 100 1 1 1 = 11 ( ----------- + --------- + .... + ----------- ). (x-1)(x+10) (x-2)(x+9) (x-10)(x+1) 099. The difference between the maximal and the minimal diagonals of the right n-angle equals to its side ( n > 5 ). Find n. 100. The sequence a_1, a_2, a_3, ... , is built according to the rule a_1 = 1, a_2 = a_1 + 1/a_1, ... , a_{n+1} = a_n + 1/a_n, ... Prove, that a_{100} > 100. 101. Given two acute-angled triangles ABC and A'B'C' with the points O and O' inside. Three pairs of the perpendiculars are drawn: OA_1 to the side BC, O'A'_1 to the side B'C', OB_1 to the side AC, O'B'_1 to the side A'C', OC_1 to the side AB, O'C'_1 to the side A'B'; it is known that OA_1 is parallel to the O'A', OB_1 is parallel to the O'B', OC_1 is parallel to the O'C' and |OA_1|*|O'A'| = |OB_1|*|O'B'| = |OC_1|*|O'C'|. Prove that O'A'_1 is parallel to the OA, O'B'_1 is parallel to the OB, O'C'_1 is parallel to the OC and |O'A'_1|*|OA| = |O'B'_1|*|OB| = |O'C'_1|*|OC|. 102. Prove that You can represent an arbitrary number not exceeding n! (n-factorial; n!= 1*2*3*...*n) as a sum of k different numbers (k<=n) that are divisors of n!. 103. Given a triangle ABC, point D on [AB], E on [AC]; |AD| = |DE| = |AC| , |BD| = |AE| , DE is parallel to BC. Prove that the length |BD| equals to the side of a right decagon (ten-angle) inscribed in a circle with the radius R=|AC|. 104. Three spheres are built on the edges AB, BC, AD of the tetrahedron ABCD. Prove, that they cover all the tetrahedron. 105. a) +-----+-----+-----+-----+ | | | | | The fields of the square table | + | - | + | + | 4x4 are filled with the "+" or | | | | | "-" signs. You are allowed to +-----+-----+-----+-----+ change the signs simultaneously | | | | | in the whole row, column, or | + | + | + | + | diagonal to the opposite sign. | | | | | That means, for example, that You +-----+-----+-----+-----+ can change the sign in the corner | | | | | square, because it makes a diagonal | + | + | + | + | itself. | | | | | Prove that You will never manage +-----+-----+-----+-----+ to obtain a table containing | | | | | pluses only. | + | + | + | + | | | | | | +-----+-----+-----+-----+ b) The fields of the square table 8x8 are filled with the "+" or signs except one non-corner square with "-". You are allowed to change the signs simultaneously in the whole row, column, or diagonal to the opposite sign. That means, for example, that You can change the sign in the corner square, because it makes a diagonal itself. Prove that You will never manage to obtain a table containing pluses only. 106. Medians divide the triangle onto 6 smaller ones. 4 of the circles inscribed in those small ones are equal. Prove, that the triangle is right. 107. Prove, that the equation x**2 + x + 1 = py has solution (x,y) for the infinite number of simple p. 108. Each of the 9 referees on the figure skating championship estimates the program of 20 sportsmen by assigning him a place (from 1 to 20). The winner is determined by adding those numbers. (The less is the sum - the higher is the final place). It was found, that for the each sportsman, the difference of the places, received from the different referees was not greater than 3. What can be the maximal sum for the winner? 109. Two finite sequences a_1, a_2, ... , a_n; b_1, b_2, ... , b_n are just rearranged sequence 1, 1/2, ... , 1/n. a_1 + b_1 >= a_2 + b_2 >= ... >= a_n + b_n. Prove, that for every m ( 1 <= m <= n ) a_m + a_n >= 4/m. 110. There is scales on the teacher's table. There is a set of weights on the scales, and there are some pupils' names (may be more than one) on the every weight. A pupil entering the classroom moves all the weights with his name to another side of the scales. Prove that You can let in such a subset of the pupils, that the scales will change its position. 111. The city is a rectangle divided onto squares by m streets coming from the West to the East and n streets coming from the North to the South. There are militioners (policemen) on the streets but not on the crossroads. They watch the certain automobile, moving along the closed route, marking the time and the direction of its movement. Its trace is not known in advance, but they know, that it will not pass over the same segment of the way twice. What is the minimal number of the militioners providing the unique determination of the route according to their reports? 112. The circle inscribed in the triangle ABC touches the side [AC] in the point K. Prove, that the line connecting the middle of the [AC] side with the centre of the circle divides the segment [BK] onto two equal parts. 113. The sequence a_1, a_2, ... , a_n satisfies the following conditions: a_1 = 0, |a_2| = |a_1 + 1|, ... , |a_n| = |a_{n-1} + 1|. a_1 + a_2 + ... + a_n 1 Prove, that --------------------- >= - -. n 2 114. Given a quadrangle ABCD. The lengths of all its sides and diagonals are the rational numbers. Let O be the point of its diagonals intersection. Prove, that |AO| - the length of the [AO] segment is also rational. The third competition -- Kiev, 1969. form first day second day 8 115 116 117 | 122 123 124a 9 118 119 115 | 124 125 126 10 119 120 121 | 125 126 128 115. There is such a point E on the base AD of the trapezoid ABCD, that the perimeters of the triangles ABE, BCE and CDE are equal. Prove that |BC| = |AD|/2. 116. There is a wolf in the centre of a square field, and four dogs in the corners. The wolf can easyly kill one dog, but two dogs can kill the wolf. The wolf can run all over the field, and the dogs -- along the fence (border) only. Prove, that if the dog's speed is 1.5 times more than the wolf's, than the dogs can prohibit the wolf escaping. 117. Given a finite sequence of 0's and 1's with two properties: -- if you chose five sequential digits in one place and in the second place, those will be two different binary numbers. (Some last digits of the first number may be included as the first digits in the second.) -- if You add 0 or 1 either from the left or from the right side, the previous property will not be held. Prove that the first four digits of that sequence coincide with the last four. 118. Given positive numbers a,b,c,d. Prove that the set of unequalities a + b < c + d; (a + b)(c + d) < ab + cd; (a + b)cd < ab(c + d) contain at least one wrong. 119. What is the minimal natural a such that the polynomial ax**2 + bx + c with the integer c and b has two different positive roots both less than one. 120.Given natural n. Consider all the fractions 1/(pq), where p and q are relatively prime; 0 < p < q <= n; p+q > n. Prove that the sum of all such a fractions equals to 1/2. 121. Given n points in the three dimensional space such, that the arbitrary triangle with the vertices in three of those points contains an angle greater than 120 degrees. Prove that You can rearrange them to make a polyline (unclosed) with all the angles between the successive links will be greater than 120 degrees. 122. Find four different three-digit decimal numbers starting with the same digit, such that their sum is dividable by three of them. 123. Every city in the certain state is connected by airlines with no more than with three other ones, but one can get from every city to every other city changing a plane once only or directly. What is the maximal possible number of the cities? 124. Given a pentagon with all equal sides. a) Prove that there exist such a point on the maximal diagonal, that every side is seen from it inside a right angle. /* I mean that the side AB is seen from the point C inside an arbitrary angle that is greater or equal than angle ACB. - VAP */ b) Prove that the circles build on its sides as on the diameters cannot cover the pentagon entirely. 125. Given an equation x**3 + ?x**2 + ?x + ? = 0. First player substitutes an integer on the place of one of the interrogative marks, than the same do the second with one of the two remained marks, and, finally, the first puts the integer instead of the last mark. Explain how can the first provide the existence of three integer roots in the obtained equation. (The roots may coincide.) 126. 20 football teams participate in the championship. What minimal number of the games should be played to provide the property: from the three arbitrary teams we can find at least on pair that have already met in the championship. 127. Let h_k be an apothem of the right k-angle inscribed into a circle with radius R. Prove that (n + 1)h_{n+1} - nh_n > R. 128. Prove that for the arbitrary positive a_1, a_2, ... , a_n helds unequality a_1 a_2 a_{n-1} a_n n --------- + --------- + ... + --------- + --------- > -. a_2 + a_3 a_3 + a_4 a_n + a_1 a_1 + a_2 4 .............. (to be continued in a month or two) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ < ____/| Vladimir A. Pertsel > < \ o.O| > < =(_)= E-mail: voldemar@wisdom.weizmann.ac.il > < U > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ From hip-hop!benjie@amdahl.com Sun Feb 27 11:37:00 1994 From: Pertsel Vladimir Subject: Russian mathematical competitions (part 2) RMC 129-143 -Russian mathematical competitions References: <1994Feb6.185249.11115@wisipc.weizmann.ac.il> Keywords: Russia competition The 4-th competition -- Simferopol, 1970. form first day second day 8 129 130 131 132 133a 9 134 135 133b 136 137 10 138 139 133b 136 140 | 141 142 143 129. Given a circle, its diameter [AB] and a point C on it. Build (with the help of compasses and ruler) two points X and Y, that are symmetric with respect to AB, such that YC is orthogonal to XA. 130. The product of three positive numbers equals to one, their sum is strictly greater than the sum of the inversed numbers. Prove that one and only one of them is greater than one. 131. How many of the sides of the convex polygon can equal to its longest diagonal? 132. The digits of the 17-digit number are rearranged in the reverse order. Prove that at list one digit of the sum of the new and the initial number is even. 133. a) A castle is right triangle with the side 100 meters (in the scheme). It is divided onto 100 triangle rooms. Each wall between the rooms is 10 meters and contain one door. You are inside and are allowed to pass through every door not more than once. Prove that You can visit not more than 91 room (not exiting the castle). b) Every side of the triangle is divided onto k parts by the lines parallel to the sides. And the triangle is divided onto k**2 small triangles. Let us call the "chain" such a sequence of triangles, that every triangle in it is included only once, and the consecutive triangles have the common side. What is the greatest possible number of the triangles in the chain? 134. Given five segments. It is possible to build a triangle of every subset of three of them. Prove that at least one of those triangles is acute-angled. 135. The bisector AD, the median BM and the height CH of the acute- angled triangle ABC intersect in one point. Prove that the angle BAC is greater than 45 degrees. 136. Given five n-digit binary numbers. For each two numbers their digits coincide exactly on m places. There is no place with the common digit for all the five numbers. 2 m 3 Prove that - <= - <= -. 5 n 5 137. Prove that from every set of 200 integers You can choose a subset of 100 with the total sum dividable by 100. 138. Given triangle ABC, middle M of the side BC, the centre O of the inscribed circle. The line MO crosses the height AH in the point E. Prove that the distance |AE| equals to the radius of the inscribed circle. 139. Prove that for every natural number k there exists an infinite set of such a natural numbers t, that the decimal notation of t does not contain zeroes and the sums of the digits of the numbers t and kt are equal. 140. Two equal rectangles are intersecting in 8 points. Prove that the area of the common part is greater than the half of the square of each of the triangles. 141. All the 5-digit numbers from 11111 to 99999 are written on the cards. Those cards lies in a line in an arbitrary order. Prove that the resulting 444445-digit number is not a power of two. 142. All the natural numbers containing not more than n digits are divided onto two groups. The first contains the numbers with the even sum of the digits, the second -- with the odd sum. Prove that if 0 < k < n than the sum of the k-th powers of the numbers in the first group equals to the sum of the k-th powers of the numbers in the second group. 143. The vertices of the right n-angle are marked with some colours (each vertex -- with one colour) in such a way, that the vertices of one colour represent the right polygon. Prove that there are two equal ones among the smaller polygons. The 5-th competition -- Riga, 1971. form first day second day 8 144 145a 146a 147 | 152ab 153 154 9 144 145a 148 147 146b | 156abc152c 155 10 149 145b 150 147 151b | 156 157 158 144. Prove that for every natural n there exists a number, containing only digits "1" and "2" in its decimal notation, that is dividable by 2**n ( n-th power of two ). 145. a) Given a triangle A_1A_2A_3 and the points B_1 and D_2 on the side A_1A_2, B_2 and D_3 on the side A_2A_3, B_3 and D_1 on the side A_3A_1. If You build parallelograms A_1B_1C_1D_1, A_2B_2C_2D_2 and A_3B_3C_3D_3, the lines A_1C_1, A_2C_2 and A_3C_3, will cross in one point O. Prove that if |A_1B_1| = |A_2D_2| and |A_2B_2| = |A_3D_3|, than |A_3B_3| = |A_1D_1|. b) Given a convex polygon A_1A_2 ... A_n and the points B_1 and D_2 on the side A_1A_2, B_2 and D_3 on the side A_2A_3, ........ B_n and D_1 on the side A_nA_1. If You build parallelograms A_1B_1C_1D_1, A_2B_2C_2D_2 ... , A_nB_nC_nD_n, the lines A_1C_1, A_2C_2,...,A_nC_n, will cross in one point O. Prove that |A_1B_1|*|A_2B_2|*...*|A_nB_n| = |A_1D_1|*|A_2D_2|*...*|A_nD_n|. 146. a)A game for two. The first player writes two rows of ten numbers each, the second under the first. He should provide the following property: if number b is written under a, and d -- under c, then a + d = b + c. The second player has to determine all the numbers. He is allowed to ask the questions like "What number is written in the x place in the y row?" What is the minimal number of the questions asked by the second player before he founds out all the numbers? b) There was a table mxn on the blackboard with the property: if You chose two rows and two columns, then the sum of the numbers in the two opposite vertices of the rectangles formed by those lines equals to the sum of the numbers in two another vertices. Some of the numbers are cleaned. but it is still possible to restore all the table. What is the minimal possible number of the remaining numbers? 147. Given an unite square and some circles inside. Radius of each circle is less than 0.001, and there is no couple of points belonging to the different circles with the distance between them 0.001 exactly. Prove that the area, covered by the circles is not greater than 0.34. 148. The volumes of the water containing in each of three big enough containers are integers. You are allowed only to relocate some times from one container to another the same volume of the water, that the destination already contains. Prove that You are able to discharge one of the containers. 149. Prove that if the numbers p_1, p_2, q_1, q_2 satisfy the condition (q_1 - q_2)**2 + (p_1 - p_2)(p_1q_2 - p_2q_1) < 0, then the square polynomials x**2 + p_1x + q_1 and x**2 + p_2x + q_2 have real roots, and between the roots of each there is a root of another one. 150. The projections of the body on two planes are circles. Prove, that they have the same radius. 151. Some numbers are written along the ring. If for the four numbers in succession a,b,c,d helds unequality (a - d)(b - c) < 0, You change the numbers b and c. Prove, that You will have to do this operation the finite number of times. 152. a) Prove that the line dividing the triangle onto two polygons with equal perimeters and equal areas passes through the centre of the inscribed circle. b) Prove the same statement for the arbitrary polygon outscribed around the circle. c) Prove that all the lines halving its perimeter and area simultaneously, intersect in one point. 153. Given 25 different positive numbers. Prove that You can choose two of them such, that none of the other numbers equals neither to the sum nor to the difference between the chosen numbers. 154. a) The vertex A_1 of the right 12-angle (dodecagon) A_1A_2...A_{12} is marked with "-" and all the rest -- with "+". You are allowed to change the sign simultaneously in the 6 vertices in succession. Prove that is impossible to obtain dodecagon with A_2 marked with "-" and the rest of the vertices -- with "+". b) Prove the same statement if it is allowed to change the signs not in six, but in four vertices in succession. c) Prove the same statement if it is allowed to change the signs in three vertices in succession. 155. N unit squares on the infinite sheet of cross-lined paper are painted with black colour. Prove that You can cut out the finite number of square pieces and satisfy two conditions - all the black squares are contained in those pieces. - the area of black squares is not less than 1/5 and not greater than 4/5 of every piece area. ------------- The task for the tenth form was as follows. "You are given three serious problems. Try to investigate at least one, but to obtain as many results, as You can. At the end of Your work make a sort of resume, showing the main proved facts, challenged examples and the hypotheses that seem to be true ..." /* this form of competition was never repeated later - it had required too much efforts from those who checked the works */ ------------- 156. A cube with the edge of length n is divided onto n**3 unit ones. Let us choose some of them and draw three lines parallel to the edges through their centres. What is the least possible number of the chosen small cubes necessary to make those lines cross all the smaller cubes? a) Find the answer for the small n (n = 2,3,4). b) Try to find the answer for n = 10. c) If You can not solve the general problem, try to estimate that value from the upper and lower side. d) Note, that You can reformulate the problem in such a way. Consider all the triples (x_1,x_2,x_3), where x_i can be one of the integers 1,2,...,n. What is the minimal number of the triples necessary to provide the property: for each of the triples there exist the chosen one, that differs only in one coordinate. Try to find the answer for the situation with more than three coordinates, for example, with four. 157. a) Consider the function f(x,y) = x**2 + xy + y**2. Prove that for the every point (x,y) there exist such integers (m,n), that f((x-m),(y-n)) <= 1/2. b) Let us denote with g(x,y) the least possible value of the f((x-m),(y-n)) for all the integers m,n. The statement a) was equal to the fact g(x,y) <= 1/2. Prove, that in fact, g(x,y) <= 1/3. Find all the points (x,y), where g(x,y)=1/3. c) Consider function f_a(x,y) = x**2 + axy + y**2 (0 <= a <= 2). Find any c such that g_a(x,y) <= c. Try to obtain the closest estimation. 158. 1 2 1 2 | | | | The switch with two inputs and two v v v v outputs can be in one of two +-+---+-+ +-+---+-+ different positions. In the left | | | | | | | | part of the picture a) the first input | \ / | | | | | is connected with the second output | X | | | | | and we can denote this as | / \ | | | | | 1 2 | | | | | | | | | | and the position in the right +-+---+-+ +-+---+-+ V V part of the picture 1 2 | | | | 2 1 will be denoted as | | V V V V V V 1 2 1 2 1 2 pic.a) 1 2 3 The scheme on the picture b) is universal | | | in that sense that changing the state of V V | the element switches You can obtain all +-+---+-+ | the six connections, i.e. | | | | | | 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 +-+---+-+ | | | | | | | | | | | | | | | | | | | | | | V V V V V V V V V V V V V V V V V V | V V 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 | +-+---+-+ | | | (Check it. Note, that the total number of the | | | states is 2**3 = 8, because each element | +-+---+-+ can be in two positions.) | | | V V | +-+---+-+ | | | | | | | +-+---+-+ | | | | V V V 1 2 3 pic.b) a) Try to build the universal scheme for 4 inputs and 4 outputs, that can provide all of 24 possible connections. b) What is the minimal number of the element switches for such a scheme? c) Let us call a scheme with n inputs and n outputs n-universal, if it can provide all n! possible connections of n inputs with n outputs. Here is the scheme (picture c) with 8 inputs and 8 outputs, where A and B are 4-universal. Prove that it is 8-universal. 1 2 3 4 5 6 7 8 | | | | | | | | V V V V V V V V V V V V V V V V +-+---+-+ +-+---+-+ +-+---+-+ +-+---+-+ +-+---+-+ +-+---+-+ +-+---+-+ +-+---+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+---+-+ +-+---+-+ +-+---+-+ +-+---+-+ +-+---+-+ +-+---+-+ +-+---+-+ +-+---+-+ | \ | \ | \ | \ / | / | / | / | | \ | \ | \ | \ / | / | / | / | | \ | \ | \ | X | / | / | / | ................................................................................ |/ |/ |/ |/ \| \| \| \| +-+---------+---------+---------+-----+ +-----+---------+---------+---------+-+ | | | | | A | | B | | | | | +-+---------+---------+---------+-----+ +-----+---------+---------+---------+-+ |\ |\ |\ |\ /| /| /| /| ................................................................................ | / | / | / | / \ | \ | \ | \ | | / | / | / | / \ | \ | \ | \ | V V V V V V V V V V V V V V V V +-+---+-+ +-+---+-+ +-+---+-+ +-+---+-+ +-+---+-+ +-+---+-+ +-+---+-+ +-+---+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+---+-+ +-+---+-+ +-+---+-+ +-+---+-+ +-+---+-+ +-+---+-+ +-+---+-+ +-+---+-+ | | | | | | | | V V V V V V V V 1 2 3 4 5 6 7 8 pic.c) d) Estimate the upper and lower bound for the number of the element switches in the n-universal scheme. The 6-th competition -- Chelyabinsk, 1972. form first day second day 8 159 160 161 | 166 167 168 9 162a 163 161 164 | 169 170 171 10 162b 163 165 164 | 166 172 173 159. Given a rectangle ABCD, points M -- the middle of AD side, N -- the middle of BC side. Let us take a point P on the continuation of the DC segment over the point D. Let us denote the point of intersection of lines PM and AC as Q. Prove that the angles QNM and MNP are equal. 160. Given 50 segments on the line. Prove that one of the following statements is valid. 1. Some 8 segments have the common point. 2. Some 8 segments do not intersect each other. 161. Find the maximal x such that the expression 4**{27} + 4**{1000} + 4**x is the exact square. 162. a) Let a,n,m be natural numbers, a > 1. Prove that if (a**m + 1) is dividable by (a**n + 1) than m is dividable by n. b) Let a,b,n,m be natural numbers, a > 1, a and b are relatively prime. Prove that if (a**m + b**m) is dividable by (a**n + b**n) than m is dividable by n. 163. The triangle table is built according to the rule: You put the natural number a in 2 the upper row, and then You write / \ under the number k from the left / \ side k**2, and from the right side / \ -- (k+1). For example, if a = 2, 4 3 You get the table on the picture. /\ /\ Prove that all the numbers on each / \ / \ particular line are different. 16 5 9 4 / \ / \ /\ / \ 164. Given several squares with the total area 1. Prove that You can pose them in the square of the area 2 without any intersections. 165.Let O be the point of intersection of the diagonals of the convex quadrangle ABCD. Prove that the line drawn through the points of intersection of the medians of AOB and COD triangles is orthogonal to the line drawn through the points of intersection of the heights of BOC and AOD triangles. 166. Each of the 9 straight lines divides the given square onto two quadrangles with the areas related as 2:3. Prove that there exist three of them intersecting in one point. 167. The 7-angle A_1A_2A_3A_4A_5A_6A_7 is inscribed in a circle. Prove that if the centre of the circle is inside the 7-angle, than the sum of A_1,A_2 and A_3 angles is less than 450 degrees. 168. A game for two. One gives a digit and the second substitutes it instead of a star in the following difference: **** - **** = Then the first gives the next digit, and so on 8 times. The first wants to obtain the greatest possible difference, the second -- the least. Prove that: 1. The first can operate in such a way that the difference would be not less than 4000, not depending on the second's behavior. 2. The second can operate in such a way that the difference would be not greater than 4000, not depending on the first's behavior. 169. Let x and y be the positive numbers, s -- the least of { x, (y+ 1/x), 1/y}. What is the greatest possible value of s? To what x and y does it correspond? 170. The point O inside the convex polygon makes isosceles triangle with all the pairs of its vertices. Prove that O is the centre of the outscribed circle. 171. Is it possible to put the numbers 0,1 or 2 in the squares of the cross-lined paper 100x100 in such a way, that in every rectangle 3x4 (and 4x3) would contain three zeros, four ones and five twos? 172. Let the sum of positive numbers x_1, x_2, ... , x_n be 1. Let s be the greatest of the numbers x_1 x_2 x_n -------, -------------, ... , -------------------. 1 + x_1 1 + x_1 + x_2 1 + x_1 + ... + x_n What is the minimal possible s? What x_i correspond it. /* Derivatives were not included in the school plans in Russia. They expected another solution. -VAP */ 173. One-round hockey tournament is finished (each plays with each one time, the winner gets 2 points, looser -- 0, and 1 point for draw). For arbitrary subgroup of teams there exists a team (may be from that subgroup) that has got an odd number of points in the games with the teams of the subgroup. Prove that there was even number of the participants. The 7-th competition -- Kishenew, 1973. form first day second day 8 174a 175 176 | 182 183 184ab 9 174b 177 178 | 179 185 186 184c 10 180 177 181 | 187 188 184c 174. Fourteen coins are submitted to the judge. An expert knows, that the coins from number one to seven are false, and from 8 to 14 -- normal. The judge is sure only that all the true coins have the same weight and all the false coins weights equal each other, but are less then the weight of the true coins. The expert has the scales without weights. a) The expert wants to prove, that the coins 1--7 are false. How can he do it in three weighings? b) How can he prove, that the coins 1--7 are false and the coins 8--14 are true in three weighings? 175. Prove that 9-digit number containing all the decimal digits except zero can not be the exact square. 176. Given n points, n > 4. Prove, that You can connect them with arrows, in such a way, that You can reach every point from every other point, having passed through one or two arrows. (You can connect every pair with one arrow only, and move along the arrow in one direction only.) 177. Given an angle with the vertex O and a circle touching its sides in the points A and B. A ray is drawn from the point A parallel to OB. It intersects with the circumference in the point C. The segment OC intersects the circumference in the point E. The straight lines AE and OB intersect in the point K. Prove that |OK| = |KB|. 178. The real numbers a,b,c satisfy the condition: for all x, such that -1 <= x <= 1, helds unequality | ax**2 + bx + c | <= 1. Prove that for the same x helds | cx**2 + bx + a | <= 2. 179. The tennis federation has assigned numbers to 1024 sportsmen, participating in the tournament, according to their skill. (The tennis federation uses the olympic system of tournaments. The looser in the pair leaves, the winner meets with the winner of another pair. Thus, in the second tour remains 512 participants, in the third -- 256, et.c. The winner is determined after the tenth tour.) It comes out, that in the play between the sportsmen whose numbers differ more than on 2 always win that whose number is less. What is the greatest possible number of the winner? 180. The square polynomial f(x) = ax**2 + bx + c is of such a sort, that the equation f(x) = x does not have real roots. Prove, that the equation f(f(x)) does not have real roots also. 181. n squares of the infinite cross-lined sheet of paper are painted with black colour (others are white). Every move all the squares of the sheet change their colour simultaneously. The square gets the colour, that had the majority of three ones: the square itself, its neighbor from the right side and its neighbor from the upper side. a) Prove that after the finite number of the moves all the black squares will disappear. b) Prove that it will happen not later than on the n-th move. 182. Three similar acute-angled triangles AC_1B, BA_1C and CB_1A are built on the outer side of the acute-angled triangle ABC. (Equal triples of the angles are AB_1C, ABC_1, A_1BC and BA_1C, BAC_1, B_1AC.) a) Prove that the circumferences outscribed around the outer triangles intersect in one point. b) Prove that the straight lines AA_1, BB_1 and CC_1 intersect in the same point. 183. N men are not acquainted each other. You need to introduce some of them to some of them in such a way, that all the men will have different number of the acquaintancees. Prove that it is possible for all N. 184. The king have revised the chessboard 8x8 having visited all the fields once only and returned to the starting point. When his trajectory was drawn (the centres of the squares were connected with the straight lines), a closed broken line without self-intersections appeared. a) Give an example that the king could make 28 steps parallel the sides of the board only. b) Prove that he could not make less than 28 such a steps. c) What is the maximal and minimal length of the broken line if the side of a field is 1? 185. Given a triangle with the sides a, b, c and with the area 1. a >= b >= c. Prove that b**2 >= 2. 186. Given a convex n-angle with pairwise (mutually) non-parallel sides /* who knows Russian - a letter "r" had broken on the organizing committee's typewriter - and it became an unexhaustable source of jokes for some years */ and a point inside it. Prove that there are not more than n straight lines coming through that point and halving the area of the n-angle. 187. Prove that for every positive x_1, x_2, x_3, x_4, x_5 helds unequality (x_1, x_2, x_3, x_4, x_5)**2 >= >= 4(x_1x_2 + x_3x_4 + x_5x_1 + x_2x_3 + x_4x_5). 188. Given 4 points in three-dimensional space, not lying in one plane. What is the number of such a parallelepipeds, that those points serve as a vertices for each? The 8-th competition -- Erevan, 1974. form first day second day 8 189abc190 191 | 197 198 199 200a 9 190 192 189d 193 | 201 202 200b 10 194 195 196 193 | 203 204 200b 189. a,b,c) Given some cards with either "-1" or "+1" written on the opposite side. You are allowed to choose a triple of cards and ask about the product of the three numbers on the cards. What is the minimal number of questions allowing to determine all the numbers on the cards ... a) for 30 cards, b) for 31 cards, c) for 32 cards. (You should prove, that You cannot manage with the less amount of questions.) d) Fifty abovementioned cards are lying along the circumference. You are allowed to ask about the product of three consecutive numbers only. You need to determine the product af all the 50 numbers. What is the minimal number of questions allowing to determine it? 190. Among all the numbers representable as {36}**k - 5**l (k and l are natural numbers) find the smallest. Prove that it is really the smallest. 191. a) Each of the side of the convex hexagon (6-angle) is longer than 1. Does it necessary have a diagonal longer than 2? b) Each of the main diagonals of the convex hexagon is longer than 2. Does it necessary have a side longer than 1? 192. Given two circles with the radiuses R and r, touching each other from the outer side. Consider all the trapezoids, such that its lateral sides touch both circles, and its bases touch different circles. Find the shortest possible lateral side. 193. Given n vectors of unit length in the plane. The length of their total sum is less than one. Prove that You can rearrange them to provide the property: for every k, k<= n, the length of the sum of the first k vectors is less than 2. 194. Find all the real a,b,c such that the equality |ax + by + cz| + |bx + cy + az| + |cx + ay + bz| = |x| + |y| + |z| is valid for all the real x,y,z. 195. Given a square ABCD. Points P and Q are in the sides AB and BC respectively. |BP| = |BQ|. Let H be the base of the perpendicular from the point B to the segment PC. Prove, that the angle DHQ is a straight one. 196. Given some red and blue points. Some of them are connected by the segments. Let us call "exclusive" the point, if its colour differs from the colour of more than half of the connected points. Every move one arbitrary "exclusive" point is repainted to the other colour. Prove that after the finite number of moves there will remain no "exclusive" points. 197. Find all the natural n and k such that n**n has k digits and k**k has n digits. 198. Given points D and E on the legs CA and CB, respectively, of the isosceleos right triangle. |CD| = |CE|. The extensions of the perpendiculars from D and C to the line AE cross the hypotenuse AB in the points K and L. Prove that |KL| = |LB|. 199. Two are playing the game "cats and rats" on the chessboard 8x8. The first has one piece -- a rat, the second -- several pieces -- cats. All the pieces have four available moves -- up, down, left, right -- to the neighbor field, but the rat can also escape from the board if it is on the boarder of the chessboard. If they appear on the same field -- the rat is eaten. The players move in turn, but the second can move all the cats in independent directions. a)Let there be two cats. The rat is on the interior field. Is it possible to put the cats on such a fields on the border that they will be able to catch the rat? b)Let there be three cats, but the rat moves twice diring the first turn. Prove that the rat can escape. 200. a) Prove that You can rearrange the numbers 1, 2, ... , 32 in such a way, that for every couple of numbers none of the numbers between them will equal their arithmetic mean. b) Can You rearrange the numbers 1, 2, ... , 100 in such a way, that for every couple of numbers none of the numbers between them will equal their arithmetic mean? 201. Find all the three-digit numbers such that it equals to the arithmetic mean of the six numbers obtained by rearranging its digits. 202. Given a convex polygon. You can not put a triangle with the area 1 inside it. Prove that You can put the polygon inside a triangle with the area 4. 203. Given a function f(x) on the segment 0 <= x <= 1. For all x, f(x) >= 0; f(1) = 1. For all the couples of x_1, x_2 such, that all the arguments are in the segment helds the inequality f(x_1 + x_2) >= f(x_1) + f(x_2). a) Prove, that for all x helds f(x) <= 2x. b) Is the inequality f(x) <= {1.9}x valid? 204. Given a triangle ABC with the are 1. Let A',B' and C' are the middles of the sides BC, CA and AB respectively. What is the minimal possible area of the common part of two triangles A'B'C' and KLM, if the points K,L and M are lying on the segments [AB'],[CA'] and [BC'] respectively? The 9-th competition -- Saratov, 1975. form first day second day 8 205a 206 207 208a | 213 214 215 9 209 206 210 208b | 216 215 217 10 211 212 205b 208 | 214 218 219 205. a) The triangle ABC was turned around the centre of the outscribed circle by the angle less than 180 degrees and thus was obtained the triangle A_1B_1C_1. The corresponding segments [AB] and [A_1B_1] intersect in the point C_2; [BC] and [B_1C_1] -- A_2; [AC] and [A_1C_1] -- B_2. Prove that the triangle A_2B_2C_2 is similar to the triangle ABC. b) The quadrangle ABCD was turned around the centre of the outscribed circle by the angle less than 180 degrees and thus was obtained the quadrangle A_1B_1C_1D_1. Prove that the points of intersection of the corresponding lines (AB and A_1B_1, BC and B_1C_1, CD and C_1D_1, DA and D_1A_1) are the vertices of the parallelogram. 206. Given a triangle ABC with the unit area. The first player chooses a point X on the side [AB], than the second -- Y on [BC] side, and, finally, the first chooses a point Z on [AC] side. The first tries to obtain the greatest possible area of the XYZ triangle, the second -- the smallest. What area can obtain the first for sure and how? 207. What is the smallest perimeter of the convex 32-angle, having all the vertices in the nodes of cross-lined paper with the sides of its squares equal to 1? 208. a) Given a big square consisting of 7x7 squares. You should mark the centres of k points in such a way, that no quadruple of the marked points will be the vertices of a rectangle with the sides parallel to the sides of the given squares. What is the greatest k such that the problem has solution? b) The same problem for {13}x{13} square. 209. Denote the middles of the convex hexagon A_1A_2A_3A_4A_5A_6 diagonals A_6A_2, A_1A_3, A_2A_4, A_3A_5, A_4A_6, A_5A_1 as B_1, B_2, B_3, B_4, B_5, B_6 respectively. Prove that if the hexagon B_1B_2B_3B_4B_5B_6 is convex, than its area equals to the quarter of the initial hexagon. 210. Prove that it is possible to find 2**{n+1} of 2**n digit numbers containing only "1" and "2" as digits, such that every two of them distinguish at least in 2**{n-1} digits. 211. Given a finite set of polygons in the plane. Every two of them have a common point. Prove that there exists a straight line, that crosses all the polygons. 212. Prove that for all the positive numbers a,b,c the following unequality is valid: a**3 + b**3 + c**3 + 3abc > ab(a + b) + bc(b + c) + ac(a + c). 213. Three flies are crawling along the perimeter of the ABC triangle in such a way, that the center of their masses is a constant point. One of the flies has already passed along all the perimeter. Prove, that the center of the flies' masses coincides with the center of masses of the ABC triangle. (The center of masses for the triangle is the point of medians intersection.) 214. Several zeros, ones and twos are written on the blackboard. An anonymous clean in turn pairs of different numbers, writing, instead of cleaned, the number not equal to each. (0 instead of pair {1,2}; 1 instead of {0,2}; 2 instead of {0,1}). Prove that if there remains one number only, it does not depend on the processing order. 215. Given a horizontal strip on the plane (its sides are parallel lines) and n lines intersecting the strip. Every two of them intersect inside the strip, and not a triple has a common point. Consider all the paths along the segments of those lines, starting on the lower side of the strip and ending on the upper side with the properties: moving along such a path we are constantly rising up, and, having reach the intersection, we are obliged to turn to the another line. Prove that a) there are not less than n/2 such a paths without common points; b) there is a path consisting of not less than of n segments; c) there is a path that goes along not more than along n/2+1 lines; d) there is a path that goes along all the n lines. 216. For what k is it possible to construct a cube kxkxk of the black and white cubes 1x1x1 in such a way that every small cube has the same colour, that have exactly two his neighbors. (Two cubes are neighbors, if they have the common face.) 217. Given a polynomial P(x) with a) natural coefficients; b) integer coefficients; Let us denote with a_n the sum of the digits of P(n). Prove that there is a number encountered in the sequence a_1, a_2, ... , a_n, ... infinite times. 218. The world and the european champion are determined in the same tournament carried in one round. There are 20 teams and k of them are european. The european champion is determined according to the results of the games only between those k teams. What is the greatest k such that the situation, when the single european champion is the single world outsider, is possible if: a) it is hockey (draws allowed)? b) it is volleyball (no draws)? 219. a) Given real numbers a_1, a_2, b_1, b_2 and positive p_1, p_2, q_1, q_2. Prove that in the table 2x2 a_1 + b_1 a_1 + b_2 --------- --------- p_1 + q_1 p_1 + q_2 a_2 + b_1 a_2 + b_2 --------- --------- p_2 + q_1 p_2 + q_2 there is a number in the table, that is not less than another number in the same row and is not greater than another number in the same column (a saddle point). b) Given real numbers a_1, a_2, ... , a_n; b_1, b_2, ... , b_n and positive p_1, p_2, ... , p_n; q_1, q_2, ... , q_n. We build the table nxn, with the numbers (0 < i,j <= n) a_i + b_j --------- p_i + q_j in the intersection of the i-th row and j-th column. Prove that there is a number in the table, that is not less than arbitrary number in the same row and is not greater than arbitrary number in the same column (a saddle point). ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ < ____/| Vladimir A. Pertsel > < \ o.O| > < =(_)= E-mail: voldemar@wisdom.weizmann.ac.il > < U > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ From hip-hop!benjie@amdahl.com Fri Apr 1 13:59:00 1994 From: Pertsel Vladimir Subject: Russian math. competitions, part3. The 10-th competition -- Dushanbe, 1976. form first day second day 8 220 221 222ab 223 | 229 230 231 9 222b 224 223 225 | 230 232 231 10 223 226 227 228 225 | 233 234 231 220. There are 50 sharp watches lying on a table. Prove that there exist a certain moment, when the sum of the distances from the centre of the table to the ends of the minute hands is more than the sum of the distances from the centre of the table to the centres of the watches. 221. A row of 1000 numbers is written on the blackboard. We write a new row, below the first according to the rule: We write under every number a the natural number, indicating how many times the number a is encountered in the first line. Then we write down the third line : under every number b -- the natural number, indicating how many times the number b is encountered in the second line, and so on. a) Prove that there is a line that coincides with the preceding one. b) Prove that the eleventh line coincides with the twelfth. c) Give an example of the initial line such, that the tenth row differs from the eleventh. 222. Given three circumferences of the same radius in a plane. a) All three are crossing in one point K. Consider three arcs AK,CK,EK : the A,C,E are the points of the circumferences intersection and the arcs are taken in the clockwise direction. (Sorry, no picture. Every arc is inside one circle, outside the second and on the border of the third one) Prove that the sum of the arcs is 180 degrees. b) Consider the case, when the three circles give a curvilinear triangle BDF as there intersection (instead of one point K). Prove that the sum of the AB, CD and EF arcs is 180 degrees. (The arcs are taken in the clockwise direction. Every arc is inside one circle, outside the second and on the border of the third one) 223. The natural numbers x_1 and x_2 are less than 1000. We build a sequence: x_3 = |x_1 - x_2|; x_4 = min { |x_1 - x_2|, |x_1 - x_3|, |x_2 - x_3|}; ....... x_k = min { |x_i - x_j|; 0 = |a + d| + |b + d| + |c + d|. 226. Given right 1976-angle. The middles of all the sides and diagonals are marked. What is the greatest number of the marked points lying on one circumference? 227. There are n rectangles drawn on the rectangular sheet of paper with the sides of the rectangles parallel to the sheet sides. The rectangles do not have pairwise common interior points. Prove that after cutting out the rectangles the sheet will split into not more than n+1 part. 228. There are three straight roads. Three pedestrains are moving along those roads, and they are NOT on one line in the initial moment. Prove that they will be one line not more than twice. 229. Given a chessboard 99x99 with a set F of fields marked on it (the set is different in three tasks). There is a beatle sitting on every field of the set F. Suddenly all the beatles have raised into the air and flied to another fields of the same set. The beatles from the neighboring fields have landed either on the same field or on the neighboring ones (may be far from their starting point). (We consider the fields to be neighboring if they have at least one common vertex.) Consider a statement: "There is a beatle, that either stayed on the same field or moved to the neighboring one". Is it always valid if the figure F is: a) A central cross, i.e. the union of the 50-th row and the 50-th column? b) A window frame, i.e. the union of the 1-st, 50-th and 99-th rows and the 1-st, 50-th and 99-th columns? c) All the chessboard? 230. Let us call "big" a triangle with all sides longer than 1. Given a equilateral triangle with all the sides equal to 5. Prove that: a) You can cut 100 big triangles out of given one. b) You can divide the given triangle onto 100 big nonintersecting ones fully covering the initial one. c) The same as b), but the triangles either do not have common points, or have one common side, or one common vertex. d) The same as c), but the initial triangle has the side 3. 231. Given a natural number n. We shall call "universal" such a sequence of natural number a_1, a_2, ... , a_k; k>=n, if we can obtain every transposition of the first n natural numbers (i.e such a sequence of n numbers, that every one is encountered only once) by deleting some its members. (Examples: (1,2,3,1,2,1,3) is universal for n=3, and (1,2,3,2,1,3,1) -- not, because You can't obtain (3,1,2) from it.) The goal is to estimate the length of the shortest universal sequence for given n. a) Give an example of the universal sequence of n**2 members. b) Give an example of the universal sequence of (n**2 -n + 1) members. c) Prove that every universal sequence contains not less than n(n + 1)/2 members d) Prove that the shortest universal sequence for n=4 contains 12 members e) Find as short universal sequence, as You can. The Organizing Committee knows the method for (n**2 - 2n +4) members. 232. n numbers are written down along the circumference. Their sum equals to zero, and one of them equals 1. a) Prove that there are two neighbors with their difference not less than n/4. b) Prove that there is a number that differs from the arithmetic mean of its two neighbors not less than on 8/{n**2}. c) Try to improve the previous estimation, i.e what number can be used instead of 8? d) Prove that for n=30 there is a number that differs from the arithmetic mean of its two neighbors not less than on 2/113; give an example of such 30 numbers along the circumference, that not a single number differs from the arithmetic mean of its two neighbors more than on 2/113. 233. Given right n-angle wit the point O -- its centre. All the vertices are marked either with +1 or -1. We may change all the signs in the vertices of right k-angle (2 <= k <= n) with the same centre O. (By 2-angle we understand a segment, being halved by O.) Prove that in a), b) and c) cases there exists such a set of (+1)s and (-1)s, that we can never obtain a set of (+1)s only. a) n = 15; b) n = 30; c) n > 2; d) Let us denote K(n) the maximal number of (+1) and (-1) sets such, that it is impossible to obtain one set from another. Prove, for example, that K(200) = 2**{80}. 234. Given a sphere of unit radius with the big circle (i.e of unit radius) that will be called "equator". We shall use the words "pole", "parallel","meridian" as self-explanatory. a) Let g(x), where x is a point on the sphere, be the distance from this point to the equator plane. Prove that g(x) has the property (*) if x_1, x_2, x_3 are the ends of the pairwise orthogonal radiuses, than g(x_1)**2 + g(x_2)**2 + g(x_3)**2 = 1. Let function f(x) be an arbitrary nonnegative function on a sphere that satisfies (*) property. b) Let x_1 and x_2 points be on the same meridian between the north pole and equator, and x_1 is closer to the pole than x_2. Prove that f(x_1) > f(x_2). c) Let y_1 be closer to the pole than y_2. Prove that f(y_1) > f(y_2). d) Let z_1 and z_2 be on the same parallel. Prove that f(z_1) = f(z_2). e) Prove that for all x f(x) = g(x). The 11-th competition -- Tallinn, 1977. form first day second day 8 235 236 237b 238 | 243 244ab 245 246 9 237a 239 235 240 | 247 248 249 250 10 237a 239 241 242 235 | 251 244 246 235. Given a closed broken line without self-intersections in a plane. Not a triple of its vertices belongs to one straight line. Let us call "special" a couple of line's segments such that the continuation of one of them intersects another. Prove that there is even number of special pairs. 236. Given several ponts not lying on one straight line. Some number is assigned to every point. It is known, that if a straight line contains two or more points, than the sum of the assigned to those points equals zero. Prove that all the numbers equal to zero. 237. a) Given a circle with two inscribed triangles T_1 and T_2. The vertices of T_1 are the middles of the arcs with the ends in the vertices of T_2. Consider a hexagon -- the intersection of T_1 and T_2. Prove that its main diagonals are parallel to T_1 sides and are intersecting in one point. b) The segment, that connects the middles of the arcs AB and AC of the circle outscribed around the ABC triangle, intersects AB and AC sides in D and K points. Prove that the points A,D,K and O -- the centre of the circle -- are the vertices of a diamond. 238. Several black an white checkers (tokens?) are standing along the circumference. Two men remove checkers in turn. The first removes all the black ones that had at least one white neighbor, and the second -- all the white ones that had at least one black neighbor. They stop when all the checkers are of the same colour. a) Let there be 40 checkers initially. Is it possible that after two moves of each man there will remain only one (checker)? b) Let there be 1000 checkers initially. What is the minimal possible number of moves to reach the position when there will remain only one (checker)? 239. Given infinite sequence a_n. It is known that the limit of b_n = a_{n+1} - {a_n}/2 equals zero. Rove that the limit of a_n equals zero. 240. There are direct routes from every city of a certain country to every other city. The prices are known in advance. Two tourists (they do not necessary start from one city) have decided to visit all the cities, using only direct travel lines. The first always chooses the cheapest ticket to the city, he has never been before (if there are several -- he chooses arbitrary destination among the cheapests). The second -- the most expensive (they do not return to the first city). Prove that the first will spend not more money for the tickets, than the second. /* The fact seems to be evident, but the proof is not easy -- VAP */ 241. Every vertex of a convex polyhedron belongs to three edges. It is possible to outscribe a circle around all its faces. Prove that the polyhedron can be inscribed in a sphere. 242. The polynomial x**{10} + ?x**9 + ?x**8 + ... +?x + 1 is written on the blackboard. Two players substitute (real) numbers instead of one of the question marks in turn. (9 turns total.) The first wins if the polynomial will have no real roots. Who wins? 243. Seven elves are sitting at a round table. Each elf has a cup. Some cups are filled with some milk. Each elf in turn and clockwise divides all his milk between six other cups. After the seventh has done this, every cup was containing the initial amount of milk. How much milk did every cup contain, if there was three liters of milk total? 244. Let us call "fine" the 2n-digit number if it is exact square itself and the two numbers represented by its first n digits (first digit may not be zero) and last n digits (first digit may be zero, but it may not be zero itself) are exact squares also. a) Find all two- and four-digit fine numbers. b) Is there any six-digit fine number? c) Prove that there exists 20-digit fine number. d) Prove that there exist at least ten 100-digit fine numbers. e) Prove that there exists 30-digit fine number. 245. Given a set of n positive numbers. For each its nonempty subset consider the sum of all the subset's numbers. Prove that You can divide those sums onto n groups in such a way, that the least sum in every group is not less than a half of the greatest sum in the same group. 246. There are 1000 tickets with the numbers 000, 001, ... , 999; and 100 boxes with the numbers 00, 01, ... , 99. You may put a ticket in a box, if You can obtain the box number from the ticket number by deleting one digit. Prove that a) You can put all the tickets in 50 boxes; b) 40 boxes is not enough for that; c) it is impossible to use less than 50 boxes. d) Consider 10000 4-digit tickets, and You are allowed to delete two digits. Prove that 34 boxes is enough for storing all the tickets. e) What is the minimal used boxes set in the case of k-digit tickets? 247. Given a square 100x100 on the sheet of cross-lined paper. There are several broken lines drawn inside the square. Their links consist of the small squares sides. They are neither pairwise- nor self-intersecting (have no common points). Their ends are on the big square boarder, and all the other vertices are in the big square interior. Prove that there exists (in addition to four big square angles) a node (corresponding to the cross-lining family, inside the big square or on its side) that does not belong to any broken line 248. Given natural numbers x_1, x_2, ... , x_n; y_1, y_2, ... , y_m. The following condition is valid: (x_1 + x_2 + ... + x_n) = (y_1 + y_2 + ... + y_m) < mn. (*) Prove that it is possible to delete some terms from (*) (not all and at least one) and to obtain another valid condition. 249. Given 1000 squares on the plane with their sides parallel to the coordinate axes. Let M be the set of those squares centres. Prove that You can mark some squares in such a way, that every point of M will be contained not less than in one and not more than in four marked squares. 250. Given (a) scales and a set of n different weights. We take weights in turn and add them on one of the scales sides. Let us denote "L" the scales state with the left side down, and "R" -- with the right side down. a) Prove that You can arrange the weights in such an order, that we shall obtain the sequence LRLRLRLR... of the scales states. (That means that the state of the scales will be changed after putting every new weight.) b) Prove that for every n-letter word containing R's and L's only You can arrange the weights in such an order, that the sequence of the scales states will be described by that word. 251. Let us consider one variable polynomials with the senior coefficient equal to one. We shall say that two polynomials P(x) and Q(x) commute, if P(Q(x))=Q(P(x)) (i.e. we obtain the same polynomial, having collected the similar terms). a) For every a find all Q such that the Q degree is not greater than three, and Q commutes with (x**2 - a). b) Let P be a square polynomial, and k is a natural number. Prove that there is not more than one commuting with P k-degree polynomial. c) Find the 4-degree and 8-degree polynomials commuting with the given square polynomial P. d) R and Q commute with the same square polynomial P. Prove that Q and R commute. e) Prove that there exists a sequence P_2, P_3, ... , P_n, ... (P_k is k-degree polynomial), such that P_2(x) = x**2 - 2, and all the polynomials in this infinite sequence pairwise commute. The 12-th competition -- Tashkent, 1978. form first day second day 8 252 253 254 255ab | 260 261 262 263 9 252 253 256 257 | 260 261 264 265 10 258 259 255cde257 | 260 266 267 268 252. Let a_n be the closest to sqrt(n) integer. Find the sum 1/{a_1} + 1/{a_2} + ... + 1/{a_{1980}}. 253. Given a quadrangle ABCD and a point M inside it such that ABMD is a parallelogram. the angle CBM equals to CDM. Prove that the angle ACD equals to BCM. 254. Prove that there is no m such that ({1978}**m - 1) is dividable by ({1000}**m - 1). 255. Given a finite set K_0 of points (in the plane or space). The sequence of sets K_1, K_2, ... , K_n, ... is build according to the rule: we take all the points of K_i, add all the symmetric points with respect to all its points, and, thus obtain K_{i+1}. a) Let K_0 consist of two points A and B with the distance 1 unit between them. For what n the set K_n contains the point that is 1000 units far from A? b) Let K_0 consist of three points that are the vertices of the equlateral triangle with the unit square. Find the area of minimal convex polygon containing K_n. K_0 below is the set of the unit volume tetrahedron vertices. c) How many faces contain the minimal convex polyhedron containing K_1? d) What is the volume of the abovementioned polyhedron? e) What is the volume of the minimal convex polyhedron containing K_n? 256. Given two heaps of checkers. the bigger contains m checkers, the smaller -- n (m>n). Two players are taking checkers in turn from the arbitrary heap. The players are allowed to take from the heap a number of checkers (not zero) divisible by the number of checkers in another heap. The player that takes the last checker in any heap wins. a) Prove that if m > 2n, than the first can always win. b) Find all x such that if m > xn, than the first can always win. 257. Prove that there exists such an infinite sequence {x_i}, that for all m and all k (m<>k) helds |x_m - x_k| > 1/|m-k|. 258. Let f(x) = x**2 + x + 1. Prove that for every natural m>1 the numbers m, f(m), f(f(m)), ... are relatively prime. 259. Prove that there exists such a number A that You can inscribe 1978 different size squares in the plot of the function y = A sin(x). (The square is inscribed if all its vertices belong to the plot.) 260. Given three automates that deal with the cards with the pairs of natural numbers. The first, having got the card with (a,b), produces new card with (a+1,b+1); the second, having got the card with (a,b), produces new card with (a/2,b/2), if both a and b are even and nothing in the opposite case; the third, having got the pair of cards with (a,b) and (b,c) produces new card with (a,c). All the automates return the initial cards also. Suppose there was (5,19) card initially. Is it possible to obtain a) (1,50)? b) (1,100)? c) Suppose there was (a,b) card initially (a3. Consider the set M of the pairs (x,y) with the integer coordinates in the plane such that 0 <= x < p; 0 <= y < p. Prove that it is possible to mark p points of M such that not a triple of marked points will belong to one line and there will be no parallelogram with the vertices in the marked points. 266. Prove that for every tetrahedron there exist two planes such that the projection areas on those planes relation is not less than sqrt(2). 267. Given a_1, a_2, ... , a_n. Define b_k = (a_1 + a_2 + ... + a_k)/k for 1 <= k <= n. Let C = (a_1 - b_1)**2 + (a_2 - b_2)**2 + ... + (a_n - b_n)**2; D = (a_1 - b_n)**2 + (a_2 - b_n)**2 + ... + (a_n - b_n)**2. Prove that C <= =0, y>=0 of the coordinate plane (that means that it cannot land in the point with negative coordinate). If it is in the point (x,y), it can either jump to the point (x+1,y-1), or to the point (x-5,y+7). Draw a set of such an initial points (x,y), that having started from there, a grasshopper cannot reach any point farther than 1000 from the point (0,0). Find its area. 271. Every member of a certain parliament has not more than 3 enemies. Prove that it is possible to divide that parliament onto two subparliaments so, that everyone will have not more than one enemy in his subparliament. (A is the enemy of B if and only if B is the enemy of A.) 272. Some numbers are written in the notebook. We can add to that list the arithmetic mean of some of them, if it doesn't equal to the number, already having been included in it. Let us start with two numbers, 0 and 1. Prove that it is possible to obtain a) 1/5; b) an arbitrary rational number between 0 and 1. 273. For every n the decreasing sequence {x_k} satisfies a condition x_4 x_9 x_{n**2} x_1 + --- + --- + ... + -------- <= 1. 2 3 n Prove that for every n it also satisfy x_2 x_3 x_n x_1 + --- + --- + ... + --- <= 3. 2 3 n 274. Given some points in the plane. For some pairs A,B the vector AB is chosen. For every point the number of the chosen vectors starting in that point equal to the number of the chosen vectors ending in that point. Prove that the sum of the chosen vectors equals to zero vector. 275. What is the least possible number of the checkers being required a) for the 8x8 chessboard; a) for the nxn chessboard; to provide the property: Every line (of the chessboard fields) parallel to the side or diagonal is occupied by at least one checker? 276. Find x and y (a and b parameters): x - y*sqrt(x**2 - y**2) y - x*sqrt(x**2 - y**2) ----------------------- = a; ----------------------- = b. sqrt(1 - x**2 + y**2) sqrt(1 - x**2 + y**2) 277. Given some square carpets with the total area 4. Prove that they can fully cover the unit square. 278. Prove that for the arbitrary numbers x_1, x_2, ... , x_n from the [0,1] segment (x_1 + x_2 + ... + x_n + 1)**2 >= >= 4({x_1}**2 + {x_2}**2 + ... + {x_n}**2). 279. Natural p and q are relatively prime. The [0,1] is divided onto (p+q) equal segments. Prove that every segment except two marginal contain exactly one from the (p+q-2) numbers {1/p, 2/p, ... , (p-1)/p, 1/q, 2/q, ... , (q-1q)}. 280. Given the point O in the space and 1979 straight lines l_1, l_2, ... , l_{1979} containing it. Not a pair of lines is orthogonal. Given a point A_1 on l_1 that doesn't coincide with O. Prove that it is possible to choose the points A_i on l_i (i = 2, 3, ... , 1979) in such a way that 1979 pairs A_1A_3 and l_2; A_2A_4 and l_3; .......... A_{i-1}A_{i+1} and l_i; .......... A_{1977}A_{1979} and l_{1978}; A_{1978}A_1 and l_{1979}; A_{1979}A_2 and l_1 will be orthogonal. 281. The finite sequence a_1, a_2, ... , a_n of ones and zeroes should satisfy a condition: for every k from 0 to (n-1) the sum a_1a_{k+1} + a_2a_{k+2} + ... + a_{n-k}a_n should be odd. a) Build such a sequence for n=25. b) Prove that there exists such a sequence for some n > 1000. 282. The convex quadrangle is divided by its diagonals onto four triangles. The circles inscribed in those triangles are equal. Prove that the given quadrangle is a diamond. 283. Given n points (in sequence) A_1, A_2, ... , A_n on a line. All the segments A_1A_2, A_2,A_3, ... A_{n-1}A_n are shorter than 1. We need to mark (k-1) points so that the difference of every two segments, with the ends in the marked ponts, is shorter than 1. Prove that it is possible a) for k=3; b) for every k less than (n-1). The 14-th competition -- Saratov, 1980. form first day second day 8 284 285 286 287 | 293 294 295 296 9 288 289 286 290 | 295 297 298 299 10 291 289 292 290 | 300 301 302 303 284. All the two-digit numbers from 19 to 80 are written in a line without spaces. Is the obtained number (192021....7980) dividable by 1980? 285. The vertical side of a square is divided onto n segments. The sum of the segments with even numbers lengths equals to the sum of the segments with odd numbers lengths. (n-1) lines parallel to the horizontal sides are drawn from the segments ends, and, thus, n strips are obtained. The diagonal is drawn from the lower left corner to the upper right one. This diagonal divides every strip onto left and right parts. Prove that the sum of the left parts of odd strips areas equals to the sum of the right parts of even strips areas. 286. The load for the space station "Salut" is packed in containers. There are more than 35 containers, and the total weight is 18 metric tons. There are 7 one-way transport spaceships "Progress", each able to bring 3 metric tons to the station. It is known that they are able to take an arbitrary subset of 35 containers. Prove that they are able to take all the load. 287. The points M and P are the middles of BC and CD sides of a convex quadrangle ABCD. It is known that |AM| + |AP| = a. Prove that the ABCD area is less than {a**2}/2. 288. Are there three simple numbers x,y,z, such that x**2 + y**3 = z**4? 289. Given a point E on the diameter AC of the certain circle. Draw a chord BD to maximize the area of the quadrangle ABCD. 290. There are several settlements on the bank of the Big Round Lake. Some of them are connected with the regular direct ship lines. Two settlements are connected if and only if two next (counterclockwise) to each ones are not connected. Prove that You can move from the arbitrary settlement to another arbitrary settlement, having used not more than three ships. 291. The six-digit decimal number contains six different non-zero digits and is dividable by 37. Prove that having transposed its digits You can obtain at least 23 more numbers dividable by 37. 292. Find real solutions of the system sin x + 2 sin(x+y+z) = 0, sin y + 3 sin(x+y+z) = 0, sin z + 4 sin(x+y+z) = 0. 293. Given 1980 vectors in the plane, and there are some non-collinear among them. The sum of every 1979 vectors is collinear to the vector not included in that sum. Prove that the sum of all vectors equals to the zero vector. 294. Let us denote with S(n) the sum of all the digits of n. a) Is there such an n that n + S(n) = 1980? b) Prove that at least one of two arbitrary successive natural numbers is representable as n + S(n) for some third number n. 295. Some squares of the infinite sheet of cross-lined paper are red. Each 2x3 rectangle (of 6 squares) contains exactly two red squares. How many red squares can be in the 9x11 rectangle of 99 squares? 296. An epidemic influenza broke out in the elves city. First day some of them were infected by the external source of infection and nobody later was infected by the external source. The elf is infected when visiting his ill friend. In spite of the situation every healthy elf visits all his ill friends every day. The elf is ill one day exactly, and has the immunity at least on the next day. There is no graftings in the city. Prove that a) If there were some elves immunized by the external source on the first day, the epidemic influenza can continue arbitrary long time. b) If nobody had the immunity on the first day, the epidemic influenza will stop some day. 297. Let us denote with P(n) the product of all the digits of n. Consider the sequence n_{k+1} = n_k + P(n_k). Can it be unbounded for some n_1 ? 298. Given equilateral triangle ABC. Some line, parallel to AC crosses AB and BC in M and P points respectively. Let D be the centre of PMB triangle, E - the middle of the AP segment. Find the angles of DEC triangle. 299. Let the edges of rectangular parallelepiped be x,y and z (x -(- + sqrt(d**2 - -)). 3 4 2 3 4 2 300. The A set consists of integers only. Its minimal element is 1 and its maximal element is 100. Every element of A ecxept 1 equals to the sum of two (may be equal) numbers being contained in A. What is the least possible number of elements in A? 301. Prove that there is an infinite number of such numbers B that the equation [x**{3/2}] + [y**{3/2}] = B has at least 1980 integer solutions (x,y). ([z] denotes the greatest integer not exceeding z.) 302. The edge [AC] of the tetrahedron ABCD is orthogonal to [BC], and [AD] is orthogonal to [BD]. Prove that the cosine of the angle between (AC) and (BD) lines is less than |CD|/|AB|. 303. The number x from [0,1] is written as an infinite decimal fraction. Having rearranged its first five digits after the point we can obtain another fraction that corresponds to the number x_1. Having rearranged five digits of x_k from (k+1)-th till (k+5)-th after the point we obtain the number x_{k+1}. a) Prove that the sequence x_i has limit. b) Can this limit be irrational if we have started with the rational number? c) Invent such a number, that always produces irrational numbers, no matter what digits were transposed. The 15-th competition -- Alma-Ata, 1981. form first day second day 8 304 305 306 307 | 315 316 317 318 9 308 309 310 311 | 319 320 321 322 10 311 312 312 314 | 323 324 325 326 304. Two equal chessboards (8x8) have the same centre, but one is rotated by 45 degrees with respect to another. Find the total area of black fields intersection, if the fields have unit length sides. 305. Given points A,B,M,N on the circumference. Two chords [MA_1] and [MA_2] are orthogonal to (NA) and (NB) lines respectively. Prove that (AA_1) and (BB_1) lines are parallel. 306. Let us say, that a natural number has the property P(k) if it can be represented as a product of k succeeding natural numbers greater than 1. a) Find k such that there exists n which has properties P(k) and P(k+2) simultaneously. b) Prove that there is no number having properties P(2) and P(4) simultaneously. 307. The rectangular table has four rows. The first one contains arbitrary natural numbers (some of them may be equal). The consecutive lines are filled according to the rule: we look through the previous row from left to the certain number n and write the number k if n was met k times. Prove that the second row coincides with the fourth one. 308. Given real a. Find the least possible area of the rectangle with the sides parallel to the coordinate axes and containing the figure determined by the system of inequalities y <= -x**2, y >= x**2 - 2x + a. /* as there is no derivatives in the school program of the 9-th form, the participants had to use parabola properties -VAP */ 309. Three equilateral triangles ABC, CDE, EHK (the vertices are mentioned counterclockwise) are lying in the plane so, that the vectors AD and DK are equal. Prove that the triangle BHD is also equilateral. 310. There are 1000 inhabitants in a settlement. Every evening every inhabitant tells all his friends all the news he had heard the previous day. Every news becomes finally known to every inhabitant. Prove that it is possible to choose 90 of inhabitants so, that if You tell them a news simultaneously, it will be known to everybody in 10 days. 311. It is known about real a and b that the inequality a cos(x) + b cos(3x) > 1 has no real solutions. Prove that |b| <=1. 312. The points K and M are the centres of the AB and CD sides of the convex quadrangle ABCD. The points L and M belong to two other sides and KLMN is a rectangle. Prove that KLMN area is a half of ABCD area. 313. Find all the sequences of natural k_n with two properties: for all n k_n <= n sqrt(n); for all m>n (k_n - k_m) is dividable by (m-n). 314. Is it possible to fill a rectangular table with black and white squares (only) so, that the number of black squares will equal to the number of white squares, and each row and each column will have more than 75% squares of the same color? 315. The quadrangles AMBE, AHBT, BKXM, and CKXP are parallelograms. Prove that the quadrangle ABTE is also parallelogram. (the vertices are mentioned counterclockwise) 316. Find the natural solutions of the equation x**3 - y**3 = xy + 61. 317. Eighteen soccer teams have played 8 tours of a one-round tournament. Prove that there is a triple of teams, having not met each other yet. 318. The points C_1, A_1, B_1 belong to [AB], [BC], [CA] sides, respectively, of the ABC triangle. |AC_1| |BA_1| |CB_1| 1 ------ = ------ = ------ = -. |C_1B| |A_1C| |B_1A| 3 Prove that the perimeter P of the ABC triangle and the perimeter p of the A_1B_1C_1 triangle satisfy inequality P/2 < p < 3P/4. 319. Positive numbers x,y satisfy equality x**3 + y**3 = x - y. Prove that x**2 + y**2 < 1. 320. A pupil has tryed to make a copy of a convex polygon, drawn inside the unit circle. He draw one side, from its end -- another, and so on. Having finished, he has noticed that the first and the last vertices do not coincide, but are situated d units of length far from each other. The pupil draw angles precisely, but made relative error less than p in the lengths of sides. Prove that d < 4p. 321. A number is written in the each vertex of a cube. It is allowed to add one to two numbers written in the ends of one edge. Is it possible to obtain the cube with all equal numbers if the numbers were initially as on the pictures: 0-------0 7-------4 0-------1 /| /| /| /| /| /| 0-------0 | 6-------5 | 1-------0 | | | | | | | | | | | | | | 0-----|-1 | 2-----|-3 | 0-----|-0 |/ |/ |/ |/ |/ |/ 0-------0 1-------4 0-------0 fig.a fig.b fig.c 322. Find at least one n such that each of the numbers n, (n+1), ..., (n+20) has the common divider greater than one with the number 30030 = 2*3*5*7*11*13. 323. The natural numbers from 100 to 999 are written on separate cards. They are gathered in one pile with their numbers down in arbitrary order. Let us open them in sequence and divide into 10 piles according to the least significant digit. The first pile will contain cards with 0 at the end, ... , the tenth -- with 9. Then we shall gather 10 piles in one pile, the first -- down, then the second, ... and the tenth -- up. Let us repeat the procedure twice more, but the next time we shall divide cards according to the second digit, and the last time -- to the most significant one. What will be the order of the cards in the obtained pile? 324. Six ponts are marked inside the 3x4 rectangle. Prove that there is a pair of marked points with the distance between them not greater than sqrt(5). 325. a) Find the minimal value of the polynomial P(x,y) = 4 + (x**2)(y**4) + (x**4)(y**2) - 3(x**2)(y**2) /* the usage of derivatives is forbidden, as they were not included in the school programs -- VAP */ b) Prove that it cannot be represented as a sum of the squares of some polynomials of x,y. 326. The segments [AD], [BE] and [CF] are the side edges of the _right_ triangle prism.(I mean, that the equilateral triangle is a base -- VAP) Find all the points in its base ABC, situated on the equal distances from the (AE), (BF) and (CD) lines. ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ < ____/| Vladimir A. Pertsel > < \ o.O| > < =(_)= E-mail: voldemar@wisdom.weizmann.ac.il > < U > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^