Zlib - Pub Mathematical Olympiad in China 2009 2010 Problems and Solutions

Mathematical
®lympiad
in China (2009-2010)
Problems and Solutions
Mathematical Olympiad Series
ISSN: 1793·8570
Series Editors: Lee Peng Yee (Nanyang Techrwlogical University, Singapore)

Xiong Bin (East China Normal University, China)
Published
Vol. 1 A First Step to Mathematical Olympiad Problems

by Derek Holton (University of Otago, New Zealand)
Vol. 2 Problems of Number Theory in Mathematical Competitions

by Yu Hong-Bing (Suzhou University, China)
translated by Lin Lei (East China Normal University, China)
Vol. 3 Graph Theory

by Xiong Bin (East China Normal University, China) &
Zheng Zhongyi (High School Attached to Fudan University, China)
translated by Liu Ruifang, Zhai Mingqing & Lin Yuanqing
(East China Normal University, China)
Vol. 4 Combinatorial Problems in Mathematical Competitions

by Yao Zhang (Hunan Normal University, P. R. China)
Vol. 5 Selected Problems of the Vietnamese Olympiad (1962-2009)

by Le Hai Chau (Ministry of Education and Training, Vietnam)
& Le Hai Kiwi (Nanyang Technology University, Singapore)
Vol. 6 Lecture Notes on Mathematical Olympiad Courses:

For Junior Section (In 2 Volumes)
byXuJiagu
Vol. 7 A Second Step to Mathematical Olympiad Problems

by Derek Holton (University of Otago, New Zealand &
University of Melbourne, Australia)
Vol. 8 Lecture Notes on Mathematical Olympiad Courses:

For Senior Section (In 2 Volumes)
byXuJiagu
Vol. 9 Mathemaitcal Olympiad in China (2009-2010)

edited by Bin Xiong (East China Normal University, China) &
Peng Yee Lee (Nanyang Technological University, Singapore)
Mathematical
®lympiad
in China (2009-2010)
Problems and Solutions
Editors
Xiong Bin
East China Normal University, China
Lee PengYee
Nanyang Technological University, Singapore
- East China Normal

~ University Press 11» World Scientific
Published by
World Scientific Publishing Co. Pte. Ltd.
5 Toh Tuck Link, Singapore 596224
USA office: 27 Warren Street, Suite 401-402, Hackensack, NJ 07601
UK office: 57 Shelton Street, Covent Garden, London WC2H 9HE
British Library Cataloguing-in-Publication Data

A catalogue record for this book is available from the British Library.
Mathematical Olympiad Series- Vol. 9

MATHEMATICAL OLYMPIAD IN CHINA (2009-2010)
Problems and Solutious
Copyright@ 2013 by World Scientific Publishing Co. Pte. Ltd.
AU rights reserved. This book, or parts thereof. may not be reproduced ill any form or by any means,
electronic or mechanical, including photocopying, recording or any information storage and retrieval
system now known or to be invented, without written permission from the Publisher.
For photocopying of material in this volume, please pay a copying fee through the Copyright
Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, USA. In this case permission to
photocopy is not required from the publisher.
ISBN 978-981-4390-21-7 (pbk)
Printed in Singapore by World Scientific Printers.

Editors
XIONG Bin East China Normal Unill6sity, China
Lee Peng y ee Nanyang Technological University
Original Authors
MO Chinese National Coaches of
2009- 2010
English Translators
XIONG Bin East China Normal Unill6sity, China
FENG Zhigang Shanghai High School, China
WANG Shanping East China Normal Univenity, China
Yao Yijun Fudan Uniw:rsity, China
Qu Zhenhua East China Normal University, China
Copy Editors
Nl Ming East China Normal Uniw:rsity press, China
ZHANG Ji World Scientific Publishing Co., Singapore
WONG Fook Sung Temasek Polytechnic , Singapore
KONG Lingzhi East China Normal Unill6sity press , China

This page intentionally left blank
Preface
The first time China participate in IMO was in 1985, two

students were sent to the 26th IMO. Since 1986, China has a
team of 6 students at every IMO except in 1998 when it was held
in Taiwan. So far, up to 2011, China has achieved the number
one ranking in team effort 17 times. A great majority of
students received gold medals. The fact that China obtained
such encouraging result is due to, on one hand, Chinese
students' hard working and perseverance, and on the other
hand, the effort of teachers in schools and the training offered
by national coaches. As we believe, it is also a result of the
education 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 two books
(in Chinese) on Forward to IMO= a collection of math£matical
Olympiad problems (2009 - 2010). It is a collection of problems
and solutions of the major mathematical competitions in China.
It provides a glimpse of how the China national team is selected
and formed. First, there is the China Mathematical
Competition, a national event. It is held on the second Sunday
of October every year. Through the competition, about 200
students are selected to join the China Mathematical Olympiad
(commonly known as the winter camp), or in short CMO, in
vii
Mathematical Olympiad in Chirw
the next January. CMO lasts for five days. Both the type and
the difficulty of the problems match those of IMO. Similarly,
students are given three problems to solve in 4. 5 hours each
day. From CMO, about 50 to 60 students are selected to form a
national training team. The training takes place for two weeks
in the month of March. After four to six tests, plus two
qualifying examinations, six students are finally selected to
form the national team, taking part in IMO in July of that
year.
In view of the differences in education, culture and
economy of western part of China in comparison with the coast
part in east China, mathematical competitions in West China
did not develop as fast as in the rest of the country. In order to
promote the activity of mathematical competition, and to
enhence the level of mathematical competition, starting from
2001, China Mathematical Olympiad Committee organizes the
China Western Mathematical Olympiad. The top two winners
will be admitted to the national training team. Through the
CWMO, there have been two students entering the national
team and receiving gold medals for their performance at IMO.
Since 1995, for a quite long period there was no female
student in the Chinese national team. In order to encourage
more female students participating in the mathematical
competition, starting from 2002, China Mathematical
Olympiad Committee conducted the China Girls' Mathematical
Olympiad. Again, the top two winners will be admitted directly
into the national training team. In 2007, the first girl who was
winner of China Girls' Mathematical Olympiad was selected to
enter the 2008 China national team and won the gold medal of
the 49th IMO.
Preface ix
The authors of this book are coaches of the China national

team. They are Xiong Bin, Li Shenghong, Leng Gangsong, Wu
Jianping, Chen Yonggao, Li Weigu, Yu Hongbing, Zhu
Huawei, Feng Zhigang, Liu Shixiong, Qu Zhenhua, Wang
Weiye, and Zhang Sihui. Those who took part in the
translation work are Xiong Bin, Feng Zhigang, Wang
Shanping, Yao Yijun, and Qu Zhenhua. We are grateful to Qiu
Zonghu, Wang Jie, Wu Jianping, and Pan Chengbiao for their
guidance and assistance to authors. We are grateful toNi Ming
of East China Normal University Press. Their effort has helped
make our job easier. We are also grateful to He Yue of World
Scientific Publishing for her hard work leading to the final
publication of the book.
Authors
October 2011
Introduction
Early days
The International Mathematical Olympiad CIMO), founded in
1959, is one of the most competitive and highly intellectual
activities in the world for high school students.
Even before IMO, there were already many countries
which had mathematics competition. They were mainly the
countries in Eastern Europe and in Asia. In addition to the
popularization of mathematics and the convergence in
educational systems among different countries, the success of
mathematical competitions at the national level provided a
foundation for the setting-up of IMO. The countries that
asserted great influence are Hungary, the former Soviet Union
and the United States. Here is a brief review of the IMO and
mathematical competition in China.
In 1894, the Department of Education in Hungary passed a
motion and decided to conduct a mathematical competition for
the secondary schools. The well-known scientist, J. von
Etovos , was the Minister of Education at that time. His support
in the event had made it a success and thus it was well
publicized. In addition, the success of his son, R. von Etovos,
who was also a physicist, in proving the principle of equivalence
of the general theory of relativity by A. Einstein through
xi
xii Mathematical Olympiad in Chirw
experiment, had brought Hungary to the world stage in science.

Thereafter, the prize for mathematics competition in Hungary
was named " Etovos prize". This was the first formally
organized mathematical competition in the world. In what
follows, Hungary had indeed produced a lot of well-known
scientists including L. Fejer, G. Szego, T. RadO, A. Haar
and M. Riesz (in real analysis) • D. Konig (in combinatorics) ,
T . von Karman (in aerodynamics) , and J. C. Harsanyi (in
game theory), who had also won the Nobel Prize for Economics
in 1994. They all were the winners of Hungary mathematical
competition. The top scientific genius of Hungary, J. von
Neumann, was one of the leading mathematicians in the 20th
century. Neumann was overseas while the competition took
place. Later he did it himself and it took him half an hour to
complete. Another mathematician worth mentioning is the
highly productive number theorist P. Erdos. He was a pupil of
Fejer and also a winner of the Wolf Prize. Erdos was very
passionate about mathematical competition and setting
competition questions. His contribution to discrete mathematics
was unique and greatly significant. The rapid progress and
development of discrete mathematics over the subsequent
decades had indirectly influenced the types of questions set in
IMO. An internationally recognized prize named after Erdos
was to honour those who had contributed to the education of
mathematical competition. Professor Qiu Zonghu from China
had won the prize in 1993.
In 1934, a famous mathematician B. Delone conducted a
mathematical competition for high school students in Leningrad
(now St. Petersburg). In 1935, Moscow also started organizing
such event. Other than being interrupted during the World War
Introduction xiii
II , these events had been carried on until today. As for the

Russian Mathematical Competition (later renamed as the Soviet
Mathematical Competition), it was not started until 1961.
Thus, the former Soviet Union and Russia became the leading
powers of Mathematical Olympiad. A lot of grandmasters in
mathematics including the great A. N. Kolmogorov were all
very enthusiastic about the mathematical competition. They
would personally involve in setting the questions for the
competition. The former Soviet Union even called it the
Mathematical Olympiad, believing that mathematics is the
"gymnastics of thinking". These points of view gave a great
impact on the educational community. The winner of the Fields
Medal in 1998, M. Kontsevich, was once the first runner-up of
the Russian Mathematical Competition. G. Kasparov, the
international chess grandmaster, was once the second runner-
up. Grigori Perelman, the winner of the Fields Medal in 2006
(but he declined), who solved the Poincare's Conjecture, was a
gold medalist of IMO in 1982.
In the United States of America, due to the active
promotion by the renowned mathematician G. D. Birkhoff and
his son, together with G. Polya, the Putnam mathematics
competition was organized in 1938 for junior undergraduates.
Many of the questions were within the scope of high school
students. The top five contestants of the Putnam mathematical
competition would be entitled to the membership of Putnam.
Many of these were eventually outstanding mathematicians.
There were the famous R . Feynman (winner of the Nobel Prize
for Physics, 1965), K. Wilson (winner of the Nobel Prize for
Physics, 1982), J. Milnor (winner of the Fields Medal, 1962),
D. Mumford (winner of the Fields Medal, 1974), and D.
xiv Mathematical Olympiad in Chirw
Quillen (winner of the Fields Medal, 1978).

Since 1972, in order to prepare for the IMO, the United
States of America Mathematical Olympiad ( USAMO) was
organized. The standard of questions posed was very high,
parallel to that of the Winter Camp in China. Prior to this, the
United States had organized American High School
Mathematics Examination ( AHSME) for the high school
students since 1950. This was at the junior level yet the most
popular mathematics competition in America. Originally, it was
planned to select about 100 contestants from AHSME to
participate in USAMO. However, due to the discrepancy in the
level of difficulty between the two competitions and other
restrictions, from 1983 onwards, an intermediate level of
competition, namely, American Invitational Mathematics
Examination ( AIME), was introduced. Henceforth both
AHSME and AIME became internationally well-known. A few
cities in China had participated in the competition and the
results were encouraging.
The members of the national team who were selected from
USAMO would undergo training at the West Point Military
Academy, and would meet the President at the White House
together with their parents. Similarly as in the former Soviet
Union, the Mathematical Olympiad education was widely
recognized in America. The book "How to Solve it" written by
George Polya along with many other titles had been translated
into many different languages. George Polya provided a whole
series of general heuristics for solving problems of all kinds. His
influence in the educational community in China should not be
underestimated.
Introduction XV
International Mathematical Olympiad

In 1956, the East European countries and the Soviet Union took
the initiative to organize the IMO formally. The first
International Mathematical Olympiad ( IMO) was held in
Brasov, Romania, in 1959. At the time, there were only seven
participating countries, namely, Romania, Bulgaria, Poland,
Hungary, Czechoslovakia, East Germany and the Soviet
Union. Subsequently, the United States of America, United
Kingdom, France, Germany and also other countries including
those from Asia joined. Today, the IMO had managed to reach
almost all the developed and developing countries. Except in
the year 1980 due to financial difficulties faced by the host
country, Mongolia, there were already 49 Olympiads held and
97 countries participating.
The mathematical topics in the IMO include number
theory, polynomials, functional equations, inequalities, graph
theory, complex numbers, combinatorics, geometry and game
theory. These areas had provided guidance for setting questions
for the competitions. Other than the first few Olympiads, each
IMO is normally held in mid-July every year and the test paper
consists of 6 questions in all. The actual competition lasts for 2
days for a total of 9 hours where participants are required to
complete 3 questions each day. Each question is 7 points which
total up to 42 points. The full score for a team is 252 marks.
About half of the participants will be awarded a medal, where
1/12 will be awarded a gold medal. The numbers of gold , silver
and bronze medals awarded are in the ratio of 1 : 2 : 3
approximately. In the case when a participant provides a better
solution than the official answer, a special award is given.
Each participating country will take turn to host the IMO.
The cost is borne by the host country. China had successfully

hosted the 31st IMO in Beijing. The event had made a great
impact on the mathematical community in China. According to
the rules and regulations of the IMO, all participating countries
are required to send a delegation consisting of a leader, a
deputy leader and 6 contestants. The problems are contributed
by the participating countries and are later selected carefully by
the host country for submission to the international jury set up
by the host country. Eventually, only 6 problems will be
accepted for use in the competition. The host country does not
provide any question. The short-listed problems are
subsequently translated, if necessary, in English, French,
German, Russian and other working languages. After that, the
team leaders will translate the problems into their own
languages.
The answer scripts of each participating team will be
marked by the team leader and the deputy leader. The team
leader will later present the scripts of their contestants to the
coordinators for assessment. If there is any dispute, the matter
will be settled by the jury. The jury is formed by the various
team leaders and an appointed chairman by the host country.
The jury is responsible for deciding the final 6 problems for the
competition. Their duties also include finalizing the grading
standard, ensuring the accuracy of the translation of the
problems, standardizing replies to written queries raised by
participants during the competition, synchronizing differences
in grading between the team leaders and the coordinators and
also deciding on the cut-off points for the medals depending on
the contestants' results as the difficulties of problems each year
are different.
Introduction xvii
China had participated informally in the 26th IMO in 1985.

Only two students were sent. Starting from 1986, except in
1998 when the IMO was held in Taiwan, China had always sent
6 official contestants to the IMO. Today, the Chinese
contestants not only performed outstandingly in the IMO, but
also in the International Physics, Chemistry, Informatics, and
Biology Olympiads. So far, no other countries have overtaken
China in the number of gold and silver medals received. This
can be regarded as an indication that China pays great attention
to the training of basic skills in mathematics and science
education.
Winners of the IMO

Among all the IMO medalists, there were many of them who
eventually became great mathematicians. They were also
awarded the Fields Medal, Wolf Prize and Nevanlinna Prize (a
prominent mathematics prize for computing and informatics).
In what follows, we name some of the winners.
G. Margulis, a silver medalist of IMO in 1959, was
awarded the Fields Medal in 1978. L . Lovasz, who won the
Wolf Prize in 1999, was awarded the Special Award in IMO
consecutively in 1965 and 1966. V. Drinfeld, a gold medalist of
IMO in 1969, was awarded the Fields Medal in 1990. J. -C.
Yoccoz and T. Gowers, who were both awarded the Fields
Medal in 1998, were gold medalists in IMO in 1974 and 1981
respectively. A silver medalist of IMO in 1985, L. Lafforgue,
won the Fields Medal in 2002. A gold medalist of IMO in 1982,
Grigori Perelman from Russia, was awarded the Fields Medal in
2006 for solving the final step of the Poincare conjecture. In
1986, 1987, and 1988, Terence Tao won a bronze, silver, and
gold medal respectively. He was the youngest participant to

date in the IMO, first competing at the age of ten. He was also
awarded the Fields Medal in 2006. Gold medalist of IMO 1988 and
1989, Ngo Bau Olao, won the Fields Medal in 2010, together with
the bronze medalist of IMO 1988, E. Lindenstrauss.
A silver medalist of IMO in 1977, P. Shor, was awarded
the Nevanlinna Prize. A gold medalist of IMO in 1979, A.
Razborov, was awarded the Nevanlinna Prize. Another gold
medalist of IMO in 1986, S. Smirnov, was awarded the Clay
Research Award. V. Lafforgue, a gold medalist of IMO in
1990, was awarded the European Mathematical Society prize.
He is L. Lafforgue's younger brother.
Also, a famous mathematician in number theory, N.
Elkies, who is also a professor at Harvard University, was
awarded a gold medal of IMO in 1982. Other winners include
P. Kronheimer awarded a silver medal in 1981 and R. Taylor a
contestant of IMO in 1980.
Mathematical competition in China

Due to various reasons, mathematical competition m China
started relatively late but is progressing vigorously.
"We are going to have our own mathematical competition
too!" said Hua Luogeng. Hua is a house-hold name in China.
The first mathematical competition was held concurrently in
Beijing, Tianjin, Shanghai and Wuhan in 1956. Due to the
political situation at the time, this event was interrupted a few
times. Until 1962, when the political environment started to
improve, Beijing and other cities started organizing the
competition though not regularly. In the era of Cultural
Revolution, the whole educational system in China was in
Introduction xix
chaos. The mathematical competition came to a complete halt.

In contrast, the mathematical competition in the former Soviet
Union was still on-going during the war and at a time under the
difficult political situation. The competitions in Moscow were
interrupted only 3 times between 1942 and 1944. It was indeed
commendable.
In 1978, it was the spring of science. Hua Luogeng
conducted the Middle School Mathematical Competition for 8
provinces in China. The mathematical competition in China
was then making a fresh start and embarked on a road of rapid
development. Hua passed away in 1985. In commemorating
him, a competition named Hua Luogeng Gold Cup was set up in
1986 for students in Grade 6 and 7 and it has a great impact.
The mathematical competitions in China before 1980 can
be considered as the initial period. The problems set were
within the scope of middle school textbooks. After 1980, the
competitions were gradually moving towards the senior middle
school level. In 1981, the Chinese Mathematical Society
decided to conduct the China Mathematical Competition, a
national event for high schools.
In 1981, the United States of America, the host country of
IMO, issued an invitation to China to participate in the event.
Only in 1985, China sent two contestants to participate
informally in the IMO. The results were not encouraging. In
view of this, another activity called the Winter Camp was
conducted after the China Mathematical Competition. The
Winter Camp was later renamed as the China Mathematical
Olympiad or CMO. The winning team would be awarded the
Chern Shiing-Shen Cup. Based on the outcome at the Winter
Camp, a selection would be made to form the 6-member
national team for IMO. From 1986 onwards, other than the
year when IMO was organized in Taiwan, China had been
sending a 6-member team to IMO. Up to 2011, China had been
awarded the overall team champion for 17 times.
In 1990, China had successfully hosted the 31st IMO. It
showed that the standard of mathematical competition in China
has leveled that of other leading countries. First, the fact that
China achieves the highest marks at the 31st IMO for the team
is an evidence of the effectiveness of the pyramid approach in
selecting the contestants in China. Secondly, the Chinese
mathematicians had simplified and modified over 100 problems
and submitted them to the team leaders of the 35 countries for
their perusal. Eventually, 28 problems were recommended. At
the end, 5 problems were chosen OMO requires 6 problems).
This is another evidence to show that China has achieved the
highest quality in setting problems. Thirdly, the answer scripts
of the participants were marked by the various team leaders and
assessed by the coordinators who were nominated by the host
countries. China had formed a group 50 mathematicians to
serve as coordinators who would ensure the high accuracy and
fairness in marking. The marking process was completed half a
day earlier than it was scheduled. Fourthly, that was the first
ever IMO organized in Asia. The outstanding performance by
China had encouraged the other developing countries, especially
those in Asia. The organizing and coordinating work of the
IMO by the host country was also reasonably good.
In China, the outstanding performance in mathematical
competition is a result of many contributions from the all
quarters of mathematical community. There are the older
generation of mathematicians, middle-aged mathematicians and
Introduction xxi
also the middle and elementary school teachers. There is one

person who deserves a special mention and he is Hua Luogeng.
He initiated and promoted the mathematical competition. He is
also the author of the following books: Beyond Yang hui's
Triangle, Beyond the pi of Zu Chongzhi , Beyond the Magic
Computation of Sun-zi, Mathematical Induction, and
Mathematical Problems of Bee Hive. These were his books
derived from mathematics competitions. When China resumed
mathematical competition in 1978, he participated in setting
problems and giving critique to solutions of the problems. Other
outstanding books derived from the Chinese mathematics
competitions are: Symmetry by Duan Xuefu, Lattice and Area
by Min Sihe , One Stroke Drawing and Postman Problem by
Jiang Boju.
After 1980, the younger mathematicians in China had
taken over from the older generation of mathematicians in
running the mathematical competition. They worked and
strived hard to bring the level of mathematical competition in
China to a new height. Qiu Zonghu is one such outstanding
representative. From the training of contestants and leading the
team 3 times to IMO to the organizing of the 31th IMO in
China, he had contributed prominently and was awarded the P.
Erdos prize.
Preparation for IMO

CUrrently, the selection process of participants for IMO in
China is as follows.
First, the China Mathematical Competition, a national
competition for high Schools, is organized on the second Sunday
in October every year. The objectives are: to increase the
xxii Mathematical Olympiad in Chirw
interest of students in learning mathematics, to promote the

development of co-curricular activities in mathematics, to help
improve the teaching of mathematics in high schools, to
discover and cultivate the talents and also to prepare for the
IMO. This happens since 1981. Currently there are about
200,000 participants taking part.
Through the China Mathematical Competition, around 150
of students are selected to take part in the China Mathematical
Olympiad or CMO, that is, the Winter Camp. The CMO lasts
for 5 days and is held in January every year. The types and
difficulties of the problems in CMO are very much similar to the
IMO. There are also 3 problems to be completed within 4. 5
hours each day. However, the score for each problem is 21
marks which add up to 126 marks in total. Starting from 1990,
the Winter Camp instituted the Chern Shiing-Shen Cup for team
championship. In 1991, the Winter Camp was officially
renamed as the China Mathematical Olympiad CCMO). It is
similar to the highest national mathematical competition in the
former Soviet Union and the United States.
The CMO awards the first, second and third prizes.
Among the participants of CMO, about 20 to 30 students are
selected to participate in the training for IMO. The training
takes place in March every year. After 6 to 8 tests and another
2 rounds of qualifying examinations, only 6 contestants are
short-listed to form the China IMO national team to take part in
the IMO in July.
Besides the China Mathematical Competition (for high
schools), the Junior Middle School Mathematical Competition
is also developing well. Starting from 1984, the competition is
organized in April every year by the Popularization Committee
Introduction xxiii
of the Chinese Mathematical Society. The various provinces,

cities and autonomous regions would rotate to host the event.
Another mathematical competition for the junior middle schools
is also conducted in April every year by the Middle School
Mathematics Education Society of the Chinese Educational
Society since 1998 till now.
The Hua Luogeng Gold Cup, a competition by invitation,
had also been successfully conducted since 1986. The
participating students comprise elementary six and junior middle
one students. The format of the competition consists of a
preliminary round, semifinals in various provinces, cities and
autonomous regions, then the finals.
Mathematical competition in China provides a platform for
students to showcase their talents in mathematics. It encourages
learning of mathematics among students. It helps identify
talented students and to provide them with differentiated
learning opportunity. It develops co-curricular activities in
mathematics. Finally, it brings about changes in the teaching of
mathematics.
Contents
Preface vii
lntrod.Jction xi
China Mathematical Competition 1

2008 ( Chongqing) 1
2009 (Heilongjiang) 17
China Mathematical Competition (Complementary

Test) 29
2008 ( Chongqing) 29
2009 (Heilongjiang) 38
China Mathematical Olympiad 47

2009 (Qionghai, Hainan) 47
2010 (Chongqing) 57
China National Team Selection Test 65

2009 (Wuhan, Hubei) 65
2010 (Yingtan, Jiangxi) 79
China Girls' Mathematical Olympiad 94

2008 (Zhongshan, Guangdong) 94
XXV
xxvi Mathematical Olympiad in Chirw
2009 (Xiamen, Fujian) 106
China Western Mathematical Olympiad 117

2008 (Guiyang, Guizhou) 117
2009 (Kunming, Yunnan) 125
China Southeastern Mathematical Olympiad 137

2009 (Nanchang, Jiangxi) 137
2010 (Changhua, Taiwan) 147
International Mathematical Olympiad 157

2009 (Bremen, Germany) 157
2010 CAstana, Kazakhstan) 168
China Mathematical
Competition
2008
The Popularization Committee of Chinese Methematica Society and
Chongqing Mathematical Society were responsible for the
assignment of the competition problems in the first round test and
the supplementary test.
Part I Multiple-choice Questions (Questions 1--6. six IIUll'ks

each)
Theminimumvalueoff(x) = 5 - 4~;x forx E (-=t

2
2
0
2)is( ).
2 Mathematical Olympiad in China
(A) 0 (B) 1 (C) 2 (D) 3
Solution Let x < 2 => 2 - x > o. Then
f(x) = 1 +(4 -4x +x2) = _1_ +C2 -x)

2 -x 2 -x
~2X J ~X 2 X (2 -X) = 2.
The equality holds if and only if ~ x = 2 - x , and it is so

2
when x = 1 E (- =, 2). This means that f reaches the
minimum value 2 at x = 1.
Answer: C
0 LetA = [ -2, 4), B ={xI x 2 -ax -4 ~0}. If B c:A,

then the range of real a is ( ).
(A) [ -1, 2) (B) [ -1, 2]
(C) [0, 3] (D) [0, 3)
2
Solution x -ax- 4 = 0 has two roots:
We have B c: A~ x1 ~- 2 and xz < 4. This means that
From the above we get 0 ~ a < 3.

Answer: D
8 A and B are playing ping-pong, with the agreement that

the winner of a game will get 1 point and the loser 0 point;
the match ends as soon as one of the players is ahead by 2
points or the number of games reaches six. Suppose that
China Mathernatir:4l Competition 3
the probabilities of A and B winning a game are ~ and
~ , respectively, and each game is independent. Then the

expectation E~ for the match ending with ~ games 1s
( ).
(A) 241 (B) 266 (C) 274 (D) 670

81 81 81 243
Solution I It is easy to see that ~can only be 2, 4 or 6. We
divide the six games into three rounds, each consisting of two
consecutive games. If one of the players wins two games in the
first round, the match ends and the probability is
(1_)2
3
(l)2 = _i9.
+ 3
Otherwise the players tie with each other, earning one point
each, and the match enters the second round; this probability is
5 4
1-9 = 9•
We have similar discussions for the second and third
rounds. So we get
P(~ = 2) = ~,
4 5 20
p (~ = 4) = 9 X 9 = 81 '
p (~ = 6) = ( !) 2 = ~~.
Then
E~ = 2 X _i + 4 X 20 + 6 X 16 = 266
9 81 81 81.
Answer: B
Solution ll Let A~ denote the event that A wins the k th
game, while .A-' means that B wins the game. Since Ai and A-'
are incompatible, and are independent of the other events,
we have
5
PC~= 2) = PCA1Az) +PCA1Az) = g'
PC~ = 4) = PCA1AzA3A4) + PCA1AzAaA4) +
PCA1AzAaA4) + PCA1AzA3A4)
= 2[ ( ~ f (~ )+ ( ~ f (~ )J= ~~ '
P(~ = 6) = PCA1AzA3A4) +PCA1AzAaA4) +
PCA1AzA3A4) + PCA1AzA3A4)
16
8r
Then
E~ = 2 X__§_ + 4 X 20 + 6 X 16 = 266
9 81 81 81.
Answer: B
0 Given three cubes with integer edge lengths, if the sum of

their surface areas is 564 cm2 , then the sum of their
volumes is ( ).
(A) 764 cm or 586 cm3
3
(B) 764 cm3
(C) 586 cm3 or 564 cm3 (D) 586 cm3
Solution Denote the edge lengths of the three cubes as a , b
and c , respectively. Then we have
i.e. a 2 +b 2 +c 2 = 94. We may assume that
1 ~a ~ b ~ c < 10.
Then
It follows that c 2 > 31. So 6 ~ c < 10, and this means that
c can only be 9, 8, 7 or 6.
If c = 9, then
It is easy to see that a = 2, b = 3. So we get the solution

(a, b, c) = (2, 3, 9).
If c = 8, then
a2 +b 2
= 94 - 8 2 = 30.
1his means that b ~ 4 and 2b2 ~ 30; it follows that b = 4 or 5,

so a 2 = 5 or 14; in both cases a has no integer solution.
If c = 7, then
It is easy to see that a = 3, b = 6 is the only solution.

If c = 6, then
So 2b 2 ~ 58, or b 2 ~ 29. This means that b ~ 6, but b ~

2
c = 6, sob = 6. Then a = 22 and a cannot be an integer.
In summary, there are two solutions: (a, b, c) = (2, 3, 9)
and (a, b, c) = (3, 6, 7). Then the possible volumes are
vl = 23 + 33 + 93 = 764 cm3 '

V2 = 33 + 63 + 73 = 586 cm3 •
Answer: A
0 The number of rational solutions to the system of equations

x +y +z = 0,
xyz + z = 0, is ( ) .
{
xy + yz + xz + y = 0
(A) 1 (B) 2 (C) 3 (D) 4
X+ y = 0,
Solution If z = 0, then { It follows that
xy +y = 0.
{xy=O
0, or
= = - 1,
y=l.
{x
If z =I= 0, from xyz +z = 0 we get
xy =-1. CD
Fromx + y +z = 0 we have
z =-x -y.
Substituting ® into xy + yz + xz + y = 0, we obtain
xz + Yz + xy - Y = 0.
From CD we have x =- _!_. We substitute it into

y
®, and
then make a simplification:
(y -1) (y 3 - y - 1) = 0.
It is easy to see that y 3 - y -1 has no rational solution, and

so y = 1. Then from CD and ® we get x =- 1 and z = 0,
contradicting z =I= 0.
In summary, the system has exactly two solutions:
X 0, {X 1,
= =-
{zy = 0,o, yz = 0.1,

= =
Answer: B
0 Suppose that the sides a , b , c of MBC, corresponding

to the angles A, B , C respectively, constitute a geometric
seqreore. Then the range of ~A cot C +cos A is C )
smBcotC +cosB ·
(A) (0, + oo) (B) (o, J5 t1)
(D) ( J5 2-1 ' + =)

Solution Suppose that the common ratio of a , b, c is q.
Thenb = aq, c = aq 2 • We have
sinAcot C +cos A sinAcos C + cosAsin C

sin Bcot C +cos B sin Bcos C +cos Bsin C
sinCA +C) sinC1e- B)
sin(B +C) sin(7C- A)
sinE b
= sin A = -; = q ·
So we only need to determine the range of q. As a , b, c

are the sides of a triangle, they satisfy a + b > c and b + c >a.
That is to say,
a +aq >aq 2 ,
{
aq + aq 2 >a.
It follows that
q2 - q - 1 < o,
{ q 2 +q -1 > 0.
Their solutions are
JS-1 < <-/5+1

2 q 2 '
{
q > JS-1
2 orq <- -/5+1
2 •
It is only possible that
./S-1 < <./5+1

2 q 2 •
Answer: C
Part II Short-Answer Questions (Questions 7-12, nine marks

each)
8 Letf(x) =ax +b, with a, b real nwnbers; !1Cx)
f(x), fn+l(x) = f(f,.(x)), n = 1, 2, •••. If fr(x)
12Bx +381, then a +b = _ __
Solution From the definitions we get
fn (x) = a"x + (a"-1 +a..--2 + ••• +a + 1)b

a" -1
=a"x +--
a -1
Xb.
a 7 -1
As f 7 (x) = 128x +381, we have a 7 = 128 and a _ Xb =
1
381. Then a = 2, b = 3. The answer is a + b = 5.
0 Suppose that the minimwn of f(x) = cos 2x - 2a(l +

cosx) is-~. Then a= _ __
Solution We have
f(x) = 2cos x 2 -1 - 2a - 2acos x
For a > 2, f (x) takes the minimwn value of 1 - 4a when

cos x = 1 ; for a < - 2, f (x) takes the minimwn 1 when cos x =
- 1 ; for - 2 ~ a ~ 2, f (x) takes the minimwn - ~ a 2 - 2a - 1

when cos x = ~. It is easy to see that f (x) will never be - ~

for a > 2 or a <- 2. So it is only possible that -2 ~a ~ 2. Then
from- ~ az -2a -1 = ~, we get a =-2 +../3or a =-2 -../3
(discarded). Therefore, the correct answer is a =- 2 +../3.
0 Twenty-four volunteers will be allocated to three schools.

The rule is that each school will accept at least one
volunteer and all the schools will accept different numbers
of volunteers. Then there are - - - - different ways of
allocating volunteers.
Solution We may use each space between every two consecutive
bars ( I) to represent a school and each asterisk ( * ) to represent a
volunteer, as seen in the following example: the first. second and
third schools receive 4, 18 and 2 volunteers, respectively.
1****1*•••* 1**1
Then the allocation problem may be regarded as a permutation-
and-combination problem of 4 bars and 24 asterisks.
Since the two ends of the line must be occupied by a bar,
23
respectively, there are ( ) = 253 ways to insert the other 2
2
bars into the 23 spaces between the 24 asterisks such that there
is at least 1 asterisk between every two consecutive bars, in
which there are 31 ways that at least two schools have the same
number of volunteers. So the number of allocating ways
satisfying the conditions is 253 - 31 = 222.
4]) Let S,. denote the sum of the first n terms in a number
sequence {a,.}, satisfying
n -1
Sn +a,. = n (n + 1) , n = 1, 2, ···.
Then a,.= - - -
Solution As
n n -I
= (n + I)(n +2) -a..-~-1 - n(n + 1) +a,.'
we have
n + 2-2 I I
2a..-t-l = (n +I)(n +2)- n +I + n(n +I) +a,.
-2 I
(n + l)(n +2) +a,.+ n(n + 1)'
Therefore,
a..-1-1 + (n + I)I(n + 2) = ~ (a,. + n (n I+ 1) ) ·

Define b,. = a,. + n(n 1+ I)' It is easy to see that b,.
I 1
..- h1, b1 =a1+2. Ontheotherhand, fromS1+a1 =2a1 =0
2 1
we geta1 = 0. So b1 = I 1
2 , b,. = ,.. Therefore,
2
1 I I
a,. =b,.- n(n + I)= 2"- n(n +I)'
4]) Suppose that f (x) is defined on R, satisfying j(O)

2008, and for any x E R
f(x + 2) - f(x) ~ 3 X 2-",

f(x +6)- f(x) ~ 63 X 2z.
Then /(2008) = _ __
Solution I We have
f(x +2)- f(x)
=- (f(x +4)- f(x +2))- (f(x +6)
- f(x +4)) +(f(x +6)- f(x))
~- 3 X 2x+-2 - 3 X 2x+t + 63 X 2x = 3 X 2x.
This means that f(x + 2) - f(x) = 3 X 2x. So we have
/(2008) = /(2008) - /(2006) + /(2006) - /(2004) + ...

+ /(2) - /(0) + /(0)
= 3 X (22006 + 22004 + •.. + 22 + 1) + /(0)
4 1003-t-1 -1
= 3X +2008
4-1
= 22008 + 2007.
Solution ll We define g (x) = f (x) - 2x. Then we have

g(x + 2) - g(x) = f(x + 2)- f(x) - 2x+-2 + 2%
-:::;;; 3 X 2x -3 X 2x = 0,
g (x + 6) - g (x) = f (x + 6) - f (x) - 2x+-6 + 2%
~ 63 X 2"' - 63 X 2.r = 0.
This means thatg(x) -:::;;;g(x +6) -:::;;;g(x +4) -:::;;;g(x +2)-:::;;;

g (x) , and it implies that g (x) is a periodic function with 2 as a
period. So
/(2008) = g(2008) +22008 = g(O) +22008
= 2007 + 22008.
Cf) Suppose that a ball with radius 1 moves freely inside a

regular tetrahedron with edge length 4./6. Then the area
of the inner surface of the container, which the ball can
never touch, is - - -
Solution As shown in Fig. 1, consider the situation where the
p
ball is in a corner of the container. Draw
the planeA1B1C1 II ABC, tangent to the
ball at point D. Then the ball center 0 is
also the center of the tetrahedron
P-A1B1C1, with PO ..lA1B1C1 and the
foot point D being the center of M1B1C1. B
Since Fig. I
= 4 X V o-A 1 B 1 c 1
1
= 4 X3 XS L'-A IBICI X OD,
we have PD = 40D = 4r, where r is the radius of the ball. It

follows that
P0 = PD - OD = 3r.
Suppose that the ball is tangent to the plane P AB at point

P 1. Then we have
As shown in Fig. 2, it is easy to see p

that the locus of the ball on the plane
P AB is also a regular triangle, denoted by
P1EF. Through P1 draw P1M ..l PA with
point M on PA. Then L.MPP1 = ~ , and At:..t..t...~~~~~Q.8
PM =PP1 XcosL!viPP1 ='2t/Zr X 1 =J6r. Fig. 2
It follows that P1E = PA- 2PM =a- 2J6r, where a

PA. Now, the space on PAB which the ball will never touch is
the shaded part of Fig. 2, and its size is equal to
SMAB - S L'>.P 1EF = 1 (a 2 - (a - 2/6r) 2 )
= 3/2ar- 6../3r 2
= 24../3 - 6../3
= 18../3'
since r = 1 and a = 4/6 under given conditions. Then the total

untouched area is
4 X 18../3 = 72../3.
Part III Word Problems (Questions 13-15, 20 marks each)

G It is known that the curve f (x) = I sin x I intercepts the
line y = kx (k > 0) at exactly three points, the maximum
x coordinate of these points being a. Prove that
cos a
sin a+ sin 3a
Solution The image of the three intercepting points of j(x) and

y = kx is shown in the figure. It is y
easy to see that the curve and the line
are tangent to each other at point
.r
A (a , - sin a) , and a E ( 7!, 327!) .
As j' (x) = - cos x for x E ( rr, 327!) , we have - cos a
- sma 1. e. a =tan a. Then

a
cos a cos a 1
sin a+ sin 3a 2sin 2acos a 4sinacos a
cos2 a + sin2 a 1 + tan2 a
4sinacos a 4tana
1 +a 2
4a ·
m Solve the inequality
log2 (x 12 +3x 10 +5x 8 +3x 6 +1) < 1 +log2 (x 4 +1).

Solution I As
and lo~ y is monotonically increasing over ( 0, + =) , the given

inequality is equivalent to
x 12 + 3x 10 + 5x 8 + 3x6 + 1 < 2x 4 + 2
or
It can be rewritten as
+ 2x 10 + 2x 8 - 2x 6
+4x 8 +4x 6 -4x 4
+x6 +x4 -xz
That is to say,
(x 8 + 2x 6 + 4x 4 + x 2
+ 1) (x 4 + x 2 -1) < 0.
Then we have x 4 +x2 - 1 < 0. It follows that x 2 <

- 1 +.fS .
2 ' I. e.
So the solution set is (- J- i.jS ,J- i.jS ).

1 1
Solution II As
1 + logz (x 4 + 1) = log2 (Zx 4 + 2),

and log2 y is monotonically increasing over ( 0, + =) , the given
inequality is equivalent to
or
(;z) 3
+ Z (;z) > x 6 + 3x + 3x 2 + 1+ Zx 2 + Z
4
= (xz + 1) 3 + Z(xz + 1).
Defineg(t) = t 2 +Zt. Then we have
Obviously, g ( t) is a monotonically increasing function;

then we have
That is to say,
We obtain x 2 < -1 +15 So the solution set is

z
CD As is shown in the figure, P is a

moving point on the parabola y 2 =
Zx , points B , C are on the y axis,

and the circle (x - 1) 2 +y2 = 1 is
c
internally tangent to h.PBC. Find the minimum value of

the area of h.PBC.
Solution Denote P, B, C by P(x 0 , y 0 ) , B(O, b), C(O, c),
and assume that b > c . The equation for the line PB is
Yo -b
y-b=--x.
Xo
It can be rewritten as
(yo -b)x -xoy +xob = 0.
Since the distance between the circle center (1 , 0) and the

line PB is 1, we have
I Yo - b + xob I = 1.
V(yo - b) 2 +x~
That is to say,
It is easy to see that xo >2. Then the last equation can be

simplified as
(x 0 - 2)b 2 + 2yob - Xo = 0.
In a similar way,
(xo - 2)c 2 + 2yoc - Xo = 0.
Therefore,
-2yo -x
b+c = - - , b e = - -0 .
Xo -2 Xo -2
Then we get
4x~ + 4y~ - 8x 0
(xo - 2) 2
As P(xo, yo) is on the parabola, y~ = 2xo. So we have
(b )z 4x5
- c = (xo - 2) 2 '
orb -c =~.Then
Xo -2
we have
1
S&BC = 2(b -c) Xxo
Xo
= - - Xx 0
Xo -2
4 - +4
= (x 0 -2) + -
Xo- 2
~4 +4 = 8.
The equality holds when xo -2 = 2; this means that xo = 4

and Yo = ± 2./2. So the minimum of S &oc is 8.
2009 n:mt.ut.Jifht·i•
The Popularization Committee of CMS and the Mathematical

Society of Heilongjiang Province were responsible for the
assignment of the competition problems in the first round test and
the extra test.
Part I Short-Amwa- Questiom {Questiom 1-8, seven IIIIUiai each)
0 Suppose that f(x) =

X
f[f[f ... f(x)]]. Then !'99)0) = _ __

""-------y----
n
Solution We have
pn (x) = f(x) = x
./I +x 2
J'99) (x) = x
.../1 + 99x 2 •
Therefore, !'99) (1) =

1•
10
0 Given the lineL: x + y- 9 = 0 and the circleM: 2x 2 +

2y 2 - Bx- By -1 = 0, point A is on L and points B, C
are on M; LBAC = 45 o and the line AB is through the
center of M. Then the range of the x coordinate of point
A is - - -
Solution Suppose that A (a , 9 -a). Then the distance from
the center of M to the line AC is
d = I AM I X sinLBAC
= ../(a - 2) 2 + (9 -a - 2) 2 X sin 45°
= .../2a 2 -IBa +53 X 1·

On the other hand, since the line AC intercepts M, it
follows that d :s:;;; the radius of M = J¥-, i. e.
2
./2a -IBa +53 x 2../2 :s:;;;~z·
(IT
The solution is 3 :s:;;; a :s:;;; 6.

8 On a coordinate plane there are two regions, M and N:

y ?0,
M is confined by { y :S:;; x , and N is determined by the
y :S:;;2 -x;
inequalities t :S:;; x :S:;; t +1 , 0 :S:;; t :S:;; 1. Then the size of the
common area of M and N is given by f (t)
Solution As shown in the figure, we have
y
J(t) = Sshadedarea
= S L:,.AOB - S L:,.OCD - S L:,.BEF
= 1- -1 t 2 - -1 (1-t) 2
2 2
0 The inequality
1 1 1 1
n + 1 + n + 2 + ... + 2n + 1 < a - 2007 3
holds for every positive integer n. Then the least positive
integer of a is - - -
Solution Obviously,
1 1 1
f(n) = n + 1 + n + 2 + ··· + 2n + 1
is monotonically decreasing. Therefore, j(l) reaches the
maximum of f (n). From
f(l) = 21 + 31 <a -2007 31 ,
we have a > 2008. Therefore, the least positive integer of a

is 2009.
2 z
0 Given points P, Q on an ellipse: 2 +~ 2 = 1 (a >b >O),
satisfyingOP l_ OQ, the minimum of I OP I XI OQ I is
Solution Define
P( I OP I cos(), I OP I sin()),
Q ( I OQ I cos ( o± ; ) , I OQ I sin ( 8 ± ; ) ) .
We have
1 _ cos28 + sin2 ()
IOPI 2 - a2 b2 '
1
2
=
2
sin 8 + cos2 8 2
I OQ 1 a2 b •
Then
1 1 1 1
I OP 12 +I OQ 12 = a2 + b2 '
. . 2a 2 b 2
Therefore, I OP I X I 0 Q I reaches the mmunum a2 + bz
when I OP I =I OQ I =
0 Suppose that the equation lg kx = 2lg(x + 1) has exactly

one real root. Then the range of k is _ __
Solution We have
kx >0,
X +1 >O,
kx=Cx+l) 2 •
The expression ® can be standardized as

x 2
+ (2 - k)x +1 = 0.
The two roots of ® are
X1 ' X2 = ~ [k - 2 ± ./k 2 - 4k],
where
tl = k2 - 4k ~ 0 ¢:9 k ~ 0 or k ~ 4.
(i) When k < 0, it is easy to see from® that xi + 1 > 0,

x2 +1< 0, and kx1 > 0. Then the equation has one real root,
XI = ~ [k -2 + ./k 2 -4k].
(ii) Whenk = 4, the equation has one real root, x = ~ -

1 = 1.
(iii) When k > 4, the two roots xi, x2 are both positive, as
well as xi *
x2. Discarded.
Therefore, the range of k is k < 0, k = 4.
8 Consider a pattern of numbers in the shape of a triangle:

the first row consists of numbers from 1 to 100 arranged
in order; each number in the second row is the sum of the
two numbers directly below it in the first row; each
number in the third row is the sum of the two numbers
directly below it in the second row;
The number in the last row is - - -
Solution It is easy to see that
(i) There are 100 rows in the pattern;
(ii) The numbers in the ith row constitute an arithmetic
sequence with the common difference
di = 2i-l' i = 1' 2' ... ' 99.

(iii) We have
a,. = a..---1 + Can-1 + 2..-- 2

)
= 2an-1 + 2"- 2
= 2[2an-2 + 2"-3 J + 2,_2

= 22 [2an-3 + 2..-4] + 2 X 2"-2
= 2n-1a1 + (n - I ) X 2"-2
= (n + 1)2n-2.
Therefore, the number in the last row is a 100 = 101 X 298 •
0 Every day at a railway station, there is just one train

arriving between 8: 00 am and 9: 00 am and between 9: 00
am and 10: 00 am, respectively. The arrival times and
their probabilities for the two trains are shown in the
following table:
TrainA 8110 8130 8150

Arrival time
Train B 9=10 9=30 9=50
Probability
1 1 1
6 2 3
Suppose that these random events are independent of

each other. Now, a traveler comes into the station at
8: 20. Then the mathematical expectation of his waiting
time is - - - - (round to minute).
Solution The distribution table for the waiting times of the
traveler is shown below.
Waiting
10 30 50 70 90
time/min
Probability
1 1 lxl lxl lxl
2 3 6 6 2 6 3 6
Therefore, the mathematical expectation of his waiting time is
10 X z1 + 30 X J1 +50 X 361 + 70 X 121 + 90 X 181 ~

.
27 (rnm),
Part II Word Problems ( 14 marks for Question 9, 15 marks

each for Questions 10 and 11, 44 marks in total}
0 Suppose that the line l : y =lex + m (k , m are integers)
6 +i2 = 1 at two different points A,

2 2
intercepts an ellipse ~
xz yz
B, and intercepts the hyperbola - - - = 1 at two
-
4 12
different points C, D. Can the line l be such that AC
B D = O? If yes, how many different possibilities are there
- +
for the line l? If no, explain the reason.

y = kx +m,
Solution For xz yz _ by eliminating y and simplifying
{
16 + 12 - 1.
it, we get
~1 = (8km) 2 -4(3 +4k 2 )(4m 2 -48) > 0. <D
by eliminating y and simplifying it,
we get
t-2 = (-2km) 2 +4(3 -k 2 )(m 2 +12) >O. ®

_____.. ____..
FromAC +BD = 0 we get (x 4 -x 2 ) +(x 3 -x 1 ) =0, which
implies that Xt + xz = xs + X4.
Then
Bkm 2km
3 +4k 2 3 -k 2 '
Therefore, km = 0 or -
3
+44k 2
3
1
_ k 2 (discarded).
Then a possible solution is either k = 0 or m = 0.

When k = 0, from <D and ® we have -2/3 < m < 2/3. As
m is an integer, it can be -3, -2, -1, 0, 1, 2, 3.
Whenm = O, from <D and® we have -/3 <k <13. Ask

is an integer, it can be -I , 0, 1.
Combining the results above, we conclude that there are
nine lines in total satisfying the given conditions.
fl!) It is known that p, q (q "# 0) are real numbers; the

equation x 2 - px + q = 0 has two real roots a, p; the
sequence {a,.} satisfiesa 1 = p, a 2 = p 2 -q, a,. = pa,.-1 -
qan- z(n = 3, 4, ... ).
C1) Find the general expression of {a,. } in terms of a , p.
( 2) If p = 1, q = ! ,find the sum of the first n terms of
{a,.}.
Solution I (1) By Vieta's theorem, we have a X p = q =I= 0,
a +p = p. Then
=(a +p)a.,-t -apad(n = 3, 4, ... ).
This can be rewritten as

Let b., = a,H - pa,. Then b..-1-1 = ab,. (n = 1, 2, ... ). This

means that {b,} is a geometric sequence with the common ratio
a. The first term of {b,} is
Therefore, b, =a 2 Xa"-1 =a"+1. Thena,H -pa, =a"H.

By rewriting
a..-1-1 = a..-t-1 +fh,(n = 1, 2, ... ).
When D. = p 2 -4q = 0, we have a = fJ # 0, a1 = p = 2a.

·
The expression CD becomes a..-1-1 = a..-1-1 + aa, , 1.. e. a..-1-1
..-~--1 - a,
---;;- = 1.
a a
Then {::} is an arithmetic sequence with the common
difference 1 , whose first term is a 1 = 2a = 2. Therefore,

a a
a
----; = 2 +1 X (n -1) = n + 1.
a
As a result, the general expression of {a,.} is
a, = (n +Da".
When D.> 0, a # fJ, we have
a..-1-1 = a..-t-1 +pa,

= pa, +fJ__f!_a..-t-1 -fJ~a..-l-1 (n = 1, 2, ... ).
- a - a
By rewriting,
..-1-2 ( ..+1 )
a..-t-1 +;-a =fJ a,+ ;-a (n = 1, 2, ... ).
n+l }
Then { a, +;_a becomes a geometric sequence with the
common ratio {3, whose first term is

2 2 a2
al +-a-= a +a +-a-=-~-'-.
{3-a ~-' {3-a {3-a
Therefore,
Then the general expression of {a,.} is

_ pn+l _an+l _
a, - {3 (n - 1, 2, ... ).
-a
(2) Given p = I, q = ! ,we have 6. = p 2 - 4q = 0. Then
a = {3 = ~ . By the expression @, the general expression of
{a,.} is
n + 1 (n = 1, 2, ... ).
a,.= (n +1) ( 21 )" = ~
Therefore, the sum of the first n terms of {a,.} is
Then
1
2s.. =
2
22 + 2a3 + ... + n+I
2n+l •
(4)-@,
1 3 n +3
2 5" = 2 - zn+l •
We finally get
S .. =
3 _n+3
2" .
Solution ll Cl) By Vieta's theorem, we have a Xf3 = q * 0,

a +{3 = p. Then
@
The character equation of {a,. } is ). 2 - p).. +q = 0, which

has roots a , f3. Then we can write down the general expression
of {a,.} according to the following different situations:
When a = f3 * 0, a,. = CA 1 +A 2 n)a". From@, we have
CA1 +Az)a = 2a,

CA1 +2Az)a 2 = 3a 2 •
Then we getA1 = Az = 1. Therefore,
a,. = (n + Da".
When a * f3, a,. = A 1a" + A f3". From@, we have
2
A1a +Azf3 =a +f3,

A1a 2 +Azf3 2 =a 2 +af3+f3 2 •
Then we get A1 -- - a
rJ--, Az -- rJ___!___ • Therefore,
t.J-a t.J-a
C2) The solution is the same as Solution I .
0 Find the maximum and minimum of the function
y = /x +27 + /13 -x +...fx.
Solution The domain of y is x E [0, 13]. We have

y = J X + 27 + ../13 - X + rx
= Jx +27 +Jl3 +2../x(l3 -x)
~ ./27 + ./IT = 3./3 + ./IT.
The equality holds whenx = 0. Therefore, the minimum of
y is 3./3 +./IT.
On the other hand, by the Cauchy inequality we have
y2 = <rx + Jx +27 + /13 -x) 2
~(~ +1 + ~ )C2x + (x +27) +303 -x)]
= 121.
The equality holds when 4x = 9 ( 13 - x) = x + 27. It is so

for x = 9. Therefore, the maximum of y is 11.
China Mathematical
Competition
(Complementary Test)
2008 IC3U·"'~1!"U·i-
0 (50 marks) As shown in Fig. 1, ABCD is a convex
quadrilateral with LB + LD < 180°, and P is a moving
point on the plane. Let
j(P) = PAX BC + PD X CA + PC x AB.

A
(1) Prove that P, A, B, C are con-
cyclic when f ( P ) reaches the
minimum.
(2) Suppose that pointE is on the arc
r---._
B
AB of the circumscribed circle 0
Fig.l
of MBC, satisfying
~ = 1 •~g =./3 -1, LECB = ~ LECA;

furthermore, DA, DC are tangent to 00, AC = ./2.
Find the minimum of f(P).
Solution I (1) As shown is Fig. 1, by the Ptolemy inequality
we have
PA XBC +PC XAB >PB XAC.
Therefore,
f(P) =PAX BC +PC XAB +PD X CA

>PB XCA +PD XCA
= (PB +PD) xCA.
The equality
,......._
holds if and only if P , A, B , C lie on 00
and P on AC. Furthermore, PB + PD > BD, and the equality
holds if and only if P lies on line BD. Combining the results
above, we have
j(P)rnm = BD X CA.
This completes the proof that P , A , B , C are concyclic

when f(P) reaches the minimum.
(2) Denote L_ECB =a. Then LECA = 2a. By the sine
theorem we have
AE sin 2a ./3
AB sin 3a 2 ·
That is to say, ./3 sin 3a = 2sin 2a. By using trigonometric

identities,
./3(3sina -4sin3 a) = 4sinacosa.

China Mathematical Competition (Complementary Test) 31
By simplification,
3./3 - 4./3 (1 - cos2 a) - 4cos a = 0.
That is to say, 4./3 cos2 a - 4cos a - .f3 = 0.
The solutions are cos a = 1 and cos a =- ~ (discarded).
Therefore a = 30° and LECA = 60°.

On the other hand,
BC = .f3 _ 1 = sin(LEAC- 30°)

EC sinLEAC .
That is to say
1 sinLEAC- ~ cosLEAC = (./3 -l)sinLEAC.
Then
2 -./3 1
sinLEAC
2
=
2 cosLEAC.
Therefore,
tanLEAC =
1 = 2 +./3.
2-./3
We obtain LEAC = 75° and LAEC = 45°.

Since MDC is an isosceles triangle and AC = ./2, we have
CD = 1. Furthermore, MBC is an isosceles triangle, soB C =
./2 and AB = 2. Then
BD 2 = AB 2 + AD 2 = 4 + 1 = 5.
We have BD = -/5. Therefore,
j(P)mm. = BD X CA = -/5 x./2 = ..;10.

Solution II C1) As shown in Fig. 2, the line ED intercepts

the circumscribed circle 0 of L':,.AEC at point P a, which lies on
ED because D is outside of 80. Through A, C, D draw lines
perpendicular to P 0 A, P 0 C, P 0 D, respectively, and they
constitute L':,.A 1 E 1 C 1 by intercepting
with each other. It is easy to see that
P o lies in L':,.AEC , as well as in
L':,.A 1 E 1C 1. Denoting the three inner
angles of L':,.ACD by x , y , z ,
respectively, we have 8
LAP 0 C = 180°- y = z +x. Fig. 2
Furthermore, from E 1C 1 l_ P aA and E 1A 1 l_ Po C, we have

LE1 = y. Inasimilarway, wehaveLA1 =x andLC1 = z. It
follows thatl:,.A1EICI (/)L':,.AEC. Now let
Then for any point M on the plane, we have
Af(P 0 ) =A (P 0 A XBC + P 0 D X CA + P 0 C X AB)

= PoA XE1C1 +Po D XC1A1 + PoC XA1E1
= 25,1\.AIBICI
~MA X B1C1 +MD XC1A1 +MC XA1E1

= ACMA X E C +MD X CA + MC X AB)
= Af(M) .
That is to say, j(Po) ~ j(M). Since M is an arbitrary

point, we know that j(P) reaches the minimum at P o, and at
the same time P 0 , A, B, C are concyclic. This completes the
proof .
China Mathematical Competition ( Complementary Test) 33
(2) From (1) we know that the minimum of f(P) is
In the same way as is shown in the proof of (2) in Solution

I , we find that both MDC and MBC are right-angled
isosceles triangles; so we have CD =AD = ~ = 1, AB
./2AC = 2, SMBc = 1,
Furthermore, since M1B1 C 1 en MBC, LAB 1B =
LAB1C + LBB1C = 90°, AB1BD is a rectangle. It follows that

~ ./5 and
B1C1 = BD =vo. ThereforeA. = ./2
f(P)nim = 2 X ji X 1 = ./IQ.
Solution ill C1) We discuss the problem on the complex

plane, and regard points A, B, C as complex numbers. Then
---- ----
by the triangle inequality we have
1PA ·BC 1+1 PC•AB 1~1 PA ·BC+PC ·AB I.
That is to say,
I (A -P)(C -B) I +I (C -P)(B -A) I
?I (A -P)(C -B)+ (C -P)(B -A) I
=1-P XC -A XB +C XB +P XA I
=I
--
(B -P)(C -A) I
=I PB ·AC I.
Then
---- ---- ---- --

~1 PB ·AC 1+1 PD ·AC I
- --
= (PB +PD) ·I AC I
=I BD I • I AC I.
The equality in CD holds only when the complex numbers
(A -P)(C -B) and (C -P)(B -A) are in the same direction.
This means that there is a real;. > o such that
(A -P)(C -B)= A(C -P)(B -A).
That is to say,
A -P B -A
C-P =il.c-B·
Therefore,
(A-P) = arg (BC _-A)

arg C _ p B ,
-- -- -- --
which means that the angle of rotation from PC to PAis equal
to that from BC to AB . It follows that P , A , B , C are
concyclic.
The equality in ® holds only when B , P , D are collinear
and Plies on the segment BD. This means that f(P) reaches
the minimum when P lies on the circumscribed circle of MBC
and P , A , B , C are concyclic.
(2) From (1) we know that f(P)mm = BD X CA. The
following steps are the same as those in the proof of ( 2) in
Solution I.
8 (50 marks) Let f(x) be a periodic function with periods

T and 1, satisfying 0 < T < 1. Prove that:
(1) If T is a rational number, there exists a prime p such
that ~ is also a period of f (x) ;
(2) If T is irrational, there exists a sequence of irrational

numbers {a~}, satisfying 1 >a~ > a,.+l > O(n = 1,
2, ... ) and each a~ is a period of f (x) .
Solution (1) T is a rational number, and there exist positive
integers m, n such that T =!!..and (m, n) = 1. There are two

m
integers a , b such that ma + nb = 1. It follows that
_l = ma +nb =a X 1 +b X T
m m
is also a period of f (x) . Furthermore, m ~ 2 because 0 < T <

1. Thenm = pm,
I
p be"mg a pnme.
. Theref ore,-
1 =m I X-Is
1 .
P m
a period of f(x).
(2) If Tis irrational, we definea1 = 1- [ j. J X T. Then 0 <

a1 < 1 and a1 is irrational. Define recursively
1
a~1 = 1- [a ,.]xa,..
It is easy to know by induction that each a,. is irrational and
0 <a,. < 1. On the other hand, we have a,.

_l_ - [l]
a,.
< 1. That is
to say,
Then
1
a,.H = 1- [a ,J x a, <a,..
This means that {a,.} is a decreasing sequence.

Finally, it is easy to prove by the definition of {a,. } and

induction that each a, is a period of f(x).
8 (50 marks) Suppose that ak > 0, k = 1, 2, ... , 2008.

2008
Prove that if and only if ~ ak > 1, there is a sequence
l=l
{x,.} satisfying
(1) 0 =x 0 <x,. <xn+u n = 1, 2, 3, ... ;
(2) limx,. exists;
2008 2007
(3) x,. -x,.-1 = ~a1xn+i- ~aH-lXn+i, n = 1, 2, 3, ....
1=1 l=O
Solution Proof of necessity: Assume that there exists {x,. }

satisfying (1) - ( 3) . Notice that the expression in ( 3 ) can be
written as
2008
x,. - x..--1 = ~ a1 (x,.-f* - Xn+r-1), n E N.
1=1
As xo = 0, we then have
n n 2008
X,. = ~ (Xl - X1-1) = ~ ~ ai (X I-f* - Xl-f*-1)

1= 1 1= 1 1 = 1
2008 n
= ~ ~al (XI-f* - Xl-f*-1)

i=1 1=1
2008
= ~ak(xn-1-* -xi).
i=l
From (2) we are able to defineb = limx,.. Let n-= in the

above expression. Then we have
2008 2008 2008
b = ~a1Cb -xk) = b~ak- ~akxk

i=1 i =1 k= 1
2008
<b~ak.
i =1
2008
Therefore, .2;a~ > 1.

1=1
2008
Proof of sufficiency: Asswne that ,2;a. > 1. Define a

1=1
polynomial function by
2008
f(s) =-1 + .2;a~s 1
, s E [0, 1].
1=1
f ( s ) is strictly increasing on the interval [ 0 , 1]. In the

meantime,
2008
j(O) =-1 < 0, j(l) =-1 + ,2;a > 0, 1
1=1
and there then exists a unique 0 <so < 1 such that f(so) = 0.
n
Now, define x, = .2:; s~, n E N. It is easy to see that {x,}
i=l
satisfies (1) and

" so -s~1
x, = ,2;s~
k=l
1 -so ·
On the other hand, lims 0+1 = 0 as 0 < s0 < 1. Then we have
s 0 - sn+1 s0
0
limx, = lim = - -- .
,.__,., ,.__,., 1 - So 1 -So
This means that {x,} satisfies (2). Finally, we have

2008
0 = f(so) =-1 + ,2;a.s~.

k= l
2008
That is to say, ,2; a 1 s~ = 1. Then we have

1=1
x, - x..-t = s3
2008 2008
= (.2;a~s~ )so = .2;a~sr

i=l i=l
2008
= .2;a~Cxn+~ - xn+k-t).
k- 1
Therefore, { Xn} also satisfies ( 3). This completes the

proof.
2009 n:rmt.],[.JI6J.f·l-
0 ( 50 marks) As shown in the Fig. 1, M, N are the
~ ~
midpoints of arcs BC, AC respectively, which are on the

circumscribed circle of an acute
triangle DABC ( .L::A < .L::B ) .
Through point C draw PC II MN ,
intercepting the circle r at point P. I B
is the inner center of DABC. Extend

line PI to intercept r at point T.
Fig.l
(1) Prove thatMP XMT =NP XNT;
.---...
(2) For an arbitrary point Q( #A, T, B) on arc AB (not
containing C) , denote the inner centers of D AQ C,
DQCB by I1, I 2, respectively. Prove that Q, I1,
I 2, T are concyclic.
Solution (1) As shown in Fig. 2, join NI, MI. Since PC II
MN and P , C, M, N are concyclic, PCMN is an isosceles
trapezoid. Therefore, NP = MC, PM = NC.
Join AM, CI. Then AM intercepts CI
at I. We have
.L::MIC = .L::MAC + .L::ACI

B
= .L::MCB + .L::BCI
= .L::MCI.
Fig. 2
Therefore, MC = MI. In the same way, NC = NI. Then

NP = MI, PM = NI.
This means that MPNI is a parallelogram. Therefore,
S L>PMr = S L>PNT , for the two triangles having the same base and
height.
On the other hand, LTNP + LPMT = 180°, asP, N, T,
Mare concyclic. Then we have
SL>PMr = ~PM XMTsinLPMT
= S M NT = ~ PN X NTsinL PNT
= ~ PN X NTsinLPMT.
Therefore, MP X MT = NP X NT.
(2) As shown in Fig. 3, we have
Therefore, NC = NI1. In the same

way, MC = MI2.
FromMP X MT = NP X NT we get
NT MT
MP NP"
Q
From ( 1) we know that MP NC,
Fig. 3
NP =MC. Then
Furthermore,
LIINT = LQNT = L QMT = LI2MT.
Therefore, L':,.I 1 NT (/) L':J 2 MT. Consequently, LNTI 1

L.MTiz. Then we have
This means that Q, I 1 , I 2 , T are concyclic.
0 (50 marks) Prove that

71
- 1 < (~ k2
k
+1) - ln n =< 21 , n = 1, 2, ....
Solution We first prove that
~X < ln(l +X) <X, X > 0. CD

1
Let
h(x) = x -ln(l +x),
g(x) = ln(l +x) - ~x·

1
Then, for x > o,
hI (X) = 1 -
1
~X > 0,
I ( ) 1 1 X
g x = 1 +x- (1 + x) 2 (1 + x)z > 0.
Therefore,
h(x) >h(O) =0, g(x) >g(O) =0.
This completes the proof of the inequalities CD.

Now letx =_!_in CD. We have
n
--1 < I n ( 1 +-
1) <-.
1
n +1 n n
Let
n k
x,. = ~ kz +1 - Inn.
Then
= n2~ ~ 1)
Xn - Xn-1
1 -ln( 1 + n
n 1
<n 2 +1 --;;
1
n(n 2 +1) <O.
1
Therefore, Xn < Xn-1 < ··· < x1 2.
Furthermore,
ln n = Cln n -ln(n -1)) + Cln(n -1) -ln(n - 2))

+ ... +Cln2 -lnl) +ln1
,.--1 1
= ~ln(1 +-,; ).
Consequently,
..--11
~- ~ (k +l)k
=-1 1 >-1.
+-
n
This completes the proof.
0 (50 marks) Suppose that k , l are two positive integers.

Prove that:
There are infinite many positive integers m ~ k such
that (7) and l are relatively prime.
Solution I Let m = k +t X l X (k ! ) , where t is any positive
integer. To prove that ( (7 ), l ) = 1, we only need to prove that
for any prime factor p of l, p { (7).

If p { k ! , we have
k ! (m )=
k
IT
i = l
(m - k + i)
4
= II Ci + tt<k DJ
4
=II i =k ! (modp).
; ~ 1
Therefore, p 1( 7).
If pI k!, there exists integer a ~ 1 such that pa Ik! but pa+l{
k !. Then pa+1 ll (k !) .
We have
m
k !(
k
)= II"' (m - k + i)
i = l
= II Ci + tz <k 1> J
i = 1
i
-II i; = 1
- k! (modpa+1 ).
get p t(7)· The proof is completed.
Solution n Let m = k +t X l X (k I) 2 ' where t is any positive

integer. The following proof steps are similar to those in
Solution I , and are omitted.
0 (50 marks) Suppose that a matrix of nonnegative entries,
P = [X"
xz1
X12
Xzz
X13
X23
X14
Xz4
X15
X25
X15
Xzs
X11
X21
X13
Xzs
x,1
Xzg
Xs1 Xsz Xss X34 X35 Xss X37 Xss X39
has the following properties:

(1) Numbers in a row are different from each other;
(2) The sum of the numbers in a column from the first six
columns is 1;
(3) X17 = X2s = X39 = 0;
(4) X27' X37' X1g' X3g' X19' X29 > 1.
Assume that matrix S is constituted by the first three
columns of P , i. e.
has the following property:
(0) For any column r::1 (k = 1, 2, ... , 9) in P, there

X34
exists i E {1, 2, 3} such that
xa ~ u; = min{xil , x;z, x;3}. <D

Prove that:
(i) For different i ( = 1, 2, 3), u; = min{xil , x;2 , x; 3 }

comes from different columns in S;
(ii) There exists a unique column x2k •

xu•1 (k * * 1, 2, 3)
r Xak"
in P such that the matrix
S' = r=:: :::

X31 Xaz
also has property ( 0) .

Solution Proof of C i ) . Assume that it is not true. There is a
column inS which contains no u,. We may say that u, =1=- x, 2 ,
i = 1, 2, 3. By property (1), we have u, < x;2, i = 1, 2, 3.
On the other hand, let k = 2 in CD. Then by property ( 0) ,
there existsio E {1, 2, 3} such thatx;0 z <u,. The contradiction
means the assumption is not valid. This completes the proof
of ( i ) .
Proof of ( ii ) . By the drawer principle, we know that at
least two of the three numbers
min{xn , X12}, min {xzl, Xzz}, min {xal, Xaz}
are in the same column. We may say that
min{xzl, Xz2} = X22, min{xal, Xaz} = Xaz.
By ( i ) , we know that the first column of S contains a u, ,

and it must be u 1 = x 11 ; the second column also contains a u; ,
assuming that it isu 2 = x 22 , and then it must beu 3 = x 33 •
DefineM = {1, 2, ... , 9} and
I = {k EM Ixa > min{x a , x 12 } , i = 1, 3}.

Obviously, I = {k E M I xu > xn, Xak > xaz}, and 1, 2,

3 f/:. I. Sincex 18 , x 38 > 1 ~x 11 , x 32 , we have8 E I. Therefore,
I * 0. Consequently, 3 k E I such that
* x2k • = max{xzk I k E
I}. Of course, k • * 1, 2, 3.
We now prove that
xn Xtz X a•
S' X21 X22 X2k *
r Xat Xaz X3k"
has property (0).

By the definition of I, we know that
xa• >xu = Ut, X3k" > Xa2 ~ ua.
Let k * = k in ( i ) , and we get xzk" ~ uz according to

property (0) of S. Then define
We claim that, for any k EM, there exists i E {1, 2, 3}

such that u~ ~ xa;. Otherwise, we would have xa > min{x; 1 ,
x;z}, i = 1, 3 and x2k > xzk", contradicting the definition
of k •.
Therefore, S' has property (0).
Secondly, we prove the uniqueness of S'. Assume that
3 ko E M such that
xn Xtz
S= Xzt Xzz
[
X at
also has property ( 0 ) . Without loss of generality, we

assume that
Mathematical Olympiad in China
u; =min{x;l, X;2, x; 3} =x;;, z = 1, 2, 3,
Since x32 < x31, xz2 < x21, and by ( i ) , we have
By C i ) again, we have either

(a) U3 = min{x31' X32' X3k0 } = X3k 0 Or
(b) U2 = min{Xzl' Xz2' XZk 0 } = XZk 0 •
If (a) is true, we will have
For 3 EM, since both S and S have property (0), we will

get
By property (1) of P, we have 3 = ko. Therefore, S= S.

If (b) is true, we will have
Since S has property ( 0) , we know that, for k • E M,

thereexistsi E {1, 2, 3}suchthatu; ~xa. Ask* EI,andby
@,@,it must bex2k· ~Uz = x2k·
On the other hand, S also has property ( 0) . Then, in a
similar way, we getx2k ~u~ = xZk·.
Therefore, k * = k. This completes the proof.
Chinese Mathematical
Olympiad
2009 IC•H·HVI®MISli!flhl
First Day
(0800 - 1230; January 9, 2009)
0 Given an acute triangle PBC, PB "#PC. Let points A, D

be on sides PB and PC, respectively. Let M, N be the
midpoints of segments BC and AD, respectively. Lines
AC and BD intersect at point 0. Draw OE l_ AB at point
E and OF l_ CD at point F.
( 1) Prove that if A , B , C, D are concyclic, then
EM X FN = EN X FM.
(2) Are the four points A, B, C, D always concyclic if

EM XFN =EN xFM? Prove your answer. (Posed by
Xiong Bin)
p
Proof (1) Denote by Q, R the midpoints
of OB, OC, respectively. It is easy to
see that
EQ =
1
-OB = RM, MQ =
1
-OC = RF,
2 2
and
L EQM = LEQO + LOQM = + LOQM,

2 L EBO
LMRF = LFRO + LORM = 2LFCO + LORM.
Because of that A, B, C, D are concyclic, and Q, R are
the midpoints of OB , OC, and we have
LEBO= LFCO, LOQM = LORM.
So L EQM = L MRF, which implies that LEQM (/)

L:c.MRF, and EM = FM.
Similarly, we have EN = FN, so EM X FN = EN X FM
holds.
(2) Suppose that OA = 2a, OB = 2b, OC = 2c, OD = 2d
and
LOAB =a, LOBA = (3, L ODC = y, L OCD =e.
Then
cosLEQM = cos(LEQO + LOQM)

= cos(2[3 + LAOB)
=- cos(a - [3) .
So
Chinese Mathematical Olympiad 49
EM 2 = EQ 2 + QM 2 - 2EQ X QM X cosL.EQM
= b + 2 c2 + 2bccos(a - (3).
Making similar equations for EN, p

FN, FM, we have
EN x FM =EM xFN
8 EN 2 X FM 2 = EM 2 X FN 2
8(a 2 +d 2 +2adcos(a -(3)) X (b 2 + c 2 +
2bccos(y -f))) = (a 2 + d +2adcos(y-
2
8 /L__---->L---"' c
f))) X (b 2 + c 2 + 2bccos(a -(3))
8(cos(y - f)) - cos(a - (3))(ab - cd)(ac - bd) = 0.
Because a +(3 = y +fJ, cos(y -f)) -cos(a -(3) = 0 holds if

and only if a = y, f3 = f) (i.e. A, B, C, D are concyclic) or
a = f), f3 = y (which follows AB II CD, a contradiction.) ; ab -
cd = 0 holds if and only if AD II B C; ac - bd = 0 holds if and
only if A, B, C, D are concyclic.
So, when AD II B C holds, we also have
EM X FN = EN X FM.
We know that A, B, C , D are not concyclic in this case

because P B * PC, so the answer is "false".
8 Find all pairs Cp , q) of prime numbers such that pq I 5P +
5q . (Posed by Fu Yunhao)
Solution If 2 I pq, we suppose that p = 2 without loss of
generality, and then q I 5q + 25. By Fermat's theorem we have
q I 5q - 5, so q 130, where (2, 3) and ( 2 , 5) are solutions [ (2,
2) does not fit].
If 51 pq, we suppose that p = 5 without loss of generality
and then 5q I 5q +5 5• By Fermat's theorem we have q I 5" 1 -1,
so q 1313, where (5, 5) and (5, 313) are solutions.

Otherwise, we have pq I 5p---1 + 5q--1 , and so
5p--1 + 5q--1 = 0 (mod p).
By Fermat's theorem, 5p--1 = l(mod p),

and because of CD and ®, 5q--1 - - 1 (mod p).
Denote by p -1 = 21 (2r -1), q -1 = 21 (2s -1), where k ,

l, r, s are positive integers.
If k :< l , because of ® and ® we get
1 = 1zl-i (2.---1) = ( sp---1 ) zl-i (2.---1)
= 521 (2r-1)(2.-1) = (5q--1 )Zr-1 = ( -l)Zr-1
--lCmodp),
a contradiction of p #- 2. So k > l.
But we havek <l by a similar argument- a contradiction.
Therefore, all possible pairs of primes ( p , q ) are ( 2 , 3) , ( 3 ,
2), (2, 5), (5, 2), (5, 5), (5, 313) and (313, 5).
8 Let m, n be integers with 4 <m < n, andA1Az ... A z,.+l be

a regular 2n +1 polygon. In addition, let P = {A1,
Az, ... , Az,.H }. Find the number of convex m-gons with
exactly two acute internal angles whose vertices are all in
P. (Posed by Leng Gangsong)
Solution Notice that if a convex m-gon whose vertex set is
contained in P has exactly two acute angles, they must be at
consecutive vertices: for otherwise there would be two disjoint
pairs of sides that take up more than half of the circle each.
Now assume that the last vertex, clockwise, of these four
vertices that make up two acute angles is fixed; this reduces the
Chinese Matlr.etMtictll Olympiad 51
total number of regular m-gons 2n + 1 times and we will later

multiply by this factor.
Suppose that the larger arc that the first and the last of
these four vertices make contains k points, and the other arc
contains 2n- 1 - k points. For each k, the vertices of them-
2n-1-k)
polygon on the smaller arc may be arranged in (
m-4
ways, and the two vertices on the larger arc may be arranged in
(k -n -1) 2 ways (so that the two angles cut off more than half
of the circle).
The total number of polygons given by k is thus (k -n -1) 2 X
(
2n-1 -k). Summation over all k and a change of variable
m-4
shows that the total number of polygons (divided by a factor of
2n +1 ) is 2::; k 2 X (
n-k -2)•
k;;;.o m -4
1
This can be proven to be exactly ( n ) + ( n + ) by
m -1 m -1
double induction on n > m and m > 4. The base cases n = m +1
and m = 5 are readily calculated. The induction step is
2::; k 2 X(
n-k -2)
.&~o m -4
(n -1) - k - 2) ( (n -1) - k - 2 )
= 2:;k 2 X ( + 2:;k 2 X
.&;;;.o m - 4 k~o (m - 1) - 4
=(:-=-~)+(m ~1)+(:-=-~)+(m ~2)

= (m ~ 1 )+ (: ~ ~ ).
So the total number of (2n + 1) -gons is
Second Day
(0800-1230; January 10, 2009)
0 Let n > 3 be a given integer, and a1, az, ••• , a,. be real
numbers satisfying min I a; - ai I = 1. Find the minimum
l.,;;;i<i~
..
value of~ I al 1
3
• (Posed by Zhu Huawei)
k-1
Solution Without loss of generality, we may assume that
a1 < a 2 < ··· <a,. , and note also that
I a* I +I a ..-Hl I >I a,.--k-t-1 -ak I >In +1-2k I
for 1 <. k <. n. So
1 n
>s ~CIa;. 1+1 a...t-H 1) 3
11
1
>s ~ In +1-2k I3 .
When n is odd,
When n is even,
n
..
2
~ In +l-2k 13 = 2~(2i -1) 3
i=l i=l
= 2(~i 3 - t,c2i) 3
)
= ! n 2 (n 2 - 2).
So
for odd n , and
n +1 1,
for even n. The equality holds at a, = i - - - i
2
2, ... , n.
0 Find all integers n such that we can color all the edges and
the diagonals of a convex n-polygon by n given colors
satisfying the following conditions:
(1) Each of the edges or the diagonals is colored by only
one color;
(2) For any three distinct colors, there exists a triangle
whose vertices are vertices of then-polygon and three
edges are colored by these three colors. (Posed by Su
Chun)
Solution Answer: Any odd number n > 1.
First of all, there are G) ways to choose three among n
colors, and(;) ways to choose three vertices to form a triangle,
so if the question's condition is fulfilled, all the triangles should

have a different color combination (a 1-1 correspondence).
Note that any two segments of the same color cannot have a
common endpoint.
As each color combination is used in exactly one triangle,
for each color there should be exactly C~ ) triangles which

1
1
have one side in this color, and so there should be exactly n ;
lines of this color. Therefore, n is odd.

Now we give a construction method for any odd n.
As the orientation of the vertices does not really matter,
we may assume that the polygon is a regular n-polygon. First,
color then sides of the polygon in then distinct colors. Then,
for each side, color those diagonals that are parallel to this side
into the same color.
In this way, for each color, there are n diagonals colored
in this color, and notice that each of these diagonals is of a
different length. Q)
Besides, for any two triangles with all vertices in, we shall
prove that they should have different color combinations.
Suppose that, on the contrary, they have exactly the same three
colors as their sides. Because of that all the sides with the same
line are parallel, and the two triangles must be similar. For
their vertices to be in the same circle, they must be the same,
but this is a contradiction of <D. This completes the proof.
0 Given an integer n ~ 3, prove that there exists a set S of n

distinct positive integers such that for any two distinct

nonempty subsets A and B of S J the numbers
~X ~X
xEA xEB
TATJ TBl
are two coprime composite integersJ and ~x denotes the
:z:EX
sum of all elements of a finite set X, and IX I denotes the
cardinality of X. (Posed by Yu Hongbing)
Proof Let f (X) be the average of elements of the finite
number set X. First of allJ make n different primes Pt 1 P2, ••• ,
p,. which are all bigger than n, and we prove that for any different
"
flp;
1
~
1
nonempty subset A, B of the set S 1 = : 1
{ Pi
j(A) =1=- f(B) always holds.
" n
flp; flp;
In fact, we can suppose that ; ~ t E A and ;~t f/: B
Pt Pt
without loss of generality. Every element of B can be divided
by Pt, so Pt In! f (B). But A has exactly one element which
cannot be divided by Pt, so we find that n! f (A) cannot
divided by Pt ( note that Pt > n), and therefore
n !f(A) =1=- n !f(B), which follows f(A) -=1= f(B).
Second, let S2 = {n !x :x E Sd. Then f(A) and f(B) are
different positive integers when A, B are different nonempty
subsets of S 2 •
In fact, it is easy to see that there exist two sets At, B1
which are different nonempty subsets of Sto and f(A) = n!
!CAt), f(B) = n !JCBt) holds. We get f(A) -=1= f(B) from
!CAt) -=1= JCBt) 1 and f(A) 1 f(B) are positive integers from
I A I, I B I~ nand their elements are all positive.

Then, let K be the largest element of S 2 • We prove that
for every two distinct subsets A , B of the set S 3 = {K Ix + 1:
x E S2}, f(A) and f(B) are coprime integers which are both
larger than 1.
which are different nonempty subsets of S2, and f(A) =
K !JCA1) + 1, f(B) = K !JCBt) + 1 holds. Obviously, f(A)

and f(B) are different integers which are both larger than 1. If
they have common divisors, let p be a prime common divisor of
them without loss of generality. Clearly, we have p I CK ! •
I !CAt)-JCB1) 1). We get 1 ~I !CA1)- JCB1) I ~K byO <
!CAt), JCB1) ~ K and JCA1) =I= JCB1), sop ~ K, which
follows p I K !f (A 1) , and then p 11 - a contradiction.
Lastly, let L be the largest element of S 3 • We prove that
for every two distinct nonempty subsets A, B of the set S4 =
{L! + x :x E Sa}, f(A) and f(B) are two composites which
share no common divisors.
which are different nonempty subsets of Sa, and f(A) = L! +
!CAt), j(B) =L! +/CBt) holds. Obviously, /(A) and /(B)
are different integers which are both larger than 1. Because of
that, L is the largest element of S 3 , and we have f (At ) I L !
and !CAt) 1/CA). We find that f(A) is composite by !CAt)<
f (A). For a similar reason, f ( B ) is composite too. If they
have common divisors, let p be a prime common divisor of
them without loss of generality. It is obvious that p I (L ! •
I /CAt) - /CBt) I). We get 1 ~I /CA1)- /CBt) I ~L byO <
!CAt), j(Bt) ~Land JCA1) =I= JCB1), sop ~ L, which
follows p If (A 1) and p If ( B 1 ) - a contradiction of the fact
Chinese Mathematical Olympiad 57
that jCA1) and JCB1) are coprime. This completes the proof.
2010
First Day
(0800 -1230; January 22, 2010)
0 As shown below, two circles r 1 , r 2 intersect at points A,

B , one line passing through B intersects r 1 , r 2 at points
C, D , another line passing through B intersects r 1 , r 2 at
points E, F, and line CF intersects F
r 1 ' r 2 at points p' Q' respectively .
Let M, N be the middle points of arc
PB and arc QB, respectively. Prove
that if CD = EF, then C, F, M, N
are concyclic. (Posed by Xiong Bin)
Proof Draw lines AC, AD, AE, AF, DF. From L.ADB =
L.AFB, L.ACB = L.AEF and the assumption CD = EF; one

obtains L-.ACD (/) L-.AEF. So we have AD = AF, L.AD C
L_AFE and L_ADF = L_AFD. Then L_ABC = L_AFD
L.ADF = L.ABF; AB is the bisector of L.CBF. Draw lines
CM, FN. Since M is the middle point of arc PB, CM is the
bisector of L.DCF, and FN is the bisector of L_CFB. Then
BA, CM, FN have a common intersection, say, at I. In the
circles T 1 and T 2 , one has CI X IM =AI X IB, AI X IB = NI X
IF, according to the theorem of power with respect to circles.
SoNI XIF = CI XIM, andC, F, M, N areconcyclic.
0 Given an integer k ~ 3 and a sequence {a,} that satisfies

a1 = 2k and for each n > k,
a, = {an-1 + 1, if a,-1 ~nd n are coprime,
2n , otherwtse.
Prove that a, - a,-1 is a prime for infinitely many n.

(Posed by Zhu Huawei)
Proof Suppose that a1 = 2l, l ~ k. Let p be the least prime
1, I~i<p,
divisor of k -1. Then (l -1, i) = { and thus
p, i = p,
(2l +i -2, l +i -1) ={p,1

'
1
i
~
=
i
p.
< p,
From (1) we know that
2l +i -1, 1<i<p,
al-H-
1
= { 2l + 2p -2, i = p.
ThenaHp--1-al-+p--2 =(2l+2p - 2)-(2l+p - 2) =pisaprime

number, a1-+p-1 = 2(l + p-I). From the discussion above, we
know that there are infinitely many l ~k , such that a1 = 2l and
al+p--1 - a1-+p-2 = p is the least prime divisor of l -I.
0 Let a , b, c be complex numbers such that I az 2 + bz +

c I < 1 for all complex numbers z with I z I < 1. Find the
maximum of Ibe I • (Posed by Li Weigu)
Solution Write f(z) = az 2 + bz +c. We first prove that
I /Cz) I~ 1 for all z, I z I~ 1 ~ I /Cz) I ~ 1 for all z, I z I = 1.

<D
Assume thatj(z) =a(z -a)(z -p). For any z, I z I <1,
if a = p, one of the two intersection points of the line through a
and the origin with the unit circle is closer to a than z is; if a =I=
{3, the line through z and perpendicular to the line through a , {3
intersects the unit circles at two points, one of which is closer to
a , {3 than z is, respectively. So <D holds.
For any complex number z, I z I = 1, it is obvious that
I f(z) I= I cz-2 +bz-1 +a I.

So I ab IIII8X =I be IIII8X. Writea'z 2 +b'z +c' = e;,f(e;pz).
One can choose real numbers a, {3 such that a', b' are positive
real numbers, so one can assume that a, b ~ 0 without loss
of generality
1 ~I f ( e;a) I ~ I lm f ( e;a) I = I a sin 20 + b sin 0 + Im c 1.

Without loss of generality we can assume 1m c ~ 0 (otherwise
take a map, 0 - - 0 ) . For any 0 E ( 0, ~ ) ,
1 ~a sin 20 + bsin 0 ~ 2 ./absin 20sin 0

-=::;> ab < 4sin 2~sin 0' 0 E (0 ' ~)
1 - 3../3
=::;>ab < OE min 4 . 210 . 0
(o. i) sm sm 4 max (sin 20sin 0) - 16
OE (o, "¥)
3../3
-=::;>I be Imax =I ab Imax< 16'
An example of I b c I= '[! is
3
f (z) = 1 -1 zz z - 3'{( '

I f(eiD) 1
2
= 1- ~ (cos 0 -1 f < 1.
Second Day
(0800 -1230; January 23, 2010)
0 Given two integers m, n greater than 1, and integers a1 <

a2 < ··· <am, prove that there exists a set T of integers
with I T I ~ 1 + a : ~; 1 such that each a; can be written as

2
a; = t + s for some t E T, and s E [- n, n]. (Posed by
Leng Gangsong)
Proof Writea1 =a, am =b, b -a= (2n +l)q +r, whereq,
r E Z and 0 ~ r ~ 2n. Take
T = {a + n + (2n + l)k I k = 0, 1, ... , q}.
Then I T I= q + 1 ~ 1 + 2bn -a
+ 1. We have the set
B = {t +sItE T, s = - n, - n +1, ... , n}

={a, a +1, ···,a +(2n +1)q +2n}.
Note that a + (2n + l)q + 2n ;;::: a + (2n + l)q + r = b, so

each a; belongs to B.
0 We operate on piles of cards placed at n + 1 positions A1,

A2, ... , A,. (n ;;:::3) and 0. In one operation, we can do
either of the following:
(1) If there are at least three cards at A;, we may take
three cards from A; and place one at each of A;- 1,
Ai+1 and 0 (assume thatAo =A,., A...t-1 = A1);
(2) If there are at least n cards at 0, we may taken cards
from 0 and place one at each of A 1 , A 2 , ••• , A,..
Prove that if the total number of cards is at least n 2 + 3n +
1, we can take some operations such that there are at least
n + 1 cards at each position. (Posed by Qu Zhenhua)

Proof One only needs to consider the case with the total
number of cards equal n 2 + 3n + 1. We take the following
strategy. If there are at least three cards at some A, , then use
operation (1) at this position. Such operations can be done for
only finitely many steps. Then we have no more than two cards
at each A, and no less than n 2 +n + 1 at 0.
We then take operation (2) for n + 1 times. There are then
at least n + 1 cards at each A, . We will now prove that one can
increase the number of cards at 0 to at least n + 1, while
keeping at least n + 1 cards at each A,.
Put A 1 , A 2 , A,. evenly and in increasing order on a
••• ,
circle with the center at 0. We call a group of consecutive A, 's,

G ={A,, A;+1, ••. , A;-H-1}, 1 s;;,i <n, 1 s;;,z s;;.n, on the circle
a team, where for j > n we define A; = A h . A team is good if
after we take operation (1) once at each point in G, there are
at least n + 1 cards at every point in G. Write a1, a2, ••• , a,. as
the number of cards at points A1, Az, ... , A,., a; ~n + 1, i =
1, 2, ... , n. Let G = {A,} be a team. Then, if there is only
one point A, in G, G is good iff a; ~n +4; a team of two points
G = {A, , A,+l} is good iff a; , a;+l ~ n + 3; a team G = {A,,
A;+l, ... , A;-H-l} of l points (3 <l <n- 1) is good iff a,,
a;-H-l ~n+3anda; ~n+2, i+1s;;.j s;;.i+l-2;finally, the
team G = {A1, A2, ... , A,.} of all n points is good iff aj ~n +
2, 1 < j < n. We then prove that there must exist at least one
good team if a 1 + a 2 + ... +a,. ~n2 + 2n + 1.
Assume that there is no good team. Then each a; E {n + 1,
n + 2, n + 3} , otherwise there is a good team of one point at any
A, with a, ~n + 4. Suppose that the number of n + 1, n + 2 and
n + 3 's among a1, az, ... , a,. are x, y, z respectively. We
willshowthatx ~z. Sincen 2 +2n +1 >n(n +2), z ~1. If
z = 1, thenx ~1, otherwise alia; ~n+2andG ={Au A 2 , ••• ,
A, } is a good team. If z ~ 2, the z points with n + 3 cards divide

the circle into z arcs (no two of these z points are adjacent).
Since there is no good team by assumption, there is at least one
point on each arc with n + 1 cards. So x ~ z , and the total
number of cards at A1, A2, ... , A, is
x(n +1) +y(n +2) +z(n +3) < (x +y +z)(n +2)

= n (n + 2) < n 2 + 2n + 1,
which is a contradiction. Thus, we have proven that when the
number of cards at 0 is less than n + 1, there exists a good
team. We use operation (1) on each point of a good team; the
number of cards at 0 is increased while the number of cards at
each A1, A2, ... , A,. is still no less than n + 1. We can
reiterate until there are at least n + 1 cards at 0.
0 Let a1, a2, a a, b1 , b2, ba be pairwise distinct positive

integers such that
(n + 1)a~ + na~ + (n -1)a~ I (n + 1)M + nb~ + (n -1)b~

holds for all positive integers n . Prove that there exists a
positive integer k such that b, = ka, for all i = 1, 2, 3.
(Posed by Chen Yonggao)
Proof Suppose that r is any positive integer. Since there are
infinitely many primes, there is a prime p, such that
p >(a]" +a2 +a3)(b! + b2 +b3).

Because p is prime and CD, we have (p, a! +a2 +a3) = 1.
p is coprime to p - 1; from the Chinese remainder theorem,
there is a positive integer n such that
n =r (mod p - 1) , ®
n(ai +a2 +aO +ai -a;- 0 (modp), ®
From@, ®and Fermat's theorem,
(n + Dai +na2 + (n -Da3 = n(ai +a2 +a3) +ai -a;

-0 (modp).
From the assumption of the problem,
(n + Dbi + nbi + (n -l)bj - 0 (mod p).
Again from® and Fermat's little theorem,
n(bi +b2 + b3) +b! -b3 = 0 (modp). ®

Eliminate n from @, ®:
(a! +a2 +a3)(b1 -b;)- (bi +b2 +b3)(a1-a3)(modp),

®
From Q), ® we have
(ai +a2 +a3)(bi - b;) = (bi +b2 +b3)(a1 - a;),
and thus
Ca2b1Y +2(a3bl)r +Ca3b2Y = Ca1b2Y +2(alb3Y +Ca2b3)r,
(J)
We then prove the following lemma.

Lemma Assume that x1, ... , x,, Y1, .•• , y, are real numbers,
such that for any positive integers r,
xi + x2 + ··· + x; = yi + y2 + ... + y~.
Thenx; = y;(i = 1, 2, ... , s).

Proof of the lemma. We use induction on s. If s = 1, taker =
1; then x1 = Yl· Assume that the lemma holds when s = t.

When s = t + 1, if xt+1 =1=- Yt+l, say xt+1 < Yt+l,
( Yt+1
~ )r + '" + (X tt-l )r
Yt+1
= ( ~
Yt+1
r + "' + ( r + ~
Yt+1
1 ~ 1.
Because 0 < x, <1 (1 ~i ~t + 1), take the limit r -

Yt+l
+ oo, and we have 0 ~ 1, a contradiction.

So Xt+1 = Yt+l, and then xi: + ... + x~ = y1 + ... + y~, r =
1, 2, . . . . By induction the lemma holds for all positive integer s.
Now return to the proof of the problem. Since a1, az, a3,
b1, bz, b3 are distinct,
azb1 =1=- aab1, aab1 =1=- aabz, a1bz =1=- a1ba,

a1ba =1=- azba, azb1 =1=- azba.
From (j) and the lemma we know that
or
azb1 -_ -
a3b2
- -_ -
a1ba . e. -az -_ -a3 -_ -
a1,
If ® holds, then--
asb1 a1bz
- , 1.
azbs a3 a1 az
which is a contradiction to a 1 , a z , a 3 being distinct. So ®
holds. Then!!.!. =b 2 =b 3 • Writeb 1 = kl, (k, l) =1, l ~I;

a1 az a3 a1
thenb; =;a,, i = 1, 2, 3. From2bl +bz = 7(2al +az) and

the assumption of the problem (with n = 1), 2a1 +az I 2bl +bz
and 7 is an integer. Sol = 1 and b; = ka;, i = 1, 2, 3.

China National
Team Selection Test
2009
First Day
(0800 -1230; March 31, 2009)
0 Let D be a point on side BC of triangle ABC such that

.LCAD = .LCBA. A circle with center 0 passes through
B, D, and meets segments AB, AD at E, F, respectively.
Lines BF and DE meet at point G. M is the midpoint of
AG. Prove that CM l_ AO. (Posed by Xiong Bin)
Proof As shown in Fig. 1, extend EF and meet BC at point
P, and join and extend GP, which meets AD at K and the

extension of AC at L.
Fig.l
As shown in Fig. 2, let Q be a point on AP such that
LPQF = LAEF = LADE. A
It is easy to see that A , E , F , ' '\

I
I
Q and F , D , P , Q are concyclic I
I
respectively. Denote by r the radius 9,,

' '\
of 80. By the power of a point I
I
theorem, I
I
' I
AP 2 = AQ x AP +PQ xAP
=AF XAD + PF XPE Fig. 2
= CA0 2 - r 2 ) + CP0 2 - r 2 ).
CD
Similarly,
By CD, @, we have AP 2 - AG2 = P0 2 - G0 2 , which

implies that PG l_ AO. As shown in Fig. 3, applying Menelaus'
theorem for L,.P FD and line AEB , we have
DA FE PB A
AF X EP X BD = 1. ®
Applying Ceva's theorem for

~PFD and point G, we have
DK FE PB @
KF X EP X BD = 1.
p
®--;-@yields
Fig. 3
DA _ DK
AF- KF" ®
Equation® illustrates that A, K are harmonic points with

respect to F, D, i.e. AF X KD =AD X FK.
It follows that
AK xFD = AF xKD +AD x FK = ZAF x KD. ®

Since B, D, F, E are concyclic, we have .LDBA
L_EFA. Since L_CAD = L_CBA, we have L_CAF = L_EFA,
which implies that AC II EP. Thus,
CP AF
PD FD"
Applying Menelaus' theorem to ~ACD and line LPK,

we have
Combining ®, (f) and ®, we have 1~ = 2.
In ~AGL , M, C are the midpoints of AG, AL

respectively, and henceMC II GL. SinceGL l_ AO, we conclude
thatMC l_AO.
0 Given integer n ~2, find the largest number ACn) with the
following property: if a sequence of real numbers ao, a1,
a2 ' ••• ' an satisfies
a; ~ ~ (a;+1 + a;-1), i = 1, 2, ... , n- 1,
then
n ) z n
( ~ia; ~A.(n) ~a~.
Solution The largest possible value of A. (n) is n (n t 1)

2
•
:< n(n +
2
1)
Let a1 = az = ··· =an = 1. Then we have A. (n) .
4
We shall show that for any real numbers ao, a1, az, .•• ,
an satisfying the indicated property in the problem, the
following inequality holds:
~ za, ~ a,? ) .
2
( L.J •. ) 2 n (n
,_._ + 1) 2 ( L.J CD
i=l 4 i=l
First, we notice that
Indeed, by assumption, 2ia; ~ i (a;+l + a;- 1) holds fori

1, 2, ... , n - 1. For any given positive integer 1 :< l :< n - 1,
summing the above inequality over i = 1 , 2, . . . , l , we have
(l + Da1 ~ lal+1, i.e.
al
l ,_._ l
>- + 1 f or l
al+1
= 1 ' 2 ' . . . ' n - 1•
In what follows J we show that for any i J 1 J k E {1 J

2 , . . . , n } , if i >j , then
IndeedJ the above inequality is equivalent to2ik 2 (j +k) >

2jk (i +k), i.e. (i -j)k >0, whichisclearlytrue.
2 3
Now, we are going to show inequality <D. We shall start by

estimating the lower bound of a,ai for 1 :O, i.e. a;ai >
i z + j 2
i + /i i + ja,.
Thus, we have
" 2ik 2
Let b, = ~ . + k. We see from previous results that b1 :<
i=l t
bz :<··· :<b,..
Since a~ :<a~ :< ... :<a!, by the Chebyshev inequality, we
have
Since
we find that (~ia;) 2 ~

n(n +1) 2 ~ 2
4
L.Ja;, which proves
i- 1
inequality <D.
We conclude that the maximum possible value of). (n) is
n(n + 1) 2
0 Prove that for any odd prime number p, the number of

positive integers n satisfying p I n! + 1 is no more than
cp t , where c is a constant number independent of p.
(Posed by Yu Hongbing)
Proof Clearly, if n satisfies the required property, then 1 ~
n ~ p - 1. Denote all such n 's by n 1 < n 2 < ··· < n « ; we shall
show that k ~ 12p f. If k ~ 12 there is nothing to prove. In
what follows, we assume that k > 12.
Rename n i+1 - n; (1 ~ i ~ k - 1) in nondecreasing order as
1 ~ p. 1 ~ p. 2 ~ ••• ~ p. H . It is clear that
k--1 k
~p.; = ~ Cn i+1 -n;) = n,. -n1 < p. <D

i=l i=l
First, we show that for any s ~ 1,
I {1 ~ i ~ k - 1 :p. i = s} I~ s,
i.e. there are at most s p.,'s equal to s.

In fact, suppose that n n-1 - n; = s ; then n; ! +1 = n i+1 !+
1 = 0 ( mod p) , so (p , n d) = 1, and
(n; +s)(n; + s -1)···(n; + 1) = l(mod p).
Thus, n; is a solution to the congruence equation
(x + s) (x + s -l)···(x + 1) = l(modp).
Since p is a prime number, there are at most s solutions to
the above equation, thanks to Lagrange's theorem. Thus, there
are at most s n,'s withn1+1 -n, = s, i.e. ®holds.
Now, we show that for any nonnegative integer l , if
l(l + 1) + 1 ~ k - 1 , then ,u ID:fl1+1 ~ l + 1. Suppose on the
2
contrary that ,u ~1 ~ l. Then ,u 1 , ,u 2 , ••• , ,u ~H are all
positive integers between 1 and l. By ®, there is at most one
,u; equal to 1, at most two ,u; 's equal to 2, ... , at most l ,u; 's
equal to l , and thus there are at most 1 + 2 + ... +l =
l(l + 1)
2
.U• 's less than or equal to l, which contradicts the assumption
that ,u 1, ,u 2, ••• , ,u ~1 are all less than or equal to l.
z
Let m be the largest positive integer with m(m

2
+ 1) + 1 <
k -1. Then
m (m2 + 1) +1 ~ k - 1 < (m + 1)2(m + 2) + 1' @
and hence
l-1 m--1
.L; ,u i ~ .L; (,u ili±ll+1 + ,u ili±ll+2 + ... + ,u !.i±lli.rl!2 )

i= 1 i= O 2 2 2
m--1 m--1
~ .L; Ci + D,uili±l..l+1
2
~ .L; Ci + 1)2
i=O i=O
m (m + 1) (2m + 1) m3
6 >3.
Since k > 12, m ~ 4, combining <D and @ we get
k < 2 + (m + 1) (m + 2)
2
k---1 2
<4m 2 <4(3~f.L;)1"
z
<4 X (3p)3.
This completes our proof.
Second Day
(0800 -1230; April1, 2009)
0 Let a , b be positive real numbers with b - a > 2. Prove

that for any two distinct integers m, n in the interval [a,
b) , there is a nonempty set S consisting of some integers
ITx
in the interval [ab, (a + 1) (b + 1)) , SUCh that xES
mn
is a
square of a rational number. (Posed by Yu Hongbing)

Proof We first prove the following lemma:
Lemma Let u be an integer with a ~u <u +1 <b. Then there
are two distinct integers x, y in the interval [ab, (a + 1) X
(b + 1)), such that u c:: 1) is a square of an integer.
Proof of lemma. Let v be the smallest integer not less than

ab .
- , 1. e.
. f"tes
v sat1s
u
hence
ab < uv < ab + u ( < ab +a + b + 1) , <D
and thus
ab < (u +l)v = uv +v <ab +u +ab +1 < ab

u
+a +b +l(sincea ~u <b). ®
(Here we have used a well-known result: the functionf(t) = t +~b

(a ~ t ~b) attains its maximum at t =a or b.)
By CD and®, we see that uv and (u + 1)v are two distinct
integers in the interval I = [ab, (a+ 1) (b +1) ). Let x = uv and
y = (u + 1)v. Then u(ux: 1) = v 2 is a square of an integer
number. We have verified the lemma.

Going back to the original problem, suppose that m < n.
Then a ~m ~ n - 1 < b. It follows from the lemma that for
every k = m , m + 1 , ... , n - 1 , there exist x k , y k , two distinct
integers in the interval [ab, (a + 1) (b + 1)) , and integer Ai,
such that
Multiplying all together, we find that
n-1
mn(m ~~1m)Z•••(n-l)Z = !!.Ai

is a square of an integer.
Let S be the set of numbers that appear in X;, y; (m ~i ~
n - 1) odd times. If S is nonempty, then it follows from the

IIx
above equality that xEs is a square of a rational number.
mn
If S is empty, then mn is a square of an integer. Since a +
b > 2 .;;;.b, we have ab + a + b + 1 > ab + 2 .;;;.b + 1, i. e .
../(a + 1) (b + 1) > .;;;.b + 1, which means that there is at least
an integer in the interval [ a 1 J(a + l)(b + 1) ), As a reSUlt

there is a perfect square in the interval [ab 1 (a + 1) (b + 1)).
Suppose that r 2 E [ab' (a + 1) (b + 1)) (r E Z) and let s' = I
ITx
2
{r }. Then xES' is a square of a rational number.
mn
0 Let m be an integer greater than 1 1 and let n be an odd

number with 3 ~ n <2m. Numbers a;, 1 ( i 1 j E N1 1 ~
i ~m, 1 ~j ~n) satisfy:

(1) For every 1 ~ j ~ n, a 1 , 1 , a 2 , 1 , ••• , amd is a
permutation of 1, 2, ... , m;
(2) I a;,J -a;,j+l I~ 1 for every 1 ~i ~m, 1 ~j ~n-1.
"
Find the minimal possible value of M = m.ax 2,:; a;, 1 •
t,;;;;.,;;;;m j=1
(Posed by Fu Yunhao)
Solution Letn = 2l +1. Since3 ~n <2m, we have 1 ~ l ~
m -1. We first estimate the lower bound of M.
By the condition ( 1) , there exists a unique 1 ~ i o ~ m , such
that a;0 , 1+1 = m. Consider a;0 , 1 and a;0 , Hz.
Case 1: At least one of a;0 , 1 and a;0 , Hz ism, and we may
assume without loss of generality that a;0 , 1 =m. It follows from
the condition (2) that
a;0 ,1-1 ?::-m - 1, a;0 ,t-z ?::-m - 2, ... , a;0 ,1 ?::-m - l +1,
a;0 , 1+2 ?::- m -1, a;0 , 1+3 ?::- m- 2, ... , a;0 , 21+1 ?::- m -l.
Thus,
"
M ?::- .2:::; a; 0
.;
j= l
?::- (m - l ) +2((m - l +1) + (m - l +2) +··· +m)

= (2l +Dm - l 2 •
Case 2: None of a;0 ,1 and a;0 ,1+z ism, and by the condition
(1) thereexists1~i~ ~m, i1 *io,suchthata; 1 ,~ =m. Iteasily
follows from the conditions (1) and C2) that a;1 , 1+1 = m - 1,
a;1 , 1+2 = m. It follows again from the condition (2) that
a,l'l-1 ~m -1, a,l't-z ~m -2, ... , a,l'1 ~m - l +1,

a; 1 , 1+3 ~ m - 1, a; 1 , z-H ~ m - 2, ... , a;1 , 21+1 ~ m - l + 1.
Thus,
n
M~ ~a;l'i ~2((m - l +1) +(m - l +2) +··· +m) +(m -1)

j- 1
= (2l +Dm- Cl 2 - l +1).
Combining the aoove two case, we have M ~ (2l + 1)m -l 2 •

On the other hand, consider
2i + j' 2i +j ~m,
a;, i = f(2i +j) =

j (2m + 1) - (2i + j) '
(2i + j) -2m,
( 4m + 1) - (2i + j) '
m+1
2m+1
3m+1
~2i
~2i
~2i
+j
+j
+j
~2m,
~3m.
~4m.
We shall show that this table of numbers satisfies the

required conditions in the problem.
For any 1 ~ i ~ m, 1 ~ j ~ n - 1 , if m f 2i + j , then
I a,,j -a,,j+1 I =I JC2i +i)- JC2i +i +D I= 1;

if m I 2i + j , then
I a,,j -a,,j+1 I =I JC2i +i)- J(2i +i +D I= o.

The condition (2) is verified.
We next show that the condition (1) is also fulfilled. In
fact, it suffices to show that for any integers 1 ~ j ~ n and 1 ~
k ~ m, there exists an integer 1 ~i ~m such that a;.i = k.
Ifj -k (mod2), since1 ~j ~n, 1 ~k ~m andn <2m,
k-'
we have-2m <k -j <m, and therefore-m <~ <m, and
k-' k-'
note that~ is an integer. Thus, at least one of~ and
k ; j +m is in the set {1, 2, ... , m}; taking this number to be
i will do the job.

Ifj ¥:-k (mod2), again since 1 ~j ~ n, 1 ~ k ~ m andn <
2m, we have
- 2m < (2m + 1) - (j + k) < 2m,

and therefore
(2m +I)- (j +k)

-m < 2
<m,
(2m +1) -(j +k) . .

and 1s an mteger. Thus, at least one of
2
(2m+l)-(j+k) d(2m+l)-(j+k)+ . . h {
an m IS m t e set 1 ,
2 2
2, ... , m} ; taking this number to be i will do the job.
We now estimate Min this case. Since the condition (1)
holds, for any1 ~ i1 < i2 ~ m, 1 ~j ~ n-1, we havej(2il +
j) -# f(2i2 + j), i.e. for any integers x, y with the same parity
such that 3 ~x <y ~ 2m + n andy - x < 2m, we have f(x) -#
f(y). Thus, for a given i, a;,1, a;, 3, ••• , a;, 21+1 are pairwise
distinct, and so are numbers a;, 2, a;, 4, ••• , a;, 21• As a result,
n
~a;d ~ (m -l) +2((m - l +1) + (m - l +2) + ... +m)
j= l
= (2l +Dm - l 2 •
n
Thus, M = max~a;,j ~ (2l +1)m - l 2 •
l.;;;i.,;m j=l
The minimal possible value of M is equal to

(2l +1)m -l 2 =mn- ( n T 1) . 2
0 Prove that in an arithmetic progression consisting of 40

distinct positive integers, at least one of the numbers
cannot be written as 21 + 31 , where k , l are nonnegative
integers. (Posed by Chen Yonggao)
Proof Suppose on the contrary that there exist 40 distinct
positive integers in arithmetic progression such that each term
can be written as 2k + 31 , and denote this sequence by a , a +d,
a + 2d, ... , a + 39d, where a, d are positive integers. Let
m = [logz (a + 39d)], n = [log3 (a + 39d) ].
In what follows, we first show that at most one of a +26d,

a +27d, ... , a +39d cannot be written as 2"' +3 1 or 21 +3" (k,
l are nonnegative integers) .
Suppose that a +hd cannot be written as 2m + 31 or 21 + 3" ,
for some 26 ~h ~39. Then, by assumption, a +hd = 26 +3' for
some nonnegative integers b , c. By the definition of m and n ,
it is clear that b ~ m, c ~ n. Since a + hd cannot be written as
2"' + 31 or 21 + 3" , we have b ~ m - 1, c ~ n - 1.
Ifb ~m -2, then
a + hd ~ 2"'-2 + 3"-1 = _!_ X 2"' + _!_ X 3"

4 3
7
~
12
X (a +39d) <a +26d,
a contradiction.
Ifc ~n-2, then
11
~
18
X (a +39d) <a +26d,
also a contradiction.
It follows that b = m -1, c = n -1, which implies that at
most one of a +26d, a +27d, ... , a +39d cannot be written as
2m + 31 or 21 + 3n.
In these 14 numbers, at least 13 numbers can be written as
2m + 31 or 21 + 3n. By the pigeonhole principle, at least 7
numbers can be written in the same form. We shall discuss two
cases.
Case 1 : There are 7 numbers in the form of 2m + 31 ,
denoted by
where l1 < l2 < ... < l1. Thus, 311, 31z, ••• , 317 are the 7 terms
of an arithmetic progression with 14 terms and the common
difference d. However,
a contradiction.
Case 2: There are 7 numbers m the form of 21 + 3" ,
denoted by
where kl <k2 < ... <k7. Thus 211' 21z' ••• ' 2k1 are the 7 terms
of an arithmetic progression with 14 terms and the common
difference d. However,
a contradiction.
It follows from the above arguments that our assumption at
the very beginning is false, which completes the proof.
2010
First Day
(0800 - 1230; March 27, 2010}
0 For acute triangle ABC with AB > AC, let M be the

midpoint of side BC and P a point inside D.AMC such that
L.MAB = L.PAC. Let 0, 0 1 and 0 2 be the circumcenters
of D.ABC, D.ABP and D.ACP respectively. Prove that
line AO bisects segment 010z. (Posed by Xiong Bin)
Proof I As shown in Fig. 1, draw the circumcircles of D.ABC,
D.ABP and D.ACP , respectively. Let the extension of AP
meet 00 at D, join ED, and draw the line tangent to 00 at
A, intersecting 0 01 and 00 z atE and F respectively.
It is clear that D.AM C (/) E
D.ABD , hence
AB AM
ED =Me
Since D.EAB (/) D.PDB,

AB AE
we have ED = PD"
D
AM
Consequent1y, MC AE .
= PD, 1. e. Fig.l
AE =AM X PD
MC '
and, similar!y ,
AF =AM x PD
ME
It follows that
AE =AF. CD
Draw the perpendicular lines 01 E' j_ AE with foot E ' , and
OzF' j_ AF with foot F'. Since E', F' are the midpoints of
AE, AF respectively, it follows from CD that A is the midpoint
of E'F'.
In the right-angled trapezoid OtE' F' Oz, AO is the
extension of the median, and hence it bisects the segment
OtOz.
Proof IT As shown in Fig. 2, draw A
segments A01 , COt , AOz , COz . Denote
by Q the intersection of AO and 010 z .
Then
01 Q - S L:;AOO I AB xoo1 8
Q0z - SL:;Aoo 2 ACxOOz'
AB sin.LACB
where AC = sin.LABC"
Since .LOOtQ = .LEAP = .LCAM, and .LOOzQ = .LCAP =
L.BAM, it follows that
OOt = OOt X OQ
OOz OQ OOz
= sin.LOQ0 1 X sin.LOOzQ
sin.L001Q sin.LOQOz
sin.LOOzQ sin.LBAM
sin.L001Q sin .LCAM'
and thus
01Q = sin.LACM X sin.LBAM = AM X BM = BM

Q0 2 sin.LCAM sin.LABM CM AM CM"
Note that M is the midpoint of BC, and therefore 01 Q

QOz, i.e. line AO bisects segment 0102.
0 LetA= {a1, az, ••• , azo1o} andB = {b1, b2, ••• , bzo1o}
be two sets of complex numbers, such that the equality
~ (a; +ai )~ = ~ (b; +bi )~

1.,;;i<i.,;;2010 1~i<i ~2010
holds for every n = 1, 2, ... , 2010, Prove that A =B.

(Posed by Leng Gangsong)
2010 2010
Proof Let s~~ = ~a~ and s~~ ~M. We first show by
i=l i=1
induction that S 4 = S 4 fork = 1, 2, ... , 2010.

Setting n = 1 in the given equality, we have 200951
2oogs1, and hence Assume that s j =
s1 = s1. for j = 1, sj
2, ... , k -1, where 2 ~ k ~ 2010; we are going to show that
s. = s •.
By the binomial expansion theorem, we have
~
1~i<i~2010
(a; +ai) 11
1.;;;~.;;za1o t (~ )a~ar-z
i-1 k
= 20095"' + ~ ~ ( )alat-1
1~i<i~201o 1- o l
i-1 k
= 2009S~ + ~ ~ ~ ( )a~a7-l
1~i;o!oj~2010 1= 1 l
1 k---1 2010 k
= 2009Si +2 ~ ~( )a~(SH -a~)
!= 1 i= 1 l
1 k---1 k 2010 2010 k
= 2009S. +2 ~( ( )sH ~a~ - ~( l )at)
1=1 l i=1 i-1
Similarly, we have
Since
by CD, ® and inductive hypothesis S, = S, for i = 1, 2, ... ,

k - 1, we have S" = S~t Cit is worth noting that 2010 is not a
power of 2, i.e. 2010 - 21<-l =I= 0 ) . This completes the inductive
proof that sl = s . for all k = 1' 2' ... ' 2010.
Set
By Newton's formula, we have
s- . +B1 Si-1
- +··· +Bi.-1 S1
- +kB._ = 0, ®
fork = 1, 2, ... , 2010.
It follows from@, ®and s" = s"' k = 1, 2, ... ' 2010,
by the easy inductive argument, we have
A" = B" , k = 1, 2, ... , 2010.

The right hand sides of equations® and@ are equal, and
so are their left hand sides, i.e. A =B.
0 Let n 1 , n z , ••• , n zs be pairwise distinct positive integers,

satisfying:
(1) In the decimal representation of each n; , each digit
belongs to the set {1 J 2 };

(2) For any i J j t ni cannot be obtained from n; by
adding some digits on the right.
26
Find the least possible value of ~ S (n;) J where S ( m)
i=l
denotes the sum of all digits of m in decimal

representation. (Posed by Fu Yunhao)
Solution Given two positive integers a , b in decimal
representation, we say a contains b if a can be obtained from b
by adding some digits on the right. We first prove a lemma.
Lemma Let n 10 n 2 ' ••• ' n r be pairwise distinct positive
integers with digit 1 or 2. If none contains another t then the
number of n;'s with S(n;) ~ t is at most F., where t is an
arbitrary positive integer and F. is a Fibonacci number satisfying
F1 = 1, Fz = 2, F.rrz = F.rrt +F,.(n ~ 1).
Proof of lemma. We induct on t. It is clear for t = 1, 2

(when t = 2, 1 and 11 cannot both appear). Suppose that the
lemma is true for all positive integers less than t (t ~ 3); we
shall prove that it is also true for t. Suppose that without loss of
generality S (n 1) , S (n z) , ... , S (n 1) are all the numbers with
the sum of digits ~ t, where n 1, n zt ••• , ni start with 1 and
ni+l• n;H, •.• , n1 start with 2. If one of n1, nz, ••• , n; is 1,
then j = 1 ~ FH , otherwise by deleting the first digit of n 1 ,
n2t ••• t n i we obtain j positive integers with none containing
another and the sum of digits~ t -I, and thus we again have
j ~ F H by the inductive hypothesis. Analogously t we have l -
j ~ F t--2, and therefore l ~ F H +F t--2 =F., i.e. the lemma is
also true for t. The proof of the lemma is completed.
Going back to the original problem, we consider a more
general question. Replacing 26 by m t denote the least possible
m
value of ~ S (n,) by f (m) . Fix m ~ 3, and let n 1, n z , ••• , n m
i=l
be a set of numbers satisfying the conditions in the problem

which attains the minimum f (m). Without loss of generality,
assume that rnaxS(n,) = SCn1) and n1 is maximum among all
l~i:s;;;m
these numbers attaining the maximum digital sum. Since m ~ 3,

n 1 contains at least two digits.
n1-1
If the last digit of n 1 is 1, replace n 1 by ----ro- , which is
not one of n 2 , n 3 , • , , , nm , otherwise n 1 would contain some
n,. N otlce ----ro-,

. t h at n 1 -1 n z, •.. , nm agam
. satis
. f y t he cond'1t10ns
.
in the problem, for if n; contains n\~ 1

for some i ~ 2, then
S(n;) > SCn1) andn; > n1, a contradiction. Now
a contradiction to the definition of f(m). Thus, the last digit

of n1 is 2.
If n 1 - 1 is not one of n 2 , n 3 , , •• , nm, replace n 1 byn 1 -
1, and these m numbers again satisfy the conditions in the
problem, for if n; contains n 1 - 1 for some i ~ 2, then n, must
be 10(n 1 - 1) + 1, S(n,) = S(n 1 ) ; however, n; > n 1 is a
contradiction to the choice of n 1. Now
a contradiction to the definition of f(m). Thus, n1 -1 appears
Without loss of generality, assume that n 2 = n 1 - 1.

'd
Cons1 er ----ro-,
n1 -2 n 3 , ••• , nm ;
.
smce n1 -2
~
..J..
-r- n;
f
or z. .::::::::-
. .__
3 , these
are m - 1 pairwise distinct numbers. There is no containment
among n 2 , • • • , nm , and ----Io

n -2
does not contain any of
n s , ••• , n m , otherwise n 1 would contain that number. If one

. ----rQ•
o f n3, ... , nm contams n1
~
-2
say ns, smce S (n1 - . 2) =
2, n 3 is obtained by adding 1, 2 or 11 after n ~~

2
S(n 1) - .
Adding 1 or 2 yields n 2 , n 1 , and we must have n 3 = 100 •
----w-
n1 -2
+ 11 = 10nl - 9. Now S(n3) = SCn1) and n3 > n1, a
. ·
contrad lCtlOn tO t he Ch 0100
· 0f n1 - 2 n3,
n 1 • S0 ~, ••• , nm
satisfy the conditions in the problem, and therefore the sum of

their digits is at least f(m -1). Thus,
j(m) - SCn1) - CSCn1) -1) + CSCn1) - 2) ~ j(m -1),
i.e.
f(m) ~f(m -1) +SCn1) +1.
Let u be such that F ..- 1 < m <:F... By the lemma, there are
at most F,.- 1 of S(n 1 ) , S(n 2 ) , • , • , S(nm) less than or equal
to u - 1, so S (n 1) ~u, and
f(m) ~f(m - 1) +u +1.
It is easy to see that j(l) = 1, j(2) = 3, and hence

26
j(26) = j(2) + ~ (j(i) - f(i -1))
i- 3
= j(2) + (j(3) - j(2)) + (j(5) - j(3)) + (j(B) - j(5))
+(j(13)- /(8)) +CJ(21)- /03)) +CJ(26)- /(21))
~3+4X1+5X2+6X3+7X5+8X8+9
X 5 (by equation (D)

= 179,
25
i.e. ~ S(n;) ~ 179.

i=l
On the other hand, by the property of Fibonacci numbers,

there are exactly 8 numbers consisting of digits 1 and 2, with
digital sum 5, denoted by a1, az, ... , as, and there are exactly
13 such numbers with digital sum 6, denoted by b 1 , b 2 , ••• ,
b13. Add a digit 2 after each of a1 , az, .•• , as, denoting these
new numbers by c1, Cz, ••• , ca. Add a digit 1 (resp. digit 2) to
each of b1, bz, ba, b4, bs, denoting these new numbers by d1,
dz, da, d4, ds (resp. e1, ez, ea, e4, es). Now consider
Ct , Cz, ••• , cs, d1, dz, •.. , ds, e1, ez, ••• , es, bs, b7, ••• , bts.
These are pairwise distinct numbers consisting of digits 1 and 2,

with total digital sum 7 x 8 + 7 x 5 +8 x 5 +6 x 8 = 179. And
there is none containing another. In fact, if x contains y, since
their digital sum is either 6, 7 or 8, and a number with digital
sum 8 ends up with 2, it follows that x has exactly one more
digit than y. However, deleting the last digit of dtt dz, ... ,
ds and e1, ez, .•. , es yields b1 , bz, ... , bs, and deleting the
last digit of c1, Cz , ••. , cs yields a1, az, •.• , as, none of
which is in this set of 26 numbers.
26
We conclude that the least possible value of .L; S (n;)
is 179.
Second Day
(0800 -1230; March 28, 2010)
0 Let G = G (V; E) be a simple graph with vertex set V and

edge set E, and assume that IV I= n. A map /:Y -zis
said to be good if f satisfies:

(1) ~f(v) =IE I;
vEV
(2) If one colors arbitrarily some vertices into red, there
exists a red vertex v , such that f ( v) is not greater
than the number of vertices adjacent to v that are not
colored into red.
Let m CG) be the number of good maps f. Show that if
each vertex of V is adjacent to a least one other vertex,
thenn ~m(G) ~n!. (Posed by Qu Zhenhua)
Proof Given an ordering r = Cv 1 , v z , ••. , v") on the
vertices in V, we associate a map f V- Z as follows: f r ( v) is
r :
equal to the number of vertices in V that are ordered preceding

v. We claim that fr is good.
Each edge is counted exactly once in ~ f r ( v) , for an edge
vEV
e E E with vertices u, v E V such that u is ordered before v in
r; then e is counted once in f r ( v) . Thus,
For any nonempty subset A c Vof all red vertices, choose

v E A with the most preceding ordenings in r. Then by
definition, fr (v) is not greater than the number of vertices
adjacent to v that are not colored into red. We have verified
that f r is good.
Conversely, given any good map f :V- Z, we claim that
f = fr for some ordering r of V.
First, let the red vertice setA = V . By the condition (2) in
the problem, there exists v E A such that f (v) ~ 0, and denote
one of such vertices by v 1 • Assuming that we have already
chosen v 1 , • • • , vi from V, if k < n , set the red vertice set
A = V- {vl, ... , vk }. By the condition (2) in the problem,

there exists v E A such that f ( v) is less than or equal to the
number of vertices in v 1 , ... , v k that are adjacent to v.
Denote one of such vertices by v H-1· Continuing in this way, we
order the vertices by r = Cv1, vz, ..• , v,.). By the
construction we have f(v) ~ fr(v) for any v E V. By the
condition (1) in the problem, we have
IE I= ~f(v) ~ ~fr(v) =IE I,

vEV vEV
and thereforef(v) = fr(v) for anyv E V.

We have shown that for any ordering,, f. is good, and
any good map f is f, for some r. Since the number of orderings
on V is n! 1 we see that m(G) ~ n! (note that two distinct
orderings may result in the same map).
Next, we prove that n ~ m(G). Assume at the moment
that G is connected. Pick arbitrarily v 1 E V. By the
connectivity, we may choose v z E V - {v d such that v z is
adjacent to v1, and again we may choosev3 E V- {vl, vz}
such that v 3 is adjacent to at least one of v 1 , v z . Continuing in
this way, we get an orderingr = Cv1, Vz, .•• , v,.) such that vk
is adjacent to at least one of the vertices preceding it under
orderingr, forany2~k ~n. Thus,fr(v1) =Oandfr(vk) >
0 for 2 ~ k ~ n. Since v 1 may be arbitrary, we have at least n
good maps.
In general, if G is a union of its connected components
G1, ... , Gk, since each vertex is adjacent to at least another
vertex, each component has at least two vertices, denote by
n1 1 ••• 1 nk ~ 2 the number of vertices of these components.
For each G;, we have at least n; good maps on its vertices, i =
1, ... , k. It is easy to see that patching good maps on G,'s
together results in a good map on G, and thus
We conclude that n ~ m(G) ~ n !.
0 Given integer a1 > 2, for n > 2, define a,. to be the least

positive integer not coprime to a,.-1 and not equal to a1,
a2 , ••• , a,.- 1 • Prove that every integer except 1 appears
in the sequence {a,.}. (Posed by Yu Hongbing)
Proof We proceed in three steps:
Step 1: We prove that there are infinitely many even
numbers in this sequence.
Suppose on the contrary that there are only finitely many
even numbers, and there is an integer E, such that all even
numbers greater than E do not appear in the sequence. It
follows that there exists a positive integer K such that a,. is an
odd number greater than E for any n > K. Then there is some
n1 >K such that a,. 1+1 > a,. 1 (otherwise the sequence is strictly
decreasing after a,. 1 , a contradiction).
Let p be the smallest prime divisor of a,. 1 , p > 3. Since
we have a,. 1H - a,. 1 > p, i.e. a,. 1+1 > a,. 1 + p.

On the other hand, a,. 1 +pis even and greater thanE, so
it does not appear before a,. 1 , and therefore a,. 1H = a,. 1 + p,
which is even - a contradiction.
Step 2: We prove that all even numbers are in this
sequence.
Suppose on the contrary that 2k is not in this sequence and
is the smallest such even number. Let {a,., } be the subsequence
of {a,. } consisting of all even numbers. By step 1, it is an

infinite sequence. Since (a,. , 2k) . > 1 and 2k (/:. {a,.} , we have
a,.,+1 ~ 2k by definition.
However, {a,. 1 +1} is infinite - a contradiction. Thus,
{a,.} contains all even numbers.
Step 3: We prove that {a,.} contains all odd numbers
greater than 1.
Suppose on the contrary that 2k +1 is an odd integer greater
than 1 which is not in {a,.}, and is the smallest such number.
By step 2, there is an infinite subsequence { am. } of {a,. }
'
consisting of even numbers that are multiples of 2k + 1. Arguing
analogously as in step 2' we have am,+l ~ 2k + 1' i = 1' 2' ... '
a contradiction.
We have shown that {a,} contains all positive integers
except 1.
0 Given integer n ~ 2 and real numbers x1, x2, ... , x, in

the interval [0, 1], prove that there exist real numbers ao,
a 1 , ... , a,. satisfying simultaneously the following
conditions:
(1) ao +a,. = 0;
(2) I a, I~ 1, for every i = 0, 1, ... , n;
(3) I a; - a;- 1 I = x;, for every i = 1, 2, ... , n.
Proof For any a E [0, 1), define a sequence {a, }~=o generated
by a as follows: ao =a fori ~i ~n. a, =a;-1 -x, ifa;-1 ~0,
and a; = a;-1 + x; if a;-1 < 0,
Set f(a) =a,.. It is easy to show by induction that I a; I ~ 1
for every 0 ~ i ~ n.
If there existsa E [0, 1) such thatf(a) =-a, consider the
sequence generated bya, ao =a, a1, ... , a,. = f(a) =-a.

Clearly, this sequence satisfies the conditions (1) and (3). By
the recursive relation, it also satisfies the condition (2). Thus,
it suffices to show that there exists a E [ 0, 1) such that
f(a) =-a.
For any a E [0, 1) , we say that a is a breaking point if at
least one term in its generating sequence is 0. Since every
n
breaking point is of the form ~t;x;, where t; =-1, 0, 1,
i- 1
there are finitely many breaking points.

Clearly, 0 is a breaking point; label all breaking points in
increasing order by 0 = b1 < b2 < ··· < bm < 1.
We first prove that for 1 <k <m - 1, f(a) = f(bk) +
(a -b .. ) for everya E [b .. , b~t-t-1).
Consider b.. , bH1 and their generating sequences. Assume

that qo = b._, q1, q2 , •.• , q,. is the generating sequence of b._,
and ro = bH-1, r1, r2, ..• , r,. is the generating sequence of
bHl· Suppose that r1 is the first term of {r; }i- o equal to 0.
Construct a sequence {s; }?=o as follows:
s l+l = - r l+l ' ••• ' s,. =- r n.
It is clear that the sequence {s; }?=o satisfies so = bw; and

for 1 0, and S; = S;-1 +X;
if S;-1 < 0.
We prove by induction that q;s; ~ 0 ands; - q, = bH-1 - b._.
The conclusion is obviously true fori = 0. Assume that it holds
fori -1. Thenq;-1S;-1 ~0 ands;-1 -q,-1 = bH-1 -b .. >O, which
implies that q;-1 ~ o, S;-1 > o, or q;-1 < o, S;-1 < o. In the
former case, q, = q;- 1 - x,, s, = s;-1 - x,, and thus s, - q, =
s;-1 -q;-1 = bH-1 -b •. Similarly, in the latter case, we have

s, -q, = bH-1 -b•. Ifq;s; <0, thenq, <0 <s;. Seth' =bH-1 -
s, = b• + (- q,) E (b•, bH-1), and consider the generating
sequence of b', uo = b', u1, ... , un. It is easy to show by
induction that s; -u; = s 0 -u 0 = s; for any 0 ~j ~ i (q;-1 and
s;-1 both add or subtract x; for j < i; u; lies between q;-1 and
s;-1, so the recursive relation is the same). Then u; = s; - s; =
1
0, i.e. b is a breaking point - a contradiction to b•, bH1
being two consecutive breaking points. Therefore, q,s, ~ 0. By
induction we have verified thatq;s; ~0 ands, -q, = b1<+1 -b. for
allO ~ i ~ n.
Since f(b.) = q"' f(bi.H) = rn =- s,.' we have f(bk) +
f(bH-1) = b~. - bH-1· It follows from the above argument that,
for any b~t. < b' < bH-1, the generating sequence of b' has the
same recursive relation as {q, }?=o and {s, }?=o, and hence
f(b') = /(b,) + (b' -b,).
Let us go back to the original problem.
If f(b.) =-b, for some k, we are done. If f(b~.) = b" for
some k, then consider the generating sequence of bk, reversing
every term after the first 0, and we obtain a new sequence zo =
b" , z 1 , ... , z,. = - bk, which satisfies the required conditions.

Now assume that I f(b«) I# b« for every k, and we shall
consider two cases to show thatf(a) =-a for some a E [0, 1):
Case 1: I f(bm) I< bm, Since I /Cb1) I> b1 = O, there
exists k such that I f(b") I> b", I f(bH-1) I< bH-1·
Since /(b.)+ /(bH-1) =b. - bH-1• we have /(b.) -b. =
- (j(bH-1) +bH-1) <0, andhencej(b") <-b•. Again by f(b «) +
f(bH-1) = bk - bw, we have
i.e.
b1 - 2bw < f(bl) <-bk.
' blt; -j(bk)

Let b =
2
. Then b1 bm. Since there is no breaking number
in (bm , 1) , we see from the previous argument that for any
b' E (bm, 1), the generating sequence of b' and the generating
sequence of bm have the same recursive relation, and hence
Since I f I,;;;;; 1, we have f(b,.) ,;;;;; b,., and hence
-1,;;;;; f(b,.) <-b,..
Let b' = b,. - {(b,.). Then
b,. = b,. - ~- b,.) < b' < b,. - i- 1) = bm t 1 < 1,
J(b') = J(b,.) + (b'- bm)

= (b,. - 2b') + (b' - b,.) =- b'.
The result again follows.

China Girls' Mathematical
Olympiad
2008
0 (1) Can one divide the set {1 , 2, ... , 96} into 32 subsets,
each containing three elements, and the sums of the
three elements in each subset are all equal?
(2) Can one divide the set {1, 2, ... , 99} into 33 subsets,
each containing three elements, and the sums of the
three elements in each subset are all equal? (Posed by
Liu Shixiong)
Solution (1) No. As
1 + 2 + ··· + 96 =
96 X (~ 6 + 1) = 48 X 97,
and 32 '} 48 x 97.

(2) Yes. The sum of the three elements in each set is
1 + 2 + ··· + 99 = 99 X (99 + 1) = 150

33 33 X 2 '
We can divide 1, 2, 3, ... , 66 into 33 pairs, such that the

sums of these pairs form an arithmetic sequence:
1 +50, 3 +49, ... ' 33 +34, 2 +66, 4 +65, ... ' 32 +51.
Hence, the following decomposition satisfies the requirement:

{1, 50, 99}, {3, 49, 98}, ... '{33, 34,83}, {2, 66,82},
{4, 65, 81}' .. . ' {32, 51, 67}.
Remark The general case is as follows:
Let the family of subsetsA; = {x;, y;, z;} of the setM =
{1, 2, 3, ... , 3n}, i = 1, 2, ... , n, satisfy At U A2 U ••o U
An = M. Writes; = x; + y; + z;, and find all possible values of
n, such that the s~ s are all equal.
This can be answered as follows: First, n I 1 + 2 +3 + · +
o•
3n, i.e.
n l 3n( 3 ~ +1) =;>2 I 3n +1.
Hence, n must be odd.

For n odd, 1, 2, 3, ... , 2n can form n pairs such that the
sums of each pair become an arithmetic sequence of common
difference 1 :
1 + ( n + -n+1)
- , 3 + ( n + -n-1)
- , .•• , n + (n + 1);
2 2
2 +2n, 4 + (2n -1), 0 •• , (n -1) + ( n + -n +3)

- o
2
Its general term is

2k -1 + ( n + n t 1
+ 1- k), 1 ~k
n +1
~-2-,
ak = { [1 - n + 2(k -1)] + [ 2n + n t 1 - (k -1)], -n +3

2
- ~k ~n.
It is easy to see that ai + 3n + 1 - k =

9
n t 3
is a constant,
so all the following n triples have the same sum:
{1, n + -n+1
- , 3n } ,
2
{3, n + -n-1
-,
2
3n - 1 } , ... ,
n +1} ;
{n, n +1, 3n +1--2-
n+3}
{2, 2n, 3n +1--- , ... , {n -1, n +n+3
-- , 2n +1 }.
2 2
For n odd, take these triples as A1, Az, ... , A,; then
they satisfy the required condition. So n can be any odd
number.
G The real polynomial cp(x) = ax 3 +bx 2 +ex +d has three

positive roots, and cp(O) < 0. Prove that

Proof We denote by x1, x2, x 3 the three positive roots of the
polynomial cp(x) = ax 3 +bx 2 +ex +d. By Vieta's theorem, we
have
= -ae ,
d
a
As cp(O) < 0, we getd < 0, and hence a > 0.

Dividing both sides of CD by a 3 , we get an equivalent form
of CD:
~ 7(xl +xz +x3)(x1xz +xzx3 +x3xl)

< 2(xl + Xz + x3) + 9xlxzx3
3
~ xfxz +xrx3 +x~x1 +x~x3 +x~x1 +x~xz

< 2(x~ +x~ +xD.
Because x1, xz, x 3 are all greater than 0, Cx1 - xz)(xr -
xD ~ 0. That is to say,
By the same argument, X~X3 + X~X2 <X~ +X~' X~Xl + xrx3 <
x~ +xL
Summing up these three inequalities we get ®, and the
equality holds iff x1 = xz = x3.
0 Find the smallest constant a > 1, such that for any point P
inside a square ABCD there exist two triangles among
..6.PAB , ..6.PBC , ..6.PCD , ..6.PDA , with the ratio
between their areas belonging to the interval [a- 1 , a].
(Posed by Li Weigu)
1 +JS . prove that a min
Solution amin =
2
. We fust < 1 +JS
2
Write cp =
1
~.j5. We may assume that each edge has length
./2. For any point P inside the square ABCD, let S1, Sz, S3,
S 4 denote the area of ..6.PAB , ..6.PBC, ..6.PCD , ..6.PDA
respectively; we can also assume that S1 ~ Sz ~ S( ~ S3.
c,..,-----...., o
Let A = ~> 11 = ~:- If A, 11 > CfJ• as . . . . . . . . . . . sl //
' /
s, p//<\
/ \
s.
/ \
/ \
/ s, \
/ \
we h ave 1 _S zS z = 11, S 2 So B A
2
p = _!!!__ = 1,
1+1_ 1+cp
cp
and we reach a contradiction. Hence, min {A, f.J.} < CfJ• which
implies that a min < cp.
On the other hand, for any a E (1, cp), we take any t E
1 ~JS
(a, ) such that b = 1~t > ~. Inside the square ABCD
we can choose a point P so that 5 1 = b, 5 2 = -,

b
53 b
t tz'
54 = 1 -b. Then we have
Sz = t E ( 1 +J5 )
53 a' 2 '
b b
t 2 (1 - b) > 4(1 -b) > 2 > a.
Thus, for any i, j E {1, 2, 3, 4}, we have~: tf: [a-1 , a].

J
Hence a min = cp.
0 Outside a convex quadrilateral ABCD we construct

equilateral triangles ABQ, BCR , CDS and DAP.
Denoting by x the sum of the diagonals of ABCD , and by
y the sum of line segments joining the midpoints of
opposite sides of PQRS , we find the maximum value of
y
(Posed by Xiong Bin)
X
1 + ,/3
Solution If ABCD is a square, then )'___
X 2
y p
Now we prove that ~
X
1 +,/3
2
s
Denote by P1, Ql, R1, S1 Q
the midpoints of DA , AB , BC,
CD , and by E, F, G, H the
midpoints of SP , PQ, QR , RS .
Then P1Q1R1S1 is a parallelogram.
R
Now draw lines P1E, S1E,
and denote by M, N the midpoints of DP, DS. Then
DS1 = S1N = DN =EM,

DP1 = P1M = MD = EN,
and
L P1DS1 = 360° -60°-60°- L PDS

= 240°- (180° - L END) = 60° +LEND
= LENS1 = L EMP1.
So we have 6.DP1S1 (/) 6.MP1E (/) 6.NES1. Hence,

6.EP 1 S 1 is equilateral.
By the same argument, 6.GQ1R1 is also equilateral. Now
let U, V be the midpoints of P1S1, Q1R1, respectively. We
then obtain
= P 1 Ql +v103 P 1 S1 = l_BD
2 + ,j3AC
2 ,
and also 1
FH ~z-AC + -J3
2-BD.
Taking the sum of these two inequalities, we have y ~
1 +J3 x, . e.
1.
2
!___ ~ 1 +J3
X~ 2
0 Suppose that the convex quadrilateral A

ABCD satisfiesAB = BC, AD =DC.
E is a point on AB , and F on AD,
such that B, E, F, D are concyclic.
Draw L DPE directly similar to B D
LADC, and LBQF directly similar

to LABC. Prove that A , P , Q are
collinear. (Posed by Ye Zhonghao)
c
Proof Denote by 0 the center of the Fig.l
circle that passes through B , E, F, D.
Draw lines OB, OF, BD.
In LBDF, 0 is the circumcenter, so L BOF = ZLBDA;
And D.ABD (/) D.CBD, so LCDA = ZL BDA. Hence, LBOF =
LCDA = LEPD, which implies that the isosceles triangles
D.B OF (/) D.EPD . CD

On the other hand, the concyclicity of B, E, F, D implies
that
L ABF (/) LADE.
Combining CD and (2), we know that the quadrilateral

ABOF(/) ADPE, so
LBAO = LDAP. ®
The same argument gives
L BAO = L DAQ.
®and@ imply that A, P, Q are collinear.

Remark In fact, when ABCD is not a A
rhombus, the collinearity of A , P , Q is

equivalent to the concyclicity of B , E, F, D.
This can be explained m the
D
following way. Fix the point E, and let
the point F move along the line AD. By
similarity, the locus of Q is a line that
passes P. Now it suffices to show that c
this locus does not coincide with the line Fig. 2
AP, i. e. to show that A is not on the locus.

To this end, we draw ~BAA' (/) ~B QF (/)~ABC (see
Fig. 3) . Then LBAA' = LAB C, which implies that A'A II
BC. As ABCD is not a rhombus, AD is not parallel to BC,
which implies that A 1 , A 1 , D are not collinear, i.e. A is not on
A'
",
''
''
''
''
A
D B D
c
Fig. 3 Fig. 4
the locus. Hence, Q is on the line AP only when B, E, F, D

are concyclic. And when ABCD is a rhombus (see Fig. 4) , for
any E and F the corresponding points P and Q are always on
the diagonal AC.
0 Suppose that the sequence of positive numbers x1, x2,

..• , x, , •.• satisfies C8x2 - 7x1 )xi = 8 and
Find positive real number a such that when x1 >a one has
x1 >x2 >··· >x, >···,and whenO<x1 <aonedoesnot
have such monotonicity. (Posed by Li Shenghong)
Solution
I. e.
X2 1 7
= X1 -X~ =g-·
Hence, xk+l = ~ xk +x"i7 , and whenx1 > 0, xk > 0, k ~ 2.
By x.H-1 - x" = x" ( x;B - ~ ) , we see that when x;B - ~ <
0, i.e. xk >Bi, onehasxki-1 -x. <0, i.e. Xi-f-1 <x"' k ~I.
And Xi-f-1 = ~ Xk + x"i ~ 7

8# = at , SO When Xk = at , the
equality holds. So if we take a = st , as soon as x 1 > st we have
x1 >x2 > ... >x,."'.
1
Whenx 1 <8s, we havex 2 >x 1 andx 2 >x 3 >"' >x,."'.
So the constant that we are looking for is a =8t.
0 For a chessboard of the size2008 X2008, in each case (they

all have different colors) write one of the letters C, G,
M, 0. If every 2 X 2 square contains all these four letters,
we call it a "harmonic chessboard." How many different
harmonic chessboard are there? (Posed by Zuming Feng)
Solution There are 12 x 22008 - 24 harmonic chessboards. We
first prove the following claim:
In every harmonic chessboard, at least one of the following
two situations occurs: ( 1) each line is composed of just two
letters, in an alternative way; (2) each column is composed of
just two letters, in an alternative way.
In fact, suppose that one line is not composed of two
letters; then there must be three consecutive squares containing
different letters. Without loss of generality, we may assume
these three letters to be C, G, M, as shown in Fig. 1. We then
get easily X 2 = X s = 0, X 1 = X 4 = M and X 3 = X6 = C, as
shown in Fig. 2.
x1 Xz x3 M 0 c
c G M c G M
x, Xs x6 M 0 c
Fig. l Fig. 2
The same argument shows that each of these three columns

is composed of two letters in an alternative way, and a fortiori
so is every column.
Now we calculate the total number of different harmonic
chessboards. If the leftmost column is composed of two letters
104- Mathematical Olympiad in China
Ceg. C and M), we see immediately that all the odd-numbered

columns are composed of these two letters, while the even-
numbered columns are composed of the other two letters. The
letter in the top square of each column can be either of the two
letters that compose this column; we check easily that it is a
harmonic chessboard. Therefore, we have (~) = 6 different
ways to choose the two letters of the first column, and 22008
ways to determine the letter in the top square of each column.
Hence, we get 6 x 22008 configurations to make each column
composed of two letters in an alternative way. We have also 6 X
22008 configurations to make each line composed of two letters in
an alternative way.
Then we need to subtract from the sum the configurations
that are counted twice, i. e. the configurations that are
alternative on each line and each column. Obviously, any such
configuration is in one-to-one correspondence to the 2 x 2 square
at the upper-left corner, which gives 4! = 24 different ways.
Hence, we get the above result.
0 For positive integer n, let f, = [2" ./2008] + [2" ./2009 ].

Prove that there are infinitely many odd numbers and even
numbers in the sequence h, !2 ,.... ([x] represents the
biggest integer that does not exceed x. ) (Posed by Zuming
Feng)
Proof We use the dyadic representations of ./2008 and ./2009 :
First, we prove that there are infinitely many even

numbers by contradiction. Suppose that there are only finitely
many even numbers in the sequence. Then there exists a

positive integer N, and for every positive integer n > N, f,.
must be odd. We consider n1 = N + 1, nz = N + 2, .... We
observe that in dyadic representation
This number is equal tob,., +a .. , modulo 2. As f,., is odd,

we have {b,.,, a,.,} = {0, 1}. Hence,
Therefore, ..,12008 + ..,12009 must be rational, which 1s

impossible, as we know that it is irrational. Hence, our
hypothesis must be wrong, which proves the existence of
infinitely many even numbers in the sequence.
In a similar way we can prove the existence of infinitely
many odd numbers in the sequence. Let
g,. = [2" ..,12009 J - [2" ..,12008].
apparently g,. and f,. have the same parity. Hence, forn > N,
g,. is even. We observe also that in dyadic representation
This number is equal to b,., -a,., modulo 2. As g,., is odd, we

have b,., =a,.,. Thus,
and this would imply the rationality of ..,12009 - ..,12008, which

is impossible. Hence, there are infinitely many odd numbers in
the sequence.
2009
First Day
( 0800 - 1200; August 13, 2009)
0 Show that there are only finitely many triples (a, b, c) of

positive integers satisfying the equation abc = 2009(a +b +
c). (Posed by Ieng Tak Leong)
Solution There are at most six permutations for any three
numbers x, y, z. It suffices to show that there are only finitely
many triples (a, b, c), with a ;? b ;? c, of positive integers
satisfying the equation abc = 2009 (a + b + c). It follows that
abc ~2009 X (3a) or be ~ 2009 X 3 = 6027. Clearly, there are
finitely many pairs ( b, c ) of positive integers satisfying the
equation b c ~ 6027 and for each fixed pair of integers (b, c)
there is at most one positive integer a satisfying the equation
abc = 2009(a + b + c) (because it is a linear equation in a).
8 A right triangle ABC, with

L BAC = 90°, is inscribed in
the circle r. The point E lies B i-==----+---+------J'-------1~
~
in the interior of the arc BC

(not containing A), with EA >
EC. The point F lies on the E
ray EC with LEAC = LCAF. The segment BF meets r

again at D ( other than B ) . Let 0 denote the
circumcenter of the triangle DEF. Prove that the points
A , C, 0 are collinear. (Posed by Bian Hongping)
Solution Let M and N be the feet of the perpendiculars from
0 to the lines DF and DE, respectively. Because 0 is the

circumcenter of the triangle DEF, the triangles EOD and ODF
are both isosceles with EO = DO = FO. It follows that
LF1JF = LF1JD + LDOF = 2LNOD + 2LDOM = 2LNOM.

Because LOND = LOMD = 90°, the quadrilateral OMDN
is concyclic, from which it follows that LNDM + LNOM =
180° or LBDN = LNOM. Because ABED is concyclic, we

have LBAE = LBDE. Combining the above equations
together, one has
LEOF = 2LNOM = 2LBDN = 2LBDE = 2LBAE.

Because BC is a diameter of r, it follows that
LEOF + LEAF = 2 LBAE + 2 LEAC = 2 LBAC = 180°,
from which it follows that AEOF is concyclic. Let w denote the

circumcircle of AEOF. Because 0 lies on the perpendicular
r-..
bisector of the segment EF, 0 is the midpoint of the arc EF(on
w), implying that AO bisects LEAF and A, C, 0 are
collinear.
8 Let n be a given positive integer. In the coordinate plane,

consider the set of the points
{PH p2' ... ' P4n-t-d

= {Cx, y) Ix andy are integers withxy =0, I x l~n, Iy l~n }.
Determine the minimum of CP1Pz) 2 + CPzPa)
2
+ ··· +
(P4nP4,-t-1) 2 + (P4nHP1) 2
• (Posed by Wang Xinmao)
Solution The answer is 16n -8.
Assume that P, = (x,, y,) for 1 ~ i ~ 4n + 1. Set
We will show that the sum

4..-1-1
S = .L; (P;P;+1) 2 ~ 16n -8.
i=l
First, we show that this minimum can be obtained

by setting
CP10 P2, •.. , P4..t-1) = CC2, 0), (4, 0), ... , Cn, 0),
(n -1, 0), ... , (1, 0), (0, 2), (0, 4), ... , (0, n), (0, n -
1), ... , CO, 1), C-2, 0), C-4, 0), ... , C-n, 0), C-n +1.
0), ... , C-1, 0), CO, - 2), (0, - 4), ... , (0, - n), CO,
- n + 1), ... , CO, -1), (0, 0))
for n even, and
CPu P2, ... , P4..t-1) = ((1, 0), (3, 0), ... , (n, 0),
(n -1, 0), ... , (2, 0), (0, 1), (0, 3), ... , (0, n), (0, n -
1), ... , (0, 2), (-1, 0), (-3, 0), ... , (-n, 0), (-n +1,
0), ... , C-2, 0), CO, -1), CO, - 3), ... , CO, - n), CO,
- n +1), ... , (0, - 2), CO, 0))
for n odd. This can be easily checked. For example, when n =

2m is even, our construction shows that
+ 3(PZmP2m+1) 2 + (P4nP4nH) 2 + CP4..-t-1Pl) 2

= 4C4(m -1) +1 +4Cm -1)) +3 X5 +1 +4
=32m - 8 = 16n - 8.
The exact same argument works when n is odd.

Note that
4..-1-1
S = 2:: [(x; -
i= l
X;+1) 2 + Cy; - Y;+1) 2 ].
By symmetry, it suffices to show that for

{xto Xz, ... , X4n-t-d = { ± 1, ± 2, ... , ± n, 0, ... , 0} ,
~
2n+l Os
and we have
4n+l
Tnc.:1 .x2 •..•• x4nt-1) = ~(x; -x;+I)
2
~8n -4.
i=l
Indeed, for every positive integer n, we are going to prove

that for 1 ~ m ~ n and
{xl o Xz' ... ' Xzm+zn+l} = { ± 1' ± 2 o ••• o ± m o ~},

2n-l-l Os
we have
Zm+2n+l
T m U:p xz· .... xz...H.H) = ~ (x, - X;H)
2
~ 8m -4.
i=l
We take induction on m. For m=1 and
clearly T 1 cx1 , x 2 • •••• .xz...t-3 ) = 8 • 1 -4 = 4, while equality holds for

{xto X20 . . . , Xzn+a} = {0, 1, O, -1, O, O, ... , 0}.
~
2n-2 Os
We assume the result is true form =k <n, and we consider

m = k + 1. By cyclic symmetry, we may assume that either
(1) {xl, xz, ... , XZm+zn+a} = (s, n, t, ... , u, -n, v,
... )
or
(2) {xu Xz, ... , XZm+zn+-a} = (s, n, -n, t, ... ).
For (1), we note that
T i-t-1, (J , n, z , ... , ~, ---n, v, ... )
= (n -s) 2 +(n -t) 2 -(s -t) 2 +(u +n) 2 -(u -v) 2

+ T i: , (s, r, . . . , at, 'V, • • • )
= 2(n -s)(n -t) +2(n +u)(n +v) +Ti,(s.t ........ v •... >
?- 2[n - (n -1) ][n - (n - 2)] + 2[n + (- n + 1)] X
[n + (-n +2)] +Bk -4
=8(k+1)+4,
by the induction hypothesis.

For (2), we note that
T »t c, '"" ____,., e., ••• )

= (n -s) 2 +(n +n) 2 +(n +t) 2 -(s -t) 2 +TA<s.t .... >
= 2n(n -s) +2n(n +t) +2(n 2 +st) +THs.t .... )
?- 2n + 2n + 2(2n -1) + Bk - 4 = B(k + 1) + 4,
by the induction hypothesis.

In every case, we have established our inductive process,
completing our proof.
0 Let n be an integer greater than 3. The points Vt , Vz , ... ,

V .. , with no three collinear, lie on the plane. Some of the
segments V; Vi , with 1 ~ i <j ~ n, are constructed. The
points V; and Vi are neighbors if V; Vi is constructed.
Initially, the chess pieces C 1 , C z , • • • , C.. are placed at
the points Vt, Vz, ... , V .. (not necessarily in that order) ,
with exactly one piece at each point. In a move, one can
choose some of the n chess pieces, and simultaneously
relocate each of the chosen piece from its current position
to one of its neighboring positions such that after the
move, exactly one chess piece is at each point and no two
chess pieces have exchanged their positions. A set of
constructed segments is called harmonic if for any initial
positions of the chess pieces each chess piece C; (1 ~ i ~
n) is at the point V; after a finite number of moves.
Determine the minimum number of segments in a

harmonic set. (Posed by Fu Yunhao)
Solution The answer is n + 1.
For a harmonic set, we consider a graph G with V1 , Vz , ... ,
V,. as its vertices and with the segments in the harmonic set as
its edges.
First, we show that there are at least n edges in G. Note
that G must be connected. Also note that each vertex must have
degree at least 2, because when a chess piece is moved from v,
to Vi there is another piece moved from V, (with k "# j ) to V; .
Hence, the total degree is at least 2n, from which it follows
that there are at least 2n = 2 = n edges.
Second, we show that there are at least n + 1 edges. Assume
that there are only n edges. In this connected graph, each
vertex has exactly degree 2, and hence it must be a complete
cycle. Without loss of generality, we may assume that the cycle
V1-v2-··· v .. -v1 consists of all the edges. In this case, if C1
and C z are placed at Vz and V1 initially, we cannot put them
back to V1 and V2 simultaneously. This is because we can only
rotate all the pieces along the cycle and cannot change their
relative positions along the cycle.
Third, we show that n + 1 edges is enough. We consider the
graph G with the cycle C 1 : V1 - Vz - ·· · - V,. - V1 and one
additional edge, V 2V,.. (This graph G now has the second cycle
Cz:V2-v3-...- v.. -v2.) With this additional edge, we can
switch the relative positions of the chess pieces along the cycle
C 1. Indeed, without loss of generality, we may assume that C;
is at V1 and C i is at V2 initially. Applying rotations on the cycle
C z, we can place C i at V,., i.e. the relative positions of C, and
Ci , along C 1 , are switched. Because we can switch the
positions of any two neighboring pieces in a finite amount of

moves, we can place C 1 , C 2 , ••• , C,. in that order on the cycle
C 1. We can then move each C; to V; by applying rotations
along the cycle C 1 .
Remark What if all the chess pieces have to be relocated at
each move?
Second Day
(0800 -1200; August 14, 2009)
0 let x, y, z be real numbers greater than or equal to 1.

Prove that
(x 2 -2x +2)(y 2 -2y +2)(z 2 -2z +2)
~ (xyz) 2 - 2xyz + 2.
Solution Set a = x - 1, b = y - 1, c = z - 1. Then a , b, c
are positive real numbers. Completing the square for trinomials
of the form A 2 - 2A +2 = (A -1) 2 + 1 transforms the desired
inequality into
(a 2 +DCb 2 +DCc 2 +D
~ [(a + 1) (b + 1) (c + 1) - 1]2 + 1
=(abc +ab +be +ca +a +b +c) 2 +1. CD
From here, we can prove the inequality by direct
expansions on both sides. Instead, we proceed in a slightly
different way. By very simple expansions, we can see that
(A 2 +1)(B 2 +1)
~[(A+ 1)(B + 1) -1]2 + 1
=CAB +A +B) 2 +1,
because the right-hand side has positive extra summands 2AB,

2A 2 B, 2AB 2 • Applying (2) twice [ (first with CA, B) = (a, b)
and then with (A , B)= ( ab +a +b, c ) ] yields CD .
0 The circle r1, with radius r, is internally tangent to the

circle r 2 at S. The chord AB of r2
is tangent to r z at C. Let M be the
~
midpoint of the arc AB ( not

containing S), and let N be the foot Ai--~:'\-'"r-'-'----1
of the perpendicular from M to the

line AB. Prove that AC X CB = 2r X M
MN. (Posed by Ye Zhonghao)

Solution It is well known that S , C, M are collinear.
Indeed, consider the dilation centered at S that sends r1 to r z.
Then the line AB is sent to the line l parallel to AB and tangent
~
to rz, i.e. the line tangent to r 2at M (the midpoint of AB).

Thus, this dilation sends C (the points of tangency of line the
AB and r 1) to M Cthe points of tangency of the line l and r 2) ,
from which it follows that S, C, M are collinear.

By the power-of-point theorem, we haveAC X CB = SC X
CM. It suffices to show that
SC XCM = 2r XMN or
sc MN
2r CM'
Set L MCN = a. Then L SCA = a. By the extended sine
law, we have~; =sin a. In the right triangle MNC, we also
have sin a = ~}j. Combining the last two equations, we obtain CD.
(We can also derive CD by observing that the triangles

MNC and CDS are similar. )
8 On a 10 X 10 chessboard, some 4n unit square fields are

chosen to form a region R. This region R can be tiled by n
2 X 2 squares. If R can also be tiled by a combination of n
pieces of the following types of shapes (with rotations
allowed).
Determine the minimum value of n . ( Posed by Zhu

Huawei)
Solution The answer is n = 4. We call those two kinds of
nonsquare tiles ducks.
First, the left-hand-side figure and the middle figure below
show that n = 4 works.
X X X X
X X X X
X X X X
2 2 b b X X X X
2 2 3 3 a b b c X X X X
1 1 3 3 a a c c X X X X
1 I 4 4 a d d c X X X X
4 4 d d X X X X
Second, we show that n must be even. We mark the

(infinite) chessboard with X in the pattern indicated in the
right-hand-side figure. It is easy to see that each 2 X 2 covers
exactly an even number of crosses (either two or four crosses)
and each duck covers exactly an odd number of crosses (either
one or three crosses). It follows that we must have an even
number of ducks in R, i.e. n is even.
Third, we show that n ~ 2. If n = 2, then R can be tiled by
two 2 x 2 squares. It is clear that these two squares much share a
common edge. Hence, we can have only two possibilities:
It is not difficult to see that is not possible to tile either of

the above configurations by a combinations of two ducks.
0 For positive integer n, an = n J5 - [n JS]. Compute the

maximum value and the minimum value of a 1 , a z , • • • ,
a 2009 • (For real number x, [x ] denotes the greatest
integer less than or equal to x. ) ( Posed by Wang
Zhixiong)
Solution Let bo = 0, b1 = 1, bn = 4b, - z +bn-1 (n ~ 2). Then
b = (2 +JS)n - (2 - JS)n
n 2J5
In particular, b6 = 1292, b1 = 54 73.

For every k = 1, 2, ... , 54 73, there are unique integers
xk, Y k such that 1292k = xk +5473yk, and 1 ~xk ~ 5473. Since
(1292, 5473) = 1, x1, xz, ... , Xs473 is a permutation of 1,
2, ... , 5473, and it is clear that {yk} is nondecreasing:
Y1 ~ Yz ~ ... ~ Ysm = 1291.
For our convenience, let j(x) = x - [x]. We have
j(xk -/5) = j(l292 k J5 - 5473yk -/5)
= !( (2 +J5)6 -2 (2 --/5)6k - (2 +J5)1 - (2 -J5)7 )

2 Yk
= j(- (2 --/5) 6k + (2 -J5)1 Yk ).

Since
0 < -J5) k -
(2 6 (2 -J5) 7 Yk
~ 5473(2 -J5) 6 - 1291(2 -J5) < 1,

7
it follows that
and this is strictly decreasing.

Now t since x1 = 1292 t Xsm = 5473 t Xsm = 418L Xsm =
2889t xs47o = 1597t we see that a1292 attains the maximum and
a1s97 the minimum.
China Western Mathematical
Olympiad
2008 I@D@hi·M®tJ.t.l!il
The 8th China Western Mathematical Olympiad was held from

October 30 to November 4,2008 in Guiyang, Guizhou, China. The
event was hosted by Guizhou Mathematical Society and HS
affiliated to Guizhou Normal University.
The competition committee comprised Zhu Huawei, Wu
Jianping, Chen Yonggao, Li Shenghong, Liu Shixiong, Feng
Zhigang, Tang Lihua, Bian Hongping and Shi Xiaokang.
First Day
( 0800 - 1200; November 1 , 2008)
0 A sequence of real numbers {a,.} is defined by ao * 0, 1,

a1 = l-a 0 , a..-1-1 = 1-a,.Cl-a,.), n = 1, 2, .... Prove
that for any positive integer n, we have
(Posed by Li Shenghong)
Proof From the given condition, we have
i.e. a,+l = 1 - aoa1 •••a,., n = 1, 2, ....

By mathematical induction, when n = 1 the proposition
holds. Assuming that it holds for n = k, then when n = k + 1 we
have
=1.
So it also holds when n = k + 1. Hence, it holds for any
positive integer n.
G In MBC, AB = AC, the inscribed circle I touches BC,

CA, AB at points D, E and F respectively. P is a point
on arc EF (not containing D) . Line BP intersects the
circle I at another point Q, and lines EP , EQ meet line BC
at M, N respectively. Prove that A
(1) P, F, E, Mare concyclic;

EM ED
( 2 ) EN = EP"
(Posed by Bian Hongping)
Proof C1 ) From the given
condition, EF II E C, so
LAEC = LAFE = LAPP + LPFE

= L PEF + L PFE = 180° - L FPE,
and thus P, F, E, Mare concyclic.

(2) By the sine law, EF II EC and the fact that P, F, E,
M are concyclic, we have
EM sinL ENM sinL FEN sin L FPE EF

EN sinLEMN sinC1r- LPFE) sinLPFE EP"
Together with EF = ED, the proposition is proven.
8 Given an integer m ~ 2, and m positive integers a 1 ,

az' ... ' am' prove that there exist infinitely many
positive integers n' such that al • 1n + az • 2" + ... + am •
m" is composite. (Posed by Chen Yonggao)
Proof Let p be a prime factor of a 1 + 2a 2 + ··· + mam. By
Fermat's little theorem, for any k and m satisfying 1 ~ k ~ m,
we have kP - k (mod p). Thus , for any positive integer n ,

we have
- O(modp).
Hence, al. p" +az. zP" + ... +am. m P" (n = 1, 2, ... )

is composite.
0 Given an integer m ~ 2, and two real numbers a, b with

a > 0 and b #- 0, the sequence {x,.} is such that x1 = b and
Xn+1 =ax::' +b, n = 1, 2, .... Prove that:
(1) When b < 0 and m is even, the sequence {x,.} IS
bounded if and only if ab,.--- 1

>- 2;
(2) Whenb <0 and m is odd, or whenb >0, the sequence
{x,.} is bounded if and only if ab"'-1 :< (m - l)"'-l.
m"'
(Posed by Zhu Huawei and Fu Yunhao)

Proof (1) When b < 0 and m is even, in order that abm-1 <
-2, we should first have ab"' + b >- b > 0, and therefore
a(ab"' +b)"' +b >ab"' +b >0, i.e. x 3 >x 2 >0. Using the fact
that ax"' +b is monotonically increasing on (0, +=), it can be
established that each succeeding term of the sequence {x,.} is
greater than its preceding term, and is greater than -b starting
from the second term.
Considering any three consecutive terms of the sequence
x,., x,.+I• Xn+z• n = 2, 3, ... , we have
Xn+z - Xn+l =a (x::'+l - x;:')

= a(x,.+l -x,.)(x::+J.1 +x::'+i2 x,. + ... +x::'-1)
> amx:;r---1 (x,.H - x,.)
>am(-b)"'-1 (xn+1 -x,.)
> 2m(xn+l -x,.)
>xn+l -x,..
It is obvious that the difference of any two consecutive

terms of the sequence {x,.} is increasing, and hence it is not
bounded.
When ab=-1 ~- 2, mathematical induction is used to prove
that each term of the sequence {x,.} falls on the interval [b, -b].
The first term b falls on the interval [b, -b]. Suppose that
the term x,. satisfies the condition b ~ x,. ~- b for a particular
n. Then 0 ~ x::' ~ b"', and hence
b =a X 0"' +b ~Xn+l ~ ab"' +b ~-b.
Thus, the sequence {x,.} is bounded if and only if ab,---1 >- 2.

(2) When b > 0, each term of the sequence {x,. } is
positive. So, we first prove that {x,.} is bounded if and only if
the equation ax"' +b = x has positive real roots.
Suppose that ax"' +b = x has no positive real roots. In such
a case, the minimum value of the function p (x) = ax"' +b - x
on the interval ( 0, + =) is greater than zero. Let t be the
minimum value. It follows that for any two consecutive terms
of the sequence x,. and x,.+l , we have Xn+l - x, =ax::' - x, +b.
Thus, each succeeding term of the sequence {x,.} is greater than
the preceding term by at least t. Hence, it is not bounded.
If the equation ax"' +b = x has positive real roots, let xo be
one of the positive real roots. Then, by using mathematical
induction, we prove that each term of the sequence {x,.} is less
than xo. Firstly, the first term b is less than xo. Suppose that
x,. < xo for a particular n. By virtue of the fact that ax"' + b is
increasing on the interval [0, +=), it can be established that
X,.H =ax::' +b < ax:f +b = Xo.
Therefore, the sequence is bounded.

Further, the equation ax"' +b = x has positive roots if and
only if the minimum value of ax"'-1 + .!!__
X
on the interval (0,
+= ) is not greater than 1, whereas the minimum value of ax...--1 +

.!!__ can be determined by mean inequality, i.e.
X
~ (mahm--
1
a.x
m--1 +~b --a.xm--1 + (m -l)x
b + ... + (m -l)x
b >-
~m -l)m--1 •
As such, the sequence { x,. } is bounded if and only if

(m -l)m-1
~
abm-1
m (m -l)m-1 ~ 1' i.e. abm-1 ~ mm •
Whenb <0, andm is odd, lety,. =-x,.. Theny1 =-b >

0, Y..-+-1 = ay': + (-b), showing that the sequence {x,.} is
bounded if and only if the sequence {y,.} is bounded. Thus, by
using the above reasoning , it can be proven that (2) holds.
Second Day
( 0800 - 1200; November 2, 2008)
0 Four frogs are positioned at four points on a straight line

such that the distance between any two neighboring points
is one unit of length. Suppose that every frog can jump to
its corresponding point of reflection, by taking any one of
the other three frogs as the reference point. Prove that
there is no case where the distances between any two
neighboring points, where the frogs stay, we all equal to
2008 unit of length. (Posed by Liu Shixiong)
Proof Without loss of generality, we may think of the initial
positioning of the four frogs as being on the real number line at
points 1, 2, 3, and 4. Further, it can be established that the
frogs at odd number positions remain at odd number positions
after each jump, and likewise for frogs at even number
positions. Thus, no matter after how many jumps, there are
two frogs remaining at odd number positions while the other
two frogs remain at even number positions. Therefore, in order
that the distances between any two neighboring frogs are all
equal to 2008, all the frogs need to stay at points which are
either all odd or all even, which is contrary to the actual
situation. Hence, the proposition is proven.
0 Given x, y, z E (0, 1) satisfying
~ + {f"="Y + !1-=-i = 2'

v~ v~ v~
find the maximum value of xyz. (Posed by Tang Lihua)
Solution Denote u = ~. Then by the given condition and
mean inequality,
2u 3 =2./xyz =,A~ ..Jx(3-3x)
~ _l_" x + (3 - 3x) = 3../3 _ _l_ ( + + )

~J3L..J 2 2 J3x y z
~ 3.;; -../3 X .Y.Xyz = 3.;; -J3u2.
Therefore, 4u 3 + 2../3 u 2 - 3../3 ~ 0, i. e.
(2u - J3)(2u 2 + 2../3u + 3) ~ O,
and thus u ~ 1· Following this, we have xyz ~ ~~, and
equality holds when x = y = z = ~ . Hence, the maximum

. 27
lS 64.
0 For a given positive integer n, find the greatest positive

integer k , such that there exist three sets of k distinct
nonnegative integers, A = {xl, x2, ... , Xi}, B = {yl,
Y2, .•. , Yi} and C = {zl, z2, ... , z1} with x; + Y; +

z; = n for any 1 <, j <, k. (Posed by Li Shenghong)
Solution By the given condition, we have
k k---1
3k (k -1)
kn ~ ~(x; +y; +z;) ~ 3~i
i=l i=O 2
2
and then k <, [ ; ]+ 1.
2
· 1"11ustrates the case ofk -- [ n]+1:
The f o11owmg
3
Set m E 'Zt. When n = 3m , for 1 <, j <, m + 1 , let x;
j -1, Y; =m +j -1, z; =2m -2j +2; form +2 <,j <,
2m + 1, let x; = j - 1 , y; = j - m - 2, z; = 4m - 2j + 3, and
the result is obvious. When n = 3m+ 1, for 1 <,j <, m, let x; =
j -1, y; = m + j , z; = 2m - 2j + 2; form + 1 <, j <, 2m, let

x; =j+1,y1 =j-m-l.z; =4m+1-2j;andxZm+l =m,
YZm+I =2m+ 1, z2m+1 = 0 will lead to the expected result. When
n = 3m + 2, for 1 <, j <, m + 1, let x; = j - 1, y; = m + j ,
z; = 2m - 2j + 3; for m + 2 <, j <, 2m + 1, let x; = j , y; =
j -m -2, Z; = 4m -2j +4; andx2m+2 =2m +2, Y2m+2 = m,
z2m+2 = 0, and the result follows.
2
In summary, the maximum value of k is [ ; J+ 1.
0 Let P be an interior point of a regular n-gon A1A2 ···An ;

the lines A;P meet the regular n-gonA 1A 2· ..An at another
point B;, where i = 1, 2, ... , n. Prove that
n n
~PA; ~~PB;.
i= l i= l
(Posed by Feng Zhigang)

Proof Denotet = [ ~ ]+ 1, and letAn-H =A 1, j = 1, 2, ... , n.
Noting that the distance between any vertex of a regular

n-gon and a point on its side is not greater than its longest
diagonal d, we therefore have, for any 1 ~ i ~ n,
Furthermore, using the fact that the sum of any two sides
of a triangle is longer than the third side, we have, for any 1 ~
Summing up CD,® fori= 1, 2, ... , n, we have

n n
~(A;P +PA,~) ~nd ~ ~(A;P +PB,),
i.e.
n n 11
2~PA, ~ ~A;P + ~PB;.

i=l i=l i=l
following which the proposition is proven.
2oo 9 It 3'!.t,i!.t.:g•ii!.i.Fi.Q
The 91h China Western Mathematical Olympiad was held from

October 26 to November 1,2009 in Kunming, Yunnan, China. The
event was hosted by Yunnan Mathematical Society and HS
affiliated to Yunnan Normal University.
The competition committee comprised Xiong Bin, Wu
Jianping, Chen Yonggao, Li Shenghong, leng Tak Leong, Liu
Shixiong, Feng Zhigang, Li Jianping, Bian Hongping and Li

Qiusheng.
First Day
(0800- 1200; October 29, 2009)
0 Let M be a subset of R obtained by deleting finitely many

real numbers from R. Prove that for any given positive
number n, there exists a polynomial f (x) of degree n
such that all its coefficients and its n real roots are in M.
(Posed by Feng Zhigang)
Proof Let T = { I x I E R I x fl: M} , which is a finite set by
definition, and a =max T. Choose any real number k > max
{I a I, 1} ; then - k f[ T and hence - k E M.
For any positive integer n, define f (x) = k (x +k )". Then
it follows from k > 1 that deg f (x) = n , and the coefficient of
xmin f(x) is given by
k x (:)xk~rm ~k.
Hence, all the coefficients of f (x) are not in T, and thus are
in M. As the roots of f (x) are all - k with multiplicity n , they
are in M. It follows that the polynomial f(x) = k(x + k)"
satisfies the condition.
0 Let n ~ 3 be any given integer. Determine the smallest

positive integer k , for which there exists a set A of k real
numbers and n real numbers x 1 , x 2, • • • , x .. , which are
distinct from each other such that
X1 + Xz' Xz +X a ' , •• ' Xn-1 +X,.' X., + X1

are all in the set A. (Posed by Xiong Bin)

Solution Let m1 = x1 + xz, mz = xz + xa, ... , m..---1
x..---1 +x,., m,. = x,. +x1.
First, note that m 1 # m 2, otherwise x1 = X3 , which
contradicts the fact that x, are distinct. Similarly, m, # m,H,
for i = 1, 2, ... , n, where m ttt-1 = m 1 , as usual. It follows that
k ~2.
Fork =2,letA ={a, b},wherea #b. Itfollowsthat

X1 +xz =a,
xz +xa =b,
(1) (if n is even)
x ..-1 +x,. =a,

x,. +x1 = b,
or
(2) (if n is odd)

X,.-1 +x,. = b,
x, +x1 =a.
For (2), we have x,. = x 2 , which is possible. For (1), it
follows that
~a= Cx1 +xz) +Cxa +x4) +··· +Cx ..-1 +x,.)
= (xz +x3) +(x4 +xs) + · .. +(x,. +x1)
and hence a = b, which is impossible again. It follows that

k ~3.
For k = 3 , one can construct a valid example as follows:

define xzk- 1 = k (k ~ 1) and xzk = n + 1- k (k ~ 1). When n is

even,
n +1, if i is odd,
{ n + 2, if i is even and i < n,
xi + x i+l = n
z-+2, if i = n, where x,.+l = x,..
When n is odd,
n +I, if i is odd and i < n,
x i +xi+l =
{
n + 2, if i is even,
n - 1 +2 if i = n, where XnH = Xn.
2 '
Therefore, the smallest positive integer k is 3.
8 Let H be the orthocenter of an acute

triangle ABC, and D be the midpoint
of the side BC. A line passing through
the point H meets the sides AB ,AC at
the points F, E respectively, such that
AE = AF. The ray DH meets the
circumcircle of L":,ABC at the point P.
Prove that P, A, E, F are concyclic. (Posed by
Bian Hongping)
Proof On the ray HD, mark a point M such that HD = DM.
Join the segments BM, CM, BH and CH . As D is the midpoint
of BC, the quadrilateral BHCM is a parallelogram, and so
L.BMC = L.BHC = 180° - L.BAC.
Hence,
L.BMC + L.BAC = 180°,

and the point M lies on the circumcircle of

""'ABC. Join the segments PB, PC, PE and
P F. It follows from AE = AF that
L.BFH = L.CEH.
As H is the orthocenter of ~BC,
L.HBF = 90° - L.BAC = L.HCE. (2)
FromCD and(Z), one has """BFHw"""CEH, so
BF CE
BH CH"
As BHCM is a parallelogram, BH = CM, CH = BM, and

hence
BF _ CE
CM- BM" ®
And D is the midpoint of BC. Thus, SMBM S f'>.PCM•
and so
~ BP X BM X sinL.MBP = ~ CP X CM X sinL.MCP.
It follows from LMBP + L MCP = 180° that
BP X BM = CP XCM.
BF CE
With ® and @, one has BP = CP. From L.P BF
L.PCE, one has """PBFw """PCE, and hence L PFB = L.PEC,

and therefore L.PFA = L.PFA. Consequently P, A, E and F
are concyclic.
0 Prove that for any given positive integer k , there exist

infinitely many positive integers n, such that the numbers
are all composite. (Posed by Chen Yonggao)

Proof For any given positive integer k , choose positive
integer m sufficiently large such that 2"' + 3"' - k > 1. Consider
the following k integers:
all of which are larger than 1. From each of these integers,

pick a prime factor: P1, P2, •.. , Pl, and let
where t is an arbitrary positive integer. For any fixed integer i

(1 <,i <,k), onehas2"• -2"' (modp;). In fact, ifp; =2, then
the result is obvious. Assuming that p, =1=- 2, it follows from
Fermat's little theorem that
Similarly, one has 3"• = 3"' (mod p;) . Observe that
Hence, 2"• + 3"• - i is a composite number.

Therefore, n, is one of the positive integers n such that
2" + 3" - 1 • 2" + 3" - 2' . . . ' 2" + 3" - k
are all composite. As t is arbitrarily chosen, there are infinitely

many such positive integers satisfying the conditions above.
Second Day
(0800 - 1200; October 30, 2009)
0 Let {x"} be a sequence such thatx1 E {5t 7} t andx,.+l E

{5"'• , 7"'• } , for n = 1, 2,. . . . Determine all the possible
cases of the last two digits of x2oo9. (Posed by Ieng Tak
Leong)
Solution Let n = 2009. Then we have the following three
cases:
(1) If Xn = 75"',--'J. t thenx,. - 7 (mod 100).
Since both 5 and 7 are oddt xk (1 ~ k ~ n) all are odd. 5"'..--2 -
1 (mod 4) ' i. e. sx..---2 = 4k + 1 for some positive integer k.

If k t m ~ Ot it follows from mathematical induction that
74Hm - 7m (mod 100) t
and hence
x,. = 7s<..-2 = 74k-l-1 - 7 (mod 100).
(2) If Xn = 7''"',--'J. t thenx,. -43 (mod 100).
T",-'J. = ( -1}"..--2 =- 1 = 3 (mod 4) ,
so 7x.-2 = 4k + 3, for some positive integer k. Hence,
x,. = 7'~"•-2 = 74H 3 - 73 = 43 (mod 100).

(3) If x,. = 5x..--l • then x,. = 25 (mod 100).
It follows from mathematical induction that if n ~ 2 t then
5" -25 (mod 100). It is obvious thatx..---1 > 2, and hencex,. =
5"'..--I - 25 (mod 100).

Therefore, the possible cases of the last two digits of x2oo9
are 07 t 25 t 43.
0 Let D be a point on the side BC of an acute triangle ABC.

The circle with diameter ED meets the lines AB and AD
respectively at the points X and P, which are different
from the points B and D. The circle with diameter CD
meets the lines AC and AD respectively at the points Y
and Q, which are different from the points C and D.
Through the point A draw two lines which are
perpendicular to PX and QY with A
the feet of perpendicular M and
N respectively.
Prove that L:,AMN (/) L:,ABC
if and only if the line AD passes Bt<------'<,........r,..-------lC
through the circumcenter of

L:,ABC. (Posed by Li Qiusheng)
Proof Join the segments XY and A
DX. It follows from the given
conditions that B, P, D, X are
concyclic, and C, Y, Q, D are
concyclic. Then
c
LAXM = LBXP = L BDP
= LQDC = LAYN.
And it follows from LAMX = LANY = 90° that L:,AMC(/)

AM AN
L:,ANY, so L MAX LNAY and AX = AY, and hence
LMAN = LXAY.
Combining the two results above, we have L::.AMN (/)
L:,AXY. So we get
L:,AMN (/) L:,AB C ~ L:,AXY (/) L:,AB C

~ XY II BC ~ L DXY = L XDB.
As A, X, D, Yare concyclic, we have .LDXY = .LDAY.

As LXDB = 90°- .LABC,
.LDXY = .LXDB ¢::::> LDAC = 90° - .LABC,
which is equivalent to the fact that the line AD passes through

the circumcenter of MBC.
Hence, MMN(/)MBC if and only if AD passes through
the circumcenter of MBC.
8 There are n ( n > 12) students participating in a

mathematics contest. The examination paper consists of
15 fill-in-the-blank questions. For each question, the
score of a correct answer is 1 point, and no point will be
awarded if the answer is wrong or left blank. After
analyzing all the possible cases of score distributions of
these n students, one finds out that if the sum of total
scores of any 12 students is not less than 36 points, then
there are at least 3 students among these n students who
answer at least 3 identical questions correctly. Determine
the smallest possible value of n. (Posed by Liu Shixiong)
Solution The smallest n is 911. We divide the proof into two
parts:
(1) We first prove that n = 911 satisfies the conditions. If
each student answers at least 3 questions correctly, then for any
15
student there are ( ) = 455 ways for him to have exactly 3
3
correct answers. If there are 911 students participating in the
contest, it follows from the pigeonhole principle that there are
at least 3 students having 3 identical correct answers.
If there is a student X whose score is not more than 2, then
the number of remaining students with a score not more than 3

cannot exceed IO; otherwiset pick any 11 of these students
together with X, and the sum of their total scores is less than 36
points. Then there are more than 9II - II = 900 students in the
rest t such that each of them has a score less than 4. Since ( ~) =
4, and 4 x 900 > 455 x 2, there are at least 3 students answering

3 identical questions correctly.
(2) There are 9IO students participating in the contest.
5
Divide them into 455 = ( I ) groups, and there are exactly 2
3
students in each group. In each groupt both students have the
identical answers with only 3 correct answers indexed by the
group label.
0 Let a1, az, ... , an ( n ~ 3 ) be real numbers satisfying

a1 + az +···+an = 0, and
2a_. ~ak-l +aH-l• fork= 2, 3, ... , n -1.
Determine the smallest it (n) t such that for any k E

{I , 2 , . . . , n } , one has
I a_. I ~). (n) • max{ I a1 I t I an I }•

(Posed by Li Shenghong)
Solution ;. (n)min = : ~ i· First, define a sequence {a.} as

n +I
follows: a1 =I, az =---and
n -I
n +I -2)
ak =- n _
1 + (n 2n(k
-l)(n _ ), fork= 3,
2 4, ... , n.
Thena 1 +a 2 +···+a, =0, and2a• ~ak-1 +aH-1 fork =2, 3, ... ,

n - 1. In this case, it is easy to check that;. (n) ~: ~ i.

Next, suppose that {a._ } is a sequence satisfying the two
conditions stated in the questions. We will prove that the
following inequalities hold:
a .. ~: ~imax{l a1 I, I an 1}, forallk E {1, 2, ... , n}.
Then, using the telescope sum, we have
(k -l)(an -al)
= (k -l)[Can -a,.._l) +Ca ..-1 -a,._z) + ... +Caz -al)]
~ (n -l)[(ak -al-l) +(al-l -ak-z) + ··· + (az -al)]
= (n -I)(ak -al),
and hence
= _!_ [Ck -Dan

n- 1
+ (n- k)a 1 ] . <D
Similarly, for any fixed k , where k (/: {1, n} , and for any
J E { 1, 2, ... , k}, we have
Hence, for j E {k, k + 1, ... , n}, we get
Consequently, we have
• 1 •
~ai ~k _ 1 ~[(j -l)a_. +(k -j)a 1 ]
k
= z-Cal +ak),
Summing up these two inequalities, we find that

l n k n+1-k
ak =~a;+ .2,;a; ~ z-Cal +ak) + 2 (ak +a,)
j=l j=k
k n+1
= z-a 1 + - -a.
2
+ n+1-k
2
a,.
Therefore, we have
From <D and®, fork = 2, 3, ... , n -1, we obtain
I ak I ~max{n ~ 1 I (k -Dan+ (n -k)al I,
n ~ 1 I ka1 + (n + 1- k)a, I}
~: ~ imax{ I a1 I, I an I}.
Consequently, it follows that ii.Cn)min = : ~ i.

China Southeastern
Mathematical Olympiad
2 0 09 It: fht§ ;sur.@!) fht. f:UI

First Day
(0800-1200; July 28, 2007}
0 Find the integer solutions of the function x 2 - 2xy + 126y 2 =

2009. (Posed by Zhang Pengcheng)
Solution Suppose that the integers x, y satisfy
x2 - 2xy + 126y2 - 2009 = 0.
Looking at this as a quadratic function of x ,

1:::. = 4y 2 -4 X (126y 2 - 2009) = 500(42 - y 2) + 36

should be a square number.
If y 2 >4 2 ,thenl:::. <0. Soy 2 < 42 ,wheny 2 E {0, 12 ,
22 , 32 } , 1:::. E {8036, 7536, 6036, 3536 } is not a square number.
For y 2 = 42 , 1:::. = 500(42 - y 2) + 36 = 62 • According to
y = 4, one can get x = 1 or 7 ; according to y = - 4, one can get
x =-1 or -7.
All the integer solutions are (x, y) = (1, 4), (7, 4), ( -1,
-4), (-7, -4).
0 For a convex pentagon ABCDE, AB = DE, BC = EA,

AB 7"= EA, and B, C, D, E are concyclic. Prove that A,
B , C , D are concyclic if and only if AC =AD. (Posed by
Xiong Bin)
Solution First, if A , B , C, D are A
concyclic, by AB =DE and BC = EA we
have L:BAC = L:EDA, L:ACB = L:DAE,
so L:ABC = L:DEA, which means that
AC =AD.
Second, if AC = AD , let 0 be the
center of the circle CB, C, D, E are on the circle). Then 0 is
on the perpendicular bisector ( AH ) of CD . Let F is the
symmetric point of B by the line AH. Then F is on the circle
0. AB 7"= EA, so DE 7"= DF, and thus E, F are not the same
points. Now one can see that D.AFD (/) D.ABC, with AB
DE, BC = EA, and one can get D.AED (/) D.CBA, and so
D.AED (/) D.DFA, which indicates L:AED = L:DFA, and
therefore A, E, F, D is concyclic. This means that A is on the
circle 0, and A, B, C, D are concyclic.
• Let X, y, Z be positive numbers, and ra = x(y - z) 2 ,

.fb =y(z -x) 2 , ,rc = z(x -y) 2 • Prove thata 2 +b 2 +
e 2 >2Cab +be +ea). (Posed by Tang Lihua)
Solution
.fb +rc -ra =-(y +z)(z -x)(x -y),

rc +li -.fb =-(z +x)(x -y)(y -z),
ra +.fb -rc =- (x + y) (y - z)(z- x)'
so
c.fb +rc -ra)crc +li -.fb)(.fi +.fb -rc)

=-(y +z)(z +x)(x +y)[(y -z)(z -x)(x -y)J2
<O.
We can get
2(ab +be +ea) - (a 2 +b 2+ e2 )

=era +.fh +.Jc)<.fb +.Jc -../a)<.Jc +../a -.fbH../a +.fb -.Jc)
<O.
This means that a 2 +b 2 + e 2 > 2(ab +be +ca).
0 There are given 12 red points on a circle. Find the

minimum of n, such that there exist n triangles, whose
vertices are red points, satisfying every chord with red
endpoints being a side of one triangle. (Posed by Tao
Pingsheng)
Solution Let the set of 12 red points be A = {A1, Az, ... ,
A 12 } • From A 1 , one can get 11 chords with red points, but
every triangle with vertex A 1 has two such chords, and so the 11
chords should be in at least 6 triangles with A1 being an
endpoint. The same applies to A; (i = 2, 3, ... , 12); we need
12 X 6 = 72 triangles, and every triangle 12
has 3 points. Son ~ 732 = 24.

9 3
On the other hand, the following
example shows that n can be 24.
Consider a circle whose perimeter is 6
12, and the 12 red points are on the circle with equal distance.
The number of chords with red endpoint is ( 122 ) = 66. If the
length of the minor arc to a chord is k , then say "the chord

belongs to k." So we have only six kinds of chords, and the
number of chords belonging to 1, 2, ... , 5 is 12, and that
belonging to 6 is 6
If three chords belonging to a , b , c (a < b < c) can be the
sides of a triangle, then a +b = c or a +b +c = 12. So the
triangles (a, b, c) E {(1, 1, 2), (2, 2, 4), (3, 3, 6), (2, 5,
5), (1, 2, 3), (1, 3, 4), (1, 4, 5), (1, 5, 6), (2, 3, 5), (2,
4, 6), (3, 4, 5), (4, 4, 4)}.
Now we give an example:
The number of ( 1 , 2 , 3) triangles is 6 , whose vertices are
{2, 3, 5}, {4, 5, 7}, {6, 7, 9},

{8, 9, 11}' {10, 11, 1}' {12, 1, 3}.
The number of (1, 5, 6) triangles is 6, whose vertices are
{1, 2, 7}' {3, 4, 9}' {5, 6, 11}'

{7,8, 1}, {9, 10, 3}, {11, 12, 5}.
The number of (2, 3, 5) triangles is 6, whose vertices are
{2, 4, 11}, {4, 6, 1}, {6, 8, 3} ,

{8, 10, 5} , {10, 12, 7}, {12, 2, 9}.
China Southeastern Mathematical Olympiad 14-1
The number of ( 4, 4, 4) triangles is 3 , whose vertices are

{1, 5, 9}' {2, 6, 10}' {3, 7' 11}.
The number of ( 2, 4, 6) triangles is 3, whose vertices are
{4, 6, 12}' {8, 10, 4}' {12, 2, 8}.
So the minimum n is 24.
Second Day
(0800-1200; July 29, 2009}
0 The set of the permutation X = Cx1, x2, ... , x&) of 1, 2,

... , 9 is A. VX E A, and letf(X) = x1 +2x2 +3x 3 +···
+9x&, M = {f(X) IX E A}. Find the value of IMI.
Solution We prove for n ~ 4. If the permutations X .. =(xu
x2, ..• , x,) of 1, 2, ... , n consist of a set A, and f(X,.) =
x1 +2x2 +3xa +ooo +nx,, M .. = {f(X) I X E A}, then I M .. I=

3
n - n +6
6
Using mathematical induction on n , we see that
M = {n(n + l)(n +2) n(n + l)(n +2) + 1 ., n(n + 1)(2n + 1)}0
" 6 ' 6 '' 6 °
For n = 4, by arranging inequality, one can see the smallest

number of M isf( {4, 3, 2, 1}) = 20, and the biggest number is
f( {1, 2, 3, 4}) = 300 Because
f ( {3' 4' 2. 1}) = 21, f ( {3' 4' 1, 2}) = 22.

/({4, 2, 1, 3}) = 23, /({3, 2, 4, 1}) = 24,
f({2, 4, 1, 3}) = 25, f({l, 4, 3, 2}) = 26,
f ( { 1' 4' 2' 3}) = 27' f ( {2' 1' 4' 3}) = 28'
f ( {1' 2' 4' 3}) = 29'
43 -4 +6
we have, I M 4 I = I {20, 21 , ... , 30} I = 11 = .
6
Suppose that the statement is true for n -1 (n ~ 5). In the
case of n, for a permutation X ..-1 = Cx1, xz, ... , x..---1) of 1,
2, ... , n - 1, let x,. = n; then we get a permutation Cx1 ,
Xz, ... , x,.-1, n) of 1, 2, ... , n, and so
n n-1
~kx1 = n 2 + ~kx1.
k=1 i=1
"
According to the supposition, the value of ~kx 1 can be every
i- 1
integer number in the interval
[ n
2 + (n - l)n (n + 1)
6 'n
2 + (n -l)n (2n -1)
6
J
= [n(n 2 +5) n(n +l)(2n +I)]
6 ' 6 .
Letx, = 1. Then
" ..--1
~kx 1 = n + ~kx 1
i-1 i-1
= n + ~k(xi - I ) +n(n - I )
k=1 2
n
According to the supposition, the value of ~kx1 can be every
i =1
integer number in the interval
n(n +1) + (n -l)n(n +1) n(n +1) +n(n -1)(2n -1)]

[ 2 6 ' 2 6
2
= [n(n +l)(n +2) 2n(n +2)]
6 ' 6 .
Because 2n (n ~ + 2) ~ n (n 26 + S) , according to the

n
supposition the value of ~ kxk can be every integer number in

k~ l
the interval
[ n(n +l)(n +2) n(n +1)(2n +DJ

6 ' 6 .
The statement is also true for n. Since
n (n + 1) (2n + 1) n (n + 1) (n + 2)
6 6
one can see that I M n I = n 3 -

6n + 6 + 1.
In particular, I M 9 I = 121.
G Let 0, I be the circumcenter and

incenter of L"--.ABC. Prove that, for
an arbitrary point D on the circle 0,
one can construct a triangle DEF,
such that 0, I are the circumcenter
E
and incenter of6DEF. (Posed by Tao
Fig.l
Pingsheng)
Solution As shown in Fig. 2, let OJ = d, R, r be the
circumradius and incircle radius of6 ABC. The point K is the
intersection of AI and the circle 0; then
KI = KB = 2Rsin L~AC,
r
AI
. LBAC"
sm 2 KE
Fig. 2
Let the points M, N be the intersections
of the line OI and the circle 0; then
(R +d)(R -d) = IM X IN= AI XKI = 2Rr,
i.e. R 2 -d 2 = 2Rr.
Now draw the tangents DE, DF from D to the circle I.
The points E, Fare on the circle 0. Then DI is the bisector of
L.EDF. It is enough to prove that EF is tangent to the circle I.
Let P be the intersections of the line DI and the circle 0.
Then P is the midpoint of the arc EF, and
. L.EDF r
PE = 2Rsm 2 , DI = . L.EDF'
sm
2
ID • IP = IM • IN = (R +d) (R -d) = R2 - d2 ,
and so
As I is on the bisector of L.EDF, we can see that I is the
incenter of .6.DEF [because L.PEI = L.PIE = ~ (180~ -
L.EPD) = ~ (180"- L.DFE) = L.EDF ~ L.DEF, and L.PEF =
L.~DF; so L.FEI = L.~EFJ. EF is tangent to the circle I.
x(2y- z) y(2z - x) z(2x - y)

8 Let f(x' Y' z) = 1 + x + 3y + 1 + y + 3z + 1 + z + 3x '
where x, y, z ~0, andx +y +z = 1. Find the maximum
value and the minimum value of f (x , y , z). (Posed by
Li Shenghong)
Solution First, prove that f < ~ ; when x = y = z = ~ , we

China Southeastern Mathematical Olympiad 14-5
1
havef = 7·
.
Smce f _ " x (x + 3y - 1)
- LJ 1 +x +3y = 1 - 2 ~ 1 +:+ 3y' by
Cauchy's inequality
~ x 2 1 (~x)z -
1+x+3y ,__ ~xO+x+3y)- ~xO+x+3y)'
and
~x(I +x +3y) = ~x(2x +4y +z) = 2+ ~xy :< ~.
3
"
So LJ 1 + xX + 3y ?:::- 7' f :< 1 - 2x 73 =
1
7; f rn.x =
1
7;
1 1
when x = y = z =
3 , we have f = 7.
Second, prove that f ?:::- 0; when x = 1, y = z = 0, we have
f = 0.
In fact, one can see that
f( x' ) _ x(2y- z) + y(2z -x) + z(2x- y)

Y' z - 1 + x + 3y 1 + y + 3z 1 + z + 3x
2
= xy ( 1 + x + 3y - 1 +} + 3z)
+ xz ( 1 + z2+ 3x - ::--:------=1=---:----::---- )
1 + x + 3y
+ yz ( 1 +: + 3z - 1 +}+ 3x)
7xyz
(1 +x +3y)(l + y +3z)
+ 7xyz
(1 +z +3x)(l +x +3y)
+ 7xyz
(1 + y + 3z) (1 + z + 3x)
~0.
- 1
So f min = 0 and f max - 7.
0 On a piece of 8 X 8 graph paper, at least how

many grids should be taken off, and we cannot
cut out a "T" which has five grids as shown in
Fig. 1? (Posed by Sun Wen-Hsien) Fig.l
Solution At least 14 grids should be taken off. An
example is given in Fig. 2.
X
X
Fig. 2 Fig. 3 Fig.4
See Fig. 3: cut the 8 X 8 graph paper into five areas. We

need to take off two grids from the center areas, otherwise we
can get a "T" with five grids in the area. Because the two grids
with "X" are not equivalent, one is in the corner, and the other
is in the center- only one grid is taken off, and we can get a
"T" with five grids, as shown in Fig. 4.
For the four corner areas, we prove that at least three grids
should be taken off in every area to ensure
that we cannot get a "T " with five grids in )<
the area.
For example, m the upper right
corner, the "T" below as shown in Fig. 5
should be taken off one grid, and the grids
over the "T" should be taken off the " X" Fig. 5
grid. From the "T" below having five cases, we can check that
if only two grids are taken off, we can get a "T" with five
grids, which is shown as follows:
__)< __)< __)<

~~~ ~~~ ~~~
~ )< ~ ~
~ ~ )< ~
X
I
I -1- 3
)< )< ~ I
3-
~~~ ~~~
~ ~ 2
~ :X )<
1-3
I 3- -
I
So the answer is 2 + 3 X 4 = 14.
2010
First Day
(0080 -1200; August 17, 2010}
0 Let a , b , c E {0, 1, 2, ... , 9}. The quadratic equation

ax 2 +bx +c = 0 has a rational root. Prove that the three-
digit number abc is not a prime number.
Solution If abc = p is a prime number, and the roots of the
equation f (x ) = ax + bx +c
2 = 0 are rational numbers, then
b2 - 4ac is a square number, x1, xz are negative, and j(x)

a(x -xl)(x -xz),
Sop= j(lO) = a(lO -x1)(10 -xz), and we get4ap
(20a -2ax 1)(20a -2ax 2 ).
. -b ± ../b 2 -4ac
Smce x1, z = a , we see that 20a - 2ax1,
2
20a - 2ax2 are integers. Now p I 20a - 2ax1 or p I 20a - 2ax 2 , and
we can suppose that p I 20a - 2ax1 ; then p ~ 20a - 2ax1 , and 4a >
20a - 2axz, which is a contradiction to xz being negative.
0 For any set A = {al, az, ••• , am}, let P(A)

2010)
a1az '"am. In addition, let n =( and let A1, Az, ... ,
99
A,. be all 99-element subsets of {1, 2, ... , 2010}. Prove
"
that2011 I ~P(A;).
Solution One can check that 2011 is a prime number. Let
f(x) = (x -l)(x - 2)•••(x - 2010) - (x 2010 +2010!).
Forn E {1, 2, ... , 2010}, we haven 2010 = 1(mod2011)

(by Fermat's little theorem), and 2010! --l(mod 2011) (by
Wilson's theorem), so
f(n) = (n -l)(n- 2)•••(n- 2010) - O(mod 2011).
This means that f(x) = O(mod 2011) have 2010 roots, but the
degree of f(x) is 2009. Using Langrange's theorem, we can see
that the coefficients can all be divided by 2011.
" "
~ P (A;) is the coefficient of x 1911 , hence 2011 I~ P (A;).
i= l i= l
0 The incircle of the triangle ABC touches BC at D and AB

at F, and intersects the line AD again at H and the line

. FD x HK
CF agam at K. Prove that FH X DK = 3.
Solution Let AF = x, EF = y,
CD = z. Then, by Stewart's theorem,
AD2 =ED xAC 2 +CD XAB 2 -ED xDC

EC EC
y (x + z) 2 + z (x + y) 2
-yz B c
y +z
= xz + 4x yz.
y +z
By the power point theorem,

AF 2 x2
AH =AD= AD'
AD 2 -x 2 4xyz
HD = AD - AH = AD = AD(y +z)"
4xyz
Similarly, we have KF = CF (x + Y) ; from D.CDK (/)
DF xCD DF
D.CFD, there follows DK = CF = CF X z.
DF xAF
From D.AFH (/) D.ADF, there follows FH = AD =
~~ X x. Using the cosine theorem, we have
DF 2 = ED 2 + EP -ZED· EFcos E
= Zy z(l- (y + z ) z +Cx + y)z - (x + z )z)
2 (x + y) (y + z )
(x + y) (y + z) ·
4xyz X 4xyz
KF X HD CF ( x + y ) AD ( y + z)
So
FH x DK DF DF
ADX X CF Z
16xy 2 z =
4
DP(x +y)(y +z) ·
D, K, H, Fare concyclic, so by the Ptolemy theorem we

can see that
KF XHD =DF XHK +FH XDK,
FDXHK
and thus FH x DK = 3.
0 Let a and b be positive integers such that 1 <a 
a +b; andifa = 1, thenb{(b +D. Sok >2.
Now, suppose that (a , b) = d, a = sd, b = td, then (s, t) =
1, with t > 1. By std 2 I dlt. (sit. + t"), it follows that st I dH (sit. +

tk), as (st, sit. +tit.) = 1, we have st I d1t.-z, and the prime
divisors of st are the divisor of d.
If s or t has a prime divisor p bigger than 11, then pI d,
and so p 2 I a or p 2 I b, but p 2 > 100; this is a contradiction.
Thus, the prime divisor belongs to {2, 3, 5 , 7} .
Let T be the set of the prime divisors of st. Then T * {3 ,
7}, otherwise one of a orb is bigger than (or equal to) 7 X 3 X
7 > 100, as similarly, T # {5, 7}. SoT is one of the following
sets:
{2}' {3}' {5}' {7}' {2, 3}' {2, 5}' {2, 7}' {3, 5}.
(1) When T = {3, 5}, we haved = 15, ands = 3, t = 5,

and only one good pair (a, b) = (45, 75);
(2) When T = {2, 7}, we haved = 14, and (s, t) = (2, 7)
or (4, 7), and only two good pairs, (a, b) = (28, 98) or (56,
98);
(3) When T = {2, 5}, we have d = 10 or 20, and the
coincide(s, t) =(1, 10), (2, 5), (4, 5), (5, 8)or(2, 5), (4,
5). There are six good pairs (a, b);
(4) When T = {2, 3}, we haved = 6, 12, 18, 24, 30, and
thecoincide(s, t) = (1, 6), (1, 12), (2, 3), (2, 9), (3, 4),
(3, 8), (3, 16), (4, 9), (8, 9), (9, 16) or (1, 6), (2, 3), (3,
4), (3, 8) or (2, 3), (3, 4) or (2, 3), (3, 4) or (2, 3). There
are 19 good pairs (a, b);
(5) When T = {7}, we have (s, t) = (1, 7), d = 7 or 14.
There are two good pairs (a , b) ;
( 6) When T = {5}, we have (s, t) = (1, 5), d = 5, 10, 15
or 20. There are four good pairs (a , b) ;
(7) WhenT={3},wehave(s, t) =(1, 3), (1, 9)or(l,
27) , and the coincide d E {3, 6, ... , 33} , {3, 6, 9} or {3}.
There are 15 good pairs (a , b) ;
(8) When T = {2}, we have (s, t) = (1, 2), (1, 4), (1,
8), (1, 16)or (1, 32), and the coincided E {2, 4, ... , 50},
{2, 4, ... , 24}, {2, 4, ... , 12}, {2, 4, 6} or {2}. There are
47 good pairs (a, b).
So we have 1 +2 +6 +19 +2 +4 +15 +47 = 96 good pairs
(a , b) satisfied.
Second Day
(0080- 1200; August 18, 2010)
0 ABC is a triangle with a right angle at C. M 1 and M z are

two arbitrary points inside ABC , and M is the midpoint of
M 1M2 • The extensions of BM 1 , BM and BM 2 intersect
AC at N 1 , N and N 2 respectively. A
ha M1N1 M 2N2 2 .MN

Prove t t BM1 + BM2 ~ BM'
Solution Let H 1 , H 2 , H be the

projection from M 1, M 2, M to the line B
BC. Then
M1N1 H1C
BM1 BH1 '
MzN2 _ H2C
BM 2 - BH2 '
MN HC
BM BH
Now suppose that BC = 1, BH1 = x, BH2 = y. Then
MzN z H 2C 1- y
BM 2 BHz y
MN HC 1-x+1-y
BM BH X + y
So it is enough to prove that
1-x + 1-y ~ 2 1-x + 1-y

X y X +y
. h ts
wh tc . eqmva
. lent to-
1 + -1 ---- - +
:;::;. 4 , 1.. e. ( x - y ) 2 :;::;.
---- 0.
X y X y
This is obviously true.
Q Let N * be the set of positive integers. Define a 1 = 2, and

for n = 1, 2, ... ,
an+l = . {). 11
mm -
a1
+ -az1 + ... + -an1 +-
1 <
A
1' ). EN*}.
Prove that a,.H = a! -a,. + 1 for n = 1, 2, ....
Solution Sincea 1 = 2, a 2 =min{;. I ;} +

1
< 1,;. EN*}, 1
1 1 1 1 1
froma +;:2andsoa 2 =3.
1
This means that when n = 1, the conclusion is right.

Suppose that for n ~ k - 1 (k ~ 2) , the conclusions are
right, for n = k, from
1 1 1 1 .
As-+-+···+-+-< I, 1.e.
a1 a2 a" A.
1
0<-<1- (1
- + -1+ · · · +1)-'
). a1 a2 a"
1
A.> 1 1 1"
1 - - - - - ··· - -
a1 a2 a"
Now we prove that
By the supposition, for 2 ~ n ~ k, a,. = a,-1 Ca..---1 -1) + 1;

then
1 1 1 1
a,. -1 a..---1 (a,.- 1 -1) a,.- 1 -1 a,.- 1
1
So--= 1 ~1 = 1 - -
- -1- , andL..J- 1 - ,.1.e.
a,- 1 a..---1 - 1 a,. -1 i= 2 a;- 1 a" -1
which means that - -::-------,:=-1-----:::- =a" (a" -1); then

l - -1 - -1 -···- -1
a1 az a"
. {
=mm). -
11
a1
+-az1 + ··· + a.
-1 + -A1 < l.A. EN*}
= a 1 (a 1 -1) + 1.
We get the conclusion for all n: a.n-1 = a! -a, + 1.
8 Let n be a positive integer. The real numbers a1,

a z , • •. , a,. and r 1 , r z , ••. , r,. are such thata1 ~az ~··· ~
a,. andO ~r1 ~rz ~ · ·· ~r,. .

" "
Prove that~ ~a,aimin(r 1 , ri) ~ 0.
i~l j~l
Solution Let
Since
" "
~ ~a 1 ai min(r 1 , ri)
i- 1 j~ l
" "
= ~a1a 1 minCr10 ri) + ~aza 1 min(rz, r;) + ···
j=1 j=l
.. "
+ ~a 4a 1 min(r1 , r 1) +··· + ~a,.a 1 min(r,, ri);
j=1 J- 1
whose k term is
"
~a.a 1 min(r 1 , r 1 )
J-1
=a1a1 r1 +a,.azrz +··· + a•a•r• + a.ta.H1r1 +··· +a.a,.r.,
i.e. the sum of the elements from the k row of the graph, k =
~ "
1, 2, ... , n, we find that .L; .L;a,a;min(r;, r;) is the sum of
i=l j=l
all elements in A1.

On the other hand, the sum can be calculated as follows.
First, count the sum of elements from the first row and the first
column of A1, and let the other elements constitute a graph Az.
Then count the sum of elements from the first row and the first
column of Az, .... So
n ~
.L; .L;a,a1 min(r;, r;)

i- 1 j - 1
= .L;r.(a~ +2ak(aHl +aHz +···+an))

i=l
+rn (~a; Y(wherer 0 = 0)

r.=n
-rl(~a;)
2
-rz(~a,)
2
-•••-r,-1 (~a,)
2
1:=2 1=3 t=n
=
n
.L; (rk - r.t--1) .L;a;
( n )2 ~ 0.
i-1 i-i
0 A1, Az, ... , A a are fixed points on a circle. Determine

the smallest positive integer n such that among any n
triangles with these eight points as vertices, two of them
will have a common side.
Solution First, we prove that if there are r triangles such
that every two of them have no common side, then the

maximum of r is 8.
There are ( :) = 28 chords whose endpoints are from the 8
points.
If every chord belongs to only one triangle, then the
maximum r ~ [ 238 J= 9. But if there 9 triangles such that every
2 of them have no common side, then there are 27 vertices of

this triangle, and there is a point belonging to 4 triangles
(suppose that it is As), whose opposite sides are chords with
endpoints of A1, Az, ... , A7, and so there is a point Ak that is
the endpoint of two triangles, and the two triangles have a
common side As Ak, so r ~ 8.
On the other hand, the following
example shows that r can be 8: from the
picture, the triangle (1 , 2 , 8 ) , (1 , 3 , 3
6), (1, 4, 7), (2, 3, 4), (2, 5, 7), (3,

5, 8), (4, 5, 6), (6, 7, 8) is satisfied.
So the maximum of r is 8.
Back to the problem, the minimum
n is 8 +1 = 9.
International Mathematical
Olympiad
2 009 •• :li§ ,rg ;tCCl§ i.. fi i.kij
First Day
(0900-1330; July 15, 2010}
0 Let n be a positive integer and let a1, a2, ••• , ak (k ~ 2)

be distinct integers in the set { 1 , ... , n } such that n
divides a; (a,+l -1) fori = 1, ... , k -1. Prove that n does
not divide a1 Ca1 -1). (Posed by Australia)
Proof We first prove by induction that for any integer 2 < i <
k, n I a1Ca; -1).
If i = 2, we haven I a1 Ca2 -1) by assumption. Suppose that

n I a1 (a; -1) for some 2 ~ i ~ k -1; then
n I a1 (a; -1) (a;H -1).
By assumption, we haven I a; (a;+l -1) , son I a1a; (ai+l -
1), and therefore
n I (ala;(a;+l -1) -al(a; -l)(a;+l -1)),
i.e. n I a1 (a;+l -1). By the method of induction, n I a1 (a, -1)

holds for every integer 2 :< i :< k. In particular, we have
n I a1Cak -1).
Since a1 (ak - l ) -ak Ca1 -1) = ak -al is not divisible by n
(because a1 and ak are distinct elements in {1, ... , n}), we
conclude that ak Ca1 -1) is not divisible by n.
0 Let ABC be a triangle with circumcenter 0. The points P

and Q are interior points of the sides CA and AB ,
respectively. Let K , L and M be the midpoints of the
segments BP , CQ and PQ, respectively, and let r be the
circle passing through K, L and M. Suppose that the line
PQ is tangent to the circle r. Prove that OP = 0 Q.
(Posed by Russia)
Proof Clearly, the line PQ touches the circle r at the point
M. By the theorem of the tangent chord angle, we have
LQMK = LMLK. Since the points K, M are the midpoints of
the segments BP and PQ respectively, KM II BQ, we get
LQMK = LAQP. Thus, LMLK = LAQP, and similarly
LMKL = LAPQ. As a result, we see that LiMKL and MPQ
are similar, and thus
MK AP
ML AQ'
Since the points K, L and M are the midpoints of the

segments BP , CQ and PQ respectively, we have
· t h'ts mto
PIuggmg · t he prevtous
· ·
equation, BQ = AP
we get CP AQ,
i.e.
AP XCP =AQ XBQ.
By the power law of a point, we have
OP 2 =0A 2 -AP XCP =0A 2 -AQ XBQ =OQ2 •
Therefore OP = OQ, as required.
8 Suppose that s1, sz, sa, . • • is a strictly increasing

sequence of positive integers such that the subsequences
s,1 , s,2 , s,3 , • • • and s,1+t, s,2+t, s,3+t, ... are both
arithmetic progressions. Prove that the sequence s1, s z ,
sa, . . . is itself an arithmetic progression. (Posed by
America)
Proof It follows easily from assumption that s, 1 , s,2 , s,3 , •••
and s,1H, s,2+t, s,3+t, •.• are both strictly increasing sequences
of positive integers.
Assume that s,A =a + (k -Ddu s,A+t = b + (k - l)dz,
k = 1, 2, ... , where a, b, d 1 , d 2 are positive integers. Since
sk < sk + 1 ~ Sk+t, by the monotonicity of the sequence {s,} we
have
L e.
or t equivalently t
Ask is arbitrary, we must haved2 -d1 = 0, i.e. d2 = d1,

denoted by d for both d 1 and d 2. Let b -a = c E N * . If d = 1 ,
by the monotonicity of {s,} we have s,»1 = s,k + 1 ~ s,.+1, and
thus skt-1 ~ s, + 1.
Since s.H-1 > s, t we get skt-1 = s, + 1t i. e. { s, } IS an
arithmetic progression, which is what we want. In what
follows, we assume that d > 1.
We shall prove that skt-1 - sk = c for any positive integer k.
Supposing on the contrary that it is not true, we discuss two
cases.
Case 1: There exists a positive integer k such that skt-1 -
s, <c. Since s.t+-1 - s, are positive integers, we may assume that
s ;+1 - s; = co attains the minimum value for some i ; then
= (a + Csrt-1 -l)d) - (b + (s; -l)d)

=cod -c.
On the other hand, since
(a + id) - (a + (i -1)d + 1) = d -1 t
we have
Sa-HJ - Sa+<i-l)d+1 ~Co (d -1)
(here we have used the minimality of c0 ) • Marking a

comparison with CD, we have co ~ c t a contradiction.
Case 2: There exists a positive integer k such that skt-1
si >c. Since s.H-1 - s1 are integerst and for any k,
we may assume that si+l - si = c1 attains the maximum value for

somej; then
= (a + (si+l -1)d) - (b + (sj -1)d)

= c1d -c.
On the other hand, since

(a + jd) - (a + (j - 1)d + 1) = d - 1,
we have
(here we have used the maximality of c1). Marking a

Comparison with ®, we have c1 < c, a contradiction.
We have verified that s.H-1 - s• = c for any positive integer
k ' i. e. {sn } is an arithmetic progression.
Second Day
(0900-1330; July 16, 2010}
0 Let ABC be a triangle with AB = AC. The angle bisectors

of LCAB and LABC meet the sides BC and CA at D and
E respectively. Let K be the incenter of the triangle
ADC. Suppose that LBEK = 45°. Find all possible values
of LCAB. (Posed by Belgium)
Solution Since AD and BE are the angle bisectors of LCAB
and LABC, their intersection point is the incenter I. Join CI;
then CI is the angle bisector of LACB . Since K is the incenter
of MDC, K lies on the segment CI.
Let LBAC = a, since AB = AC, AD _l BC, we have
LABC = LACB = 90" - ~ •
As BI and CI bisect LABC and LACB respectively,

we get
LABI = LIBC = LACI = LICB = 45" - : .
Thus,
LEIC = LIBC + LICB = 90" - ~ ,
LIEC = LBAE + LABE = 45" + 3:.

So we have
IK = St;,IEK
KC SMXc
tiE X EK X sinLIEK
~ EC X EK X sinLKEC
=sin 45" X IE
. 3a EC
sm4
= sin 45" X sin( 45"- {-)

. 3a
sm4 .
sm (go" - 2a ) •
On the other hand, since K is the incenter of .6.ADC, DK
bisects LIDK. It follows from the property of the angle
bisector that
IK ID sin ( 45" - : )
KC = DC = tanL ICD = .
cos( 45°- :)
Thus,
sin 45" X sin( 45" - {-) sin( 45" - {-)

. 3a
sm4 .
sm (go" - 2a ) cos( 45"- ~ )
Removing the denominators, we have
2sin 45"cos( 45"- ~) = 2sin : cos ~.

3
By the product-to-sum identities, we get
a ) + sm4
· (90" - 4
sm · a = sm4
. Sa + sm4,
. a
or 1 equivalently,
. (go" -4a ) = sm4.

sm . Sa
Since 0 <a< 180", sin( 90"- ~) > 0, we have sin 5; > 0,

5
i.e. 0 < ; < 180". It follows that either
90"- .Q.. = Sa~a = 60"

4 4
or
When a = 60", it is easy to see that .6.IEC (/.) .6.IDK , so

.6.IEK C/.) .6.IDK,
and therefore
L.BEK = L.IDK = 45".
When a = 90" 1
LEIC = 90° - ~ = 45° = LKDC.
Since LIEC = L.DCK, ~ICE and ~DCK are similar,

which implies that
IC xKC =DC xEC.
It follows that ~IDC and ~EKC are similar, so L.EKC =

L.IDC = 90°, and hence
L.BEK = 180° - LEIK - LEKI = 45°.
Combining the above arguments, we conclude that all

possible values of L.CAB are 60° and 90°.
0 Determine all functions f from the set of positive integers

to the set of positive integers such that, for all positive
integers a and b, there exists a nondegenerate triangle
with sides of lengths a, j(b) and j(b + f(a) - 1). (A
triangle is nondegenerate if its vertices are not collinear. )
(Posed by France)
Solution The only f with the required property is f(n) = n
for all n E N* .
By assumption and discreteness of integers, we see that for
any positive integers a , b ,
f(b) + f(b + f(a) -1) -1 ~a,
j(b) +a -1 ~ j(b + j(a) -1),

f(b + f(a) - 1) +a - 1 ~ f(b).
Setting a = 1 in® and@, we have j(b) = j(b + j(l) -1)

for any b E N* .
If j(l) # 1, then the above equality implies that f is
periodic. Since f is defined on positive integers J f is bounded.

Let positive integer M be such that M ~ f(n) for any positive
integer n (i.e. M is an upper bound for f). Putting a = 2M in
CD results in a contradiction. Thus, f(l) = 1.
Settingb = 1 in CD and@, we have f(f(n)) = n for all
n EN*.
If there exist somet EN* such thatf(t) <t, thent ~2 and
f(t) ~ t -1. Setting a = f(t) in@, we have
f(b +t -1) = f(b + f(a) -1)
~f~)+a-1~f~)+t-a
LetM = (t -1) x max f(i). For any integer n > M,

I.,;;;i,;;;r--1
denote by no the unique positive integer satisfying
1 ~ n0 ~ t -1, n 0 =n (mod t -1).

Then
t - 2 M (t - 2)n
f(n) ~f(n 0 ) +--
t- 1
Cn -no) ~-- +
t- 1 t- 1
<n.
Therefore, f(n) < n whenever integer n > M.

Now choose n 1 E N* such that n 1 > M and n 1 is not equal
to any of f(l), /(2), ... , f(M). Sincef(f(nl)) = n1, it
follows that f (n 1) > M, and hence
n1 > !Cn1) > f(f(nl)) = n1,
a contradiction. As a result, we have f(t) ~ t for any t E N* .

Then t = f(f(t)) ~ f(t) ~ t, and all inequalities become
equalities, i.e. f(n) = n for anyn EN*.
It is not hard to check that f(n) = n for all n EN* satisfies
the required property, thus completing our conclusion that the
only solution to the problem is f(n) = n for all n E N* .
0 Let a1, az, ... , a" be distinct positive integers and let M
be a set of n -1 positive integers not containing s = a1 +
a z + ··· +an. A grasshopper is to jump along the real axis,
starting at the point 0 and making n jumps to the right
with lengths a1 , az, ... , an in some order. Prove that the
order can be chosen in such a way that the grasshopper
never lands on any point in M. (Posed by Russia)
Proof We proceed by induction on n. When n = 1, M is
empty, and the result is obvious.
When n = 2, M does not contain at least one of a 1 , a 2 , and
the grasshopper can first jump the number that is not in M,
then the other number.
Let m ~3 and assume that the result is true for any n < m,
n E N* . We shall prove that the result also holds for n = m.
Suppose on the contrary that there exist m distinct positive
integers a1, az, .•• , a,. and a set M of m - 1 numbers, such
that the grasshopper cannot finish the jumping as required in
the problem.
Suppose that the grasshopper can jump at most k steps to
the right with lengths of distinct numbers in a1, az, ... , a,. ,
such that the landing points are never in M. Since M contains
only m - 1 numbers, the grasshopper can always take its first
step. If the grasshopper can jump m - 1 steps, it can also jump
the last step since M does not contain a1 + a z + ··· +a,, and
therefore 1 ~ k ~ m - 2.
We choose such k steps with a minimum total length (if
there is a tie, just choose any one that attains the minimum),
denote the lengths of these k steps by b1, bz, ... , b1, and let
bu1, buz, ... , b,. be the remaining numbers in a1, az, ... , a,.
in increasing order. Clearly,
By assumption, for anyk +1 ~j ~m, b1 +hz +··· +bk +

bi belongs toM. Thus, there are at least m - k elements of M
that are greater than or equal to b1 + hz + ·•· + b._H , and hence
there are at most k - 1 elements of M that are less than b1 +
hz + ••• +bHl·
Let
A= {b, 11 ~i ~k +LiE Z, b1 +bz +··· +bHI -b, f/:M}.
Then bH1 EA. For any b, E A, if we remove b, fromb1, bz, ••• ,
bHl , the sum of the remaining k numbers is not in M, and since
I M n {1, 2, ... 'bl +bz +··· +bHl -b,} l~k -1,
and k < m, by the inductive hypothesis there exists an ordering

c1, cz, ... , ck of these remaining numbers, such that
are not inM. Thus, c1, cz, ... , c1 is also a possible length of k
jumps, and by the choice of bt, hz, ... , b1 we have
i.e. b, ~ bHt for any b, E A.

Let A = {xi, xz, ..• , x1}, where x1 < x z < ··· < xt
bHl· By definition of A, we see that there are at least k + 1- t
numbers of M that are less thanb1 +bz +··· +bHt· Since for any
k + 1 ~j ~ m, b1 + bz + .. · +bi +bi belongs toM, there are at
least m - k numbers of M in the interval
[bl +bz + ... +bHl, b1 +bz + ... +hi +bm].
On the other hand, for any x, E A, the number
b1 +bz + ... +bHl -x; +bm

belongs toM (otherwise, since k <m -2, b,. is different from

b1 , b2 , ••• , blrl-1 , and the grasshopper can take k + 1 jumps).
For 1 < i < t - 1 , the numbers
are pairwise distinct and greater thanb1 +bz + ... +b1 +b,., and
hence there are at least t - 1 numbers of M greater than b1 +
hz + .. +bk +b,.. Summing up, M contains at least
(k +1-t) +(m -k) +(t -1) =m
numbers, which contradicts the fact that M contains onlym -1

numbers.
Thus, our assumption is false, and the result also holds for
n = m. By the method of mathematical induction, the result
holds for every positive integer n.
2010
First Day
(0900-1330; July 7, 2010}
0 Determine all functions f: R-R such that the equality

f([x]y) = f(x)[f(y)]
holds for all x, y E R. (Here [z] denotes the greatest

integer less than or equal to z. ) (Posed by France)
Solution The answer is f(x) = C (a constant function),
where C = 0 or 1 < C < 2.
Setting x = o in <D, we have
/(0) = /(0)[/(y)]
for ally E R. We discuss the following two cases:

(1) When f(O) # 0, it follows from® that [f(y)] = 1 for
ally E R. Then <D becomesj([x]y) = f(x), and settingy = 0
we get f(x) = f(O) = C # 0.
Since [j(y)] = 1 = [C], we have 1 ~ C < 2.
(2) When /(0) = 0, assume that there exists 0 <a < 1 such
that /(a) =F 0. We set x =a in (I), and then f(y) = 0 for all
y E R, which contradicts /(a) #- 0.
We now assume that f(a) = 0 for all 0 ~a < 1. For any
real number z, there is an integer N with a = ~ E [0, 1), and
it follows from <D that
f(z) = /([N]a) = /(N)[/(a)] = 0
for all z E R.
It is easy to check that/(x) = C (a constant function) with
C = 0 or 1 ~ C < 2 satisfies the required property of the
problem.
8 Let I be the incenter of the triangle ABC and let r be its

r
---
circumcircle. Let the line AI intersect
E be a point on the arc BDC and F a point on the side BC
again at D. Let
such that
L.BAF = L.CAE < ~ L.BAC.
Finally, let G be the midpoint of the segment IF. Prove

that the lines DG and EI intersect on r. (Posed by
Hongkong)
Proof Let I a be the center of the described circle of the
triangle ABC with respect to the side BC. Then D is the
midpoint of the segment IIa, DC II I a F and L.GDA = L.FiaA.
To prove that the intersection point P of the lines DG and
EI lies on r, i.e. A, E, D, P are concyclic, is equivalent to
proving that L.GDA = L.IEA, or similarly L.FiaA = L.IEA.
By the assumption L.BAF = L.CAE, A
we have ,6.ABF VJ 6AEC, and hence
AF AC
AB AE" CD
Since
I ID I
+ ~
\ I /
L.AIB = L.C (L.A + L.B), I I
I I I
I
II I
\I I
v
L.ACia = L.C + ~ CL.A + L.B), 10
we have ,6.ABI VJ ,6.AiaC, and thus
AI AC
AB Ala.
From CD and @ we get
AF Ala
AI AE"
By the assumption L.FAia = L.EAI, we have ,6.AFia VJ
,6.AIE, and therefore L.FiaA = L.IEA, which completes the

proof.
8 Let N be the set of positive integers. Determine all

functions g :N- N such that (g(m) + n)) (m + g(n)) is a
perfect square for all m, n E N. (Posed by America)
Solution The answer is g (n) = n + C, where C is a

nonnegative integer.
Clearly, the function g (n) = n + C satisfies the required
property since
(g(m) +n)(m + g(n)) = (n +m +C) 2
is a perfect square. We first prove a lemma.

Lemma If a prime number p divides g (k) - g (l) for some
positive integers k and l, then p I k -l.
2
Proof of lemma: If p I g(k) - g(l), let g(l) = g(k) +
p 2 a, where a is an integer. Choose an integer
D >max{g(k), g(l)},
and D is not divisible by p. Set n = pD - g (k) ; then n + g (k) =

pD, and thus
n + g(l) = pD + (g(l)- g(k)) = p(D + pa)

is divisible by p , but not divisible by p 2 •
By assumption, (g(k) + n)(g(n) + k) and (g(l) +
n) (g(n) + l) are both perfect squares, and therefore they are
2
divisible by p since they are divisible by p. Hence,
P I ((g(n) + k)- (g(n) + l)),

i.e. p Ik -l.
If p I g(k) - g(l) but p 2 does not divide g(k) - g(l),
choose an integer D as above and set n = p 3 D - g (k). Then
g (k) +n = p 3 D is divisible by p 3 , but not by p 4 , and
g(l) +n = p 3D + (g(l)- g(k))

is divisible by p, but not by p 2 • As with the above argument,
we have p I g (n) + k and p I g (n) + l, and therefore
P I ((g(n) +k)- (g(n) +l)),
i.e. p I k -Z. This completes the proof of the lemma.

Back to the original problem: if there exist positive
integers k and l such that g (k) = g (l) , then the lemma implies
that k -l is divisible by any prime number. Hence, k -l = 0, i. e.
k = l, and thus g is injective.
Now consider g(k) and g(k + 1). Since (k + 1) - k = 1,
once again the lemma implies that g(k + 1) - g(k) is not
divisible by any prime number, and therefore
I g <k + D - g <k) I= 1.
Let g (2) - g (1) = q, where I q I = 1. It follows easily by

induction that
g(n) = g(l) + (n -1)q.

If q = -1, then g (n) < 0 for n ~ g (1) +1 , a contradiction.
Therefore, we must have q = 1 and
g(n) = n + (g(l) -1)
for any n E N, where g(l) - 1 ~ 0. Set g(l) - 1 = C (a

constant). Then g (n) = n + C, where C is a nonnegative
integer.
Second Day
(0900-1330; July 8, 2010)
0 Let P be a point inside the triangle ABC. The lines AP ,

BP and CP intersect the circumcircle r of the triangle
ABC again at the points K , L and M respectively. The
tangent to r at C intersects the line AB at S. Suppose
that SC = SP. Prove that MK = ML. (Posed by Poland)

Proof Without loss of generality, we assume that CA > CB.
Then S lies on the extension of AB. Suppose that the line SP
intersects the circumcircle of the triangle ABC at E, F, as in
the figure. By assumption and the power of a point theorem,
we have
SP 2 = SC 2 = SB X SA ,
SP SA
and hence SB = sp· Then,6.PSA UJ
,6.BSP and L.BPS = L.SAP.
r--.. ,.....__
Since 2L.BPS = BE + LF,
~ ~
2L.SAP =BE +EK, we have

M
LF = EK. CD
,.....__ ~ ,.....__
It follows from L.SPC L.SCP that EC + MF = EC +
~
EM, and therefore we have

~ ~
MF =EM.
From CD and @, we get

,.....-........ _,...--.._ ,.-...., ,...--....., ,.-.... ,.....-........
MFL = MF+FL = ME+EK = MEK,
and thus MK = ML.
0 In each of the six boxes B1, B z , B 3, B4, B s , B s , there is

initially one coin . There are two types of operation
allowed:
Type 1: Choose a nonempty box B 1 , with 1 :(;; j :(;; 5.
Remove one coin from B 1 and add two coins to B i+l.
Type 2: Choose a nonempty box Bk, with 1 :(;; k :(;; 4.
Remove one coin from Bk and exchange the contents of
the (possibly empty) boxes B.H-1 and B-'+2.

Determine whether there is a finite sequence of such
operations that results in the boxes B1, B2, B3, B~, Bs
being empty and the box B 6 containing exactly 2010 20102010
coins. (Note that ab' = a <h'). ) (Posed by Holland)
Solution The answer is affirmative.
2010
Let A = 20102010 • Denote by
to mean that there is a finite sequence of operations on the

boxes B;, B;+I , ... , B,+* initially containing b;, b,H, ... , b,+*
coins respectively that results in containing b~, b~+l, ... , b~+*
coins respectively. Then we shall show that
(1, 1, 1, 1, 1, 1 ) - (0, 0, 0, 0, 0, A).
Lemmo. 1 For every positive integer a , 1re have (a, 0, 0)-

(0' 2a, 0).
Proof of lemma 1: We prove by induction onk ~a that (a,
0, 0)-(a - k, 2k, 0).
Since (a, 0, 0)-(a -1, 2, 0)-(a -1, 21 , 0), the
assertion is true fork = 1. Suppose that the assertion is true for
some k <a; then
(a - k, 21 0)- (a - k, 2i -1, 2 ) - · · · -
,
(a - k, 0, 2-'H)- (a - k -1, 2.H-1 , 0),
and thus
The assertion is also true fork + 1( ~ a). By the method of

induction. Lemma 1 is proven.
Lemma 2 For every positive integer a, we have (a, 0,
,2
O, 0)-(0, Pa, O, 0), where P,. 22•• (with n 2's) for a
positive integer n.
Proof of Lemma 2: We prove by induction on k <a that
(a, O, O, 0)-(a-k, PH O, 0).
By the operation of type 1, we have
(a, 0, 0, 0)-(a -2, 2, 0, 0) =(a -1, P 10 0, 0),
and the assertion is true fork = 1. Suppose that the assertion is

true for some k < a ; then
(a -k, P., 0, 0)- (a -k, 0, 2PA, 0)
=(a - k, 0, PHt• 0)- (a - k -1, PHt, 0, 0),
and therefore
(a, 0, 0, 0)-(a -k, P~, 0, 0)-(a -k -1, PH10 0, 0),
i.e. the assertion is also true fork + 1 <a. By the method of

induction, we have proven Lemma 2.
We have
(1, 1, 1, 1, 1, 1)- (1, 1, 1, 1, o, 3)- (1, 1, 1, o, 3, 0)
- (1, 1, 0, 3, 0, 0)- (1, 0, 3, 0, 0, 0)- (0, 3, 0, 0, 0 , 0)-
(0, 0, p3' 0, 0, 0) = (0, 0, 16, 0, 0, 0)- (0, 0, 0, p16' 0, 0)'
and
A = 20102o1o2o1o < (2u )2o1ozo1a
= 211X2010Z010 < 220102011 < 2(211)2011
p
-- 2211XZ011
< 2215
< 161
and thus the number of coins in the box B4 is greater than A.

Therefore, by performing operations of type 2, we have
(0, 0, 0, pl6' 0, 0)- (0, 0, 0, pl6 -1, 0, 0)
- ( 0 ' 0' 0 ' p 16 - 2 ' 0 ' 0)
_ ... _ (o. o, o, !· o, o).

Then we get
(o, o, o, !· o, o)- (o, o, o, o, 1· o)-co, o, o, o, o, A).

0 Let a 1 , a 2 , a 3 ,. • • be a sequence of positive real
numbers. Suppose that for some positive integer s,
we have
a, = max{ai + a,-k I 1 < k < n -l} <D

for all n > s. Prove that there exist positive integers l and
N, with l <sand such that a,. = a 1 +a,.-1 for alln ~N.
(Posed by Iran)
Proof By assumption, for each n > s, a,. can be written as
a,. =ah + aj h,
2
, j z < n, j 1 + )z = n. If h > s, we can
continue to write ah as a sum of two terms of the sequence. We
keep doing this until we obtain
Suppose that a;1 , a;2 is the last step in obtaining®. Then

it + iz > s, and ® is reformulated as
On the other hand, if the indices it, ... , ik satisfy @, we

set si = it + .. · + i j. By <D, we have
Hence, for any n > s , we get

a,. = max{a;1 + ··· +a;1 : Ci1, ... , i*) satisfies@}.
Let m = max {~~ 11 ~i ~ s}, and assume that m = ~~ for

some positive integer l ~ s.
Construct a sequence {b,.} as follows: b., =a,. -mn, n = 1,
2, ... ; then b1 = 0. When n ~ s, we have b,. ~ 0 by definition
of m. Whenn > s,
b, =a,. -mn = max{ai +a ..-~ 11 ~ k ~ n -1} -mn
= max{bk +bd +mn 11 ~k ~n -1} -mn
= max{b 1 +b...--k 11 ~k ~n -1} ~0,
sob,. ~ 0, n = 1, 2, ... , and for n > s,

b,. = max{bi +b,.-k 11 ~k ~n -1}.
If bi = 0 for every k = 1, 2, ... , s, then for every positive

integer n, b,. = 0, and hence a, = nm for every n, and the
conclusion follows.
Otherwise, letM =max I b, I,£= min{ I b, I :1 ~i ~s,
l.,;;i..;;s
b, < 0}. When n > s , we have
and thus 0 ~ b, ~ b,._z ~ ... ~- M.
As for the sequence {b,.}, by® and (J) every b,. belongs to
the set
T = {b;1 +b;2 +· .. +b,1 :1 ~i1, ... , i1 ~s} n [-M, 0].

It follows that Tis a finite set. Indeed, for any x E T, let
Then there are at most M

£
nonzero terms in b,.J [otherwise x <
M (- £) = - M] , and hence there are only finitely many such

£
representations for x.
Thus, for every t = 1, 2, ... , l, the sequence
bm, b<+t+l, br-m-21 , •••
is increasing, and takes only finitely many values, and hence it

is constant eventually, i.e. there is N such that {b,.} is periodic
for n > N with period l ; in other words,
b,. = b...--1 = b1 + b,.-z (n > N + l),
i.e.
a,. = b,. +mn = (b 1 +ml) + (b..--1 +m(n -l))

= a1 +a..-l(n >N +l).

Zlib - Pub Mathematical Olympiad in China 2009 2010 Problems and Solutions

Uploaded by

Copyright:

Available Formats

Zlib - Pub Mathematical Olympiad in China 2009 2010 Problems and Solutions

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Zlib - Pub Mathematical Olympiad in China 2009 2010 Problems and Solutions

Uploaded by

Copyright:

Available Formats

Mathematical

Series Editors: Lee Peng Yee (Nanyang Techrwlogical University, Singapore)

Vol. 1 A First Step to Mathematical Olympiad Problems

Vol. 2 Problems of Number Theory in Mathematical Competitions

Vol. 3 Graph Theory

Vol. 4 Combinatorial Problems in Mathematical Competitions

Vol. 5 Selected Problems of the Vietnamese Olympiad (1962-2009)

Vol. 6 Lecture Notes on Mathematical Olympiad Courses:

Vol. 7 A Second Step to Mathematical Olympiad Problems

Vol. 8 Lecture Notes on Mathematical Olympiad Courses:

Vol. 9 Mathemaitcal Olympiad in China (2009-2010)

- East China Normal

British Library Cataloguing-in-Publication Data

Mathematical Olympiad Series- Vol. 9

ISBN 978-981-4390-21-7 (pbk)

Printed in Singapore by World Scientific Printers.

Lee Peng y ee Nanyang Technological University

FENG Zhigang Shanghai High School, China

WANG Shanping East China Normal Univenity, China

Yao Yijun Fudan Uniw:rsity, China

Qu Zhenhua East China Normal University, China

WONG Fook Sung Temasek Polytechnic , Singapore

KONG Lingzhi East China Normal Unill6sity press , China

The first time China participate in IMO was in 1985, two

The authors of this book are coaches of the China national

experiment, had brought Hungary to the world stage in science.

II , these events had been carried on until today. As for the

Quillen (winner of the Fields Medal, 1978).

International Mathematical Olympiad

The cost is borne by the host country. China had successfully

China had participated informally in the 26th IMO in 1985.

Winners of the IMO

gold medal respectively. He was the youngest participant to

Mathematical competition in China

chaos. The mathematical competition came to a complete halt.

also the middle and elementary school teachers. There is one

Preparation for IMO

interest of students in learning mathematics, to promote the

of the Chinese Mathematical Society. The various provinces,

China Mathematical Competition 1

China Mathematical Competition (Complementary

China Mathematical Olympiad 47

China National Team Selection Test 65

China Girls' Mathematical Olympiad 94

2009 (Xiamen, Fujian) 106

China Western Mathematical Olympiad 117

China Southeastern Mathematical Olympiad 137

International Mathematical Olympiad 157

Part I Multiple-choice Questions (Questions 1--6. six IIUll'ks

Theminimumvalueoff(x) = 5 - 4~;x forx E (-=t

(A) 0 (B) 1 (C) 2 (D) 3

Solution Let x < 2 => 2 - x > o. Then

f(x) = 1 +(4 -4x +x2) = _1_ +C2 -x)

The equality holds if and only if ~ x = 2 - x , and it is so

0 LetA = [ -2, 4), B ={xI x 2 -ax -4 ~0}. If B c:A,

We have B c: A~ x1 ~- 2 and xz < 4. This means that

From the above we get 0 ~ a < 3.

8 A and B are playing ping-pong, with the agreement that

the probabilities of A and B winning a game are ~ and