Mathematical Olympiad In China : Problems And Solutions

MathematicalBlympiadin ChinaProblems and Solutions

This page intentionally left blank

MathematicalOlympiadin ChinaProblems and SolutionsEditorsXiong BinEast China Normal University, ChinaLee Peng YeeNanyang Technological University, SingaporeEast China NormalUniversity PressWorld Scientific

EditorsXIONG Bin East China o r m a lUniversity, ChinaLEE Peng Yee Nanpng Technological University, SingaporeOriginal AuthorsMO Chinese National Coaches Team of2003 - 2006English TranslatorsXIONG Bin East China N O T T UUniversity,Z ChinaFENG Zhigang shanghai High School, ChinaMA Guoxuan h s t China Normal University, ChinaLIN Lei East China ormalUniversity, ChinaWANG Shanping East China Normal university, ChinaZ m N G Zhongyi High School Affiliated to Fudan University, ChinaHA0 Lili Shanghai @baa Senior High School, ChinaWEE Khangping Nanpng Technological University, singuporeCopy EditorsNI Mingm t China NO UniversityZpress, ChinaZ M G Ji World Scientific Publishing GI., Singaporexu Jin h s t China Normal Universitypress, ChinaV

This page intentionally left blank

PrefaceThe first time China sent a team to IMO was in 1985. At that time, twostudents were sent to take part in the 26th IMO. Since 1986, China hasalways sent a team of 6 students to IMO except in 1998 when it was held in%wan. So far (up to 2006) , China has achieved the number one ranking inteam effort for 13 times. A great majority of students have received goldmedals. The fact that China achieved such encouraging result is due to, onone hand, Chinese students’ hard working and perseverance, and on the otherhand, the effort of teachers in schools and the training offered by nationalcoaches. As we believe, it is also a result of the educational system in China,in particular, the emphasis on training of basic skills in science education.The materials of this book come from a series of four books (inChinese) on Forurzrd to IMO: a collection of mathematical Olympiadproblems (2003 - 2006). It is a collection of problems and solutions of themajor mathematical competitions in China, which provides a glimpse onhow the China national team is selected and formed. First, it is the ChinaMathematical Competition, a national event, which is held on the secondSunday of October every year. Through the competition, about 120students are selected to join the China Mathematical Olympiad (commonlyknown as the Winter Camp) , or in short CMO, in January of the secondyear. CMO lasts for five days. Both the type and the difficulty of theproblems match those of IMO. Similarly, they solve three problems everyday in four and half hours. From CMO, about 20 to 30 students areselected to form a national training team. The training lasts for two weeksin March every year. After six to eight tests, plus two qualifyingvii

viiiMathematical Olympiad in Chinaexaminations, six students are finally selected to form the national team, totake part in IMO in July that year.Because of the differences in education, culture and economy ofWest China in comparison with East China, mathematicalcompetitions in the west did not develop as fast as in the east. Inorder to promote the activity of mathematical competition there,China Mathematical Olympiad Committee conducted the ChinaWestern Mathematical Olympiad from 2001. The top two winners willbe admitted to the national training team. Through the ChinaWestern Mathematical Olympiad, there have been two students whoentered the national team and received Gold Medals at IMO.Since 1986, the china team has never had a female student. Inorder to encourage more female students to participate in themathematical competition, starting from 2002, China MathematicalOlympiad Committee conducted the China Girls’ mathematicalOlympiad. Again, the top two winners will be admitted directly intothe national training team.The authors of this book are coaches of the China national team.They are Xiong Bin, Li Shenghong, Chen Yonggao , Leng Gangsong,Wang Jianwei, Li Weigu, Zhu Huawei, Feng Zhigang, WangHaiming, Xu Wenbin, Tao Pingshen, and Zheng Chongyi. Thosewho took part in the translation work are Xiong Bin, Feng Zhigang,Ma Guoxuan, Lin Lei, Wang Shanping, Zheng Chongyi, and HaoLili. We are grateful to Qiu Zhonghu, Wang Jie, Wu Jianping, andPan Chengbiao for their guidance and assistance to authors. We aregrateful to Ni Ming and Xu Jin of East China Normal UniversityPress. Their effort has helped make our job easier. We are alsograteful to Zhang Ji of World Scientific Publishing for her hard workleading to the final publication of the book.AuthorsMarch 2007

IntroductionEarly daysThe International Mathematical Olympiad (IMO) , founded in 1959,is one of the most competitive and highly intellectual activities in theworld for high school students.Even before IMO, there were already many countries which hadmathematics competition. They were mainly the countries in EasternEurope and in Asia. In addition to the popularization of mathematicsand the convergence in educational systems among differentcountries, the success of mathematical competitions at the nationallevel provided a foundation for the setting-up of IMO. The countriesthat asserted great influence are Hungary, the former Soviet Unionand the United States. Here is a brief review of the IMO andmathematical competition in China.In 1894, the Department of Education in Hungary passed amotion and decided to conduct a mathematical competition for thesecondary schools. The well-known scientist, 1. volt Etovos , was theMinister of Education at that time. His support in the event had madeit a success and thus it was well publicized. In addition, the success ofhis son, R . volt Etovos , who was also a physicist , in proving theprinciple of equivalence of the general theory of relativity by A .Einstein through experiment, had brought Hungary to the world stagein science. Thereafter, the prize for mathematics competition inHungary was named “Etovos prize”. This was the first formallyorganized mathematical competition in the world. In what follows,

XMathematical Olympiad in ChinaHungary had indeed produced a lot of well-known scientists includingL. Fejer, G. Szego, T . Rado, A . Haar and M . Riesz (in realanalysis), D. Konig ( in combinatorics) , T. von Kdrmdn ( inaerodynamics) , and 1. C. Harsanyi (in game theory, who had alsowon the Nobel Prize for Economics in 1994). They all were thewinners of Hungary mathematical competition. The top scientificgenius of Hungary, 1. von Neumann, was one of the leadingmathematicians in the 20th century. Neumann was overseas while thecompetition took place. Later he did it himself and it took him halfan hour to complete. Another mathematician worth mentioning is thehighly productive number theorist P. Erdos. He was a pupil of Fejerand also a winner of the Wolf Prize. Erdos was very passionate aboutmathematical competition and setting competition questions. Hiscontribution to discrete mathematics was unique and greatlysignificant. The rapid progress and development of discretemathematics over the subsequent decades had indirectly influenced thetypes of questions set in IMO. An internationally recognized prizenamed after Erdos was to honour those who had contributed to theeducation of mathematical competition. Professor Qiu Zonghu fromChina had won the prize in 1993.In 1934, B. Delone, a famous mathematician, conducted amathematical competition for high school students in Leningrad (nowSt. Petersburg). In 1935, Moscow also started organizing such event.Other than being interrupted during the World War II , these eventshad been carried on until today. As for the Russian MathematicalCompetition ( later renamed as the Soviet MathematicalCompetition) , it was not started until 1961. Thus, the former SovietUnion and Russia became the leading powers of MathematicalOlympiad. A lot of grandmasters in mathematics including A . N.Kolmogorov were all very enthusiastic about the mathematicalcompetition. They would personally involve in setting the questionsfor the competition. The former Soviet Union even called it theMathematical Olympiad, believing that mathematics is the

Introductionxi“gymnastics of thinking”. These points of view gave a great impact onthe educational community. The winner of the Fields Medal in 1998,M. Kontsevich, was once the first runner-up of the RussianMathematical Competition. G . Kasparov , the international chessgrandmaster, was once the second runner-up. Grigori Perelman , thewinner of the Fields Medal in 2006, who solved the Poincare’sConjecture, was a gold medalist of IMO in 1982.In the United States of America, due to the active promotion bythe renowned mathematician Birkhoff and his son, together with G .Polya , the Putnam mathematics competition was organized in 1938for junior undergraduates. Many of the questions were within thescope of high school students. The top five contestants of the Putnammathematical competition would be entitled to the membership ofPutnam. Many of these were eventually outstanding mathematicians.There were R . Feynman (winner of the Nobel Prize for Physics,1965), K . Wilson (winner of the Nobel Prize for Physics, 1982), 1.Milnor (winner of the Fields Medal, 1962), D. Mumford (winner ofthe Fields Medal, 1974), D. Quillen (winner of the Fields Medal,1978), et al.Since 1972, in order to prepare for the IMO, the United States ofAmerican Mathematical Olympiad ( USAMO) was organized. Thestandard of questions posed was very high, parallel to that of theWinter Camp in China. Prior to this, the United States had organizedAmerican High School Mathematics Examination (AHSME) for thehigh school students since 1950. This was at the junior level yet themost popular mathematics competition in America. Originally, it wasplanned to select about 100 contestants from AHSME to participate inUSAMO. However, due to the discrepancy in the level of difficultybetween the two competitions and other restrictions, from 1983onwards, an intermediate level of competition, namely, AmericanInvitational Mathematics Examination ( AIME ) , was introduced.Henceforth both AHSME and AIME became internationally wellknown. A few cities in China had participated in the competition and